第一次让我意识到位运算不是面试八股文是接手一个老系统的时候。配置类里七八个布尔字段加一个新开关就要加一列、加一对getter/setter改动像滚雪球一样烦。后来我改成用一个int存bit标志十几个功能开关的状态用一个整数搞定数据库里也只是一列。从那次之后我开始认真读HashMap源码里的散列扰动看ThreadLocal里的黄金分隔数把Java中位运算这块知识真正捡了起来。这篇文章我以一个写业务代码、也会翻源码的Java工程师视角把位运算的基础行为、真实落点、面试套路和边界陷阱一次讲清楚。适合三类人准备Java面试但遇到位运算总绕开的读JDK源码时被十六进制和移位表达式卡住读不下去的以及单纯想让自己代码更精炼的读者。我尽量不说废话该给代码给代码该给解释给解释。1. 位运算的底层直觉补码、六个运算符与心智模型1.1 为什么Java整数要用补码想理解位运算先得看整数在内存里是怎么存的。Java的int是32位最高位是符号位0表示正数1表示负数。但负数不是简单地把最高位改成1而是采用补码表示。补码的一个关键好处是a - b可以统一成a (-b)减法不需要单独的电路。整个CPU只需要一个加法器就能同时处理加减法符号位不用特殊判断。补码的求法是“取反加一”正数1的二进制是000...001取反变成111...110再加1变成111...111所以-1在Java里是32个1。这就解释了为什么~0等于-1而不是很多人直觉里的“很大的数”。理解了补码位运算就好办了。按位与、按位或、异或、取反这些操作是把两个整数的每一位都当成独立的比特来处理符号位也不例外。所以-1 5这类表达式运算时脑子里不用想正负数先看二进制位即可。1.2 六个运算符速查表Java里的位运算符一共六个运算符名称规则按位与两个位都是1结果才是1|按位或至少一个位是1结果就是1^按位异或两个位不同则结果为1相同则为0~按位取反0变11变0左移高位丢弃低位补0相当于乘以2的k次方带符号右移高位补符号位正数补0负数补1无符号右移高位永远补0注意只有Java等少数语言才有C并没有这个运算符这也是很多C转Java的人容易踩坑的地方后面我会单独讲。移位运算的语义也值得记牢左移a k相当于a * 2^k右移a k相当于a / 2^k向下取整。但负数右移因为是补符号位和单纯除以2的行为在边界上有微妙差异。1.3 用“比特位的布尔逻辑”建立直觉我最开始学位运算时总觉得抽象后来发现一个特别土但有用的理解方式把整数的每一个bit当成一个布尔值1是true0是false位运算就是64个或者说32个并行的布尔逻辑运算。拿0b1010 0b1100来说从低位到高位逐位看第0位0 0 0第1位1 0 0第2位0 1 0第3位1 1 1结果就是0b1000十进制8。或运算和异或同理。这个心智模型一旦建立后面那些复杂技巧都只是在这个模型上加应用层逻辑而已。也可以记几句口诀与运算用于“过滤/保留”某些位或运算用于“合并/打开”某些位异或运算用于“翻转/对比”某些位取反用于“把掩码反过来”有了这些直觉再往下看业务落点就顺了。2. 业务代码里的位运算落点权限位、散列取模与状态压缩2.1 一个int当八个开关用权限位的增删改查先说最接业务的场景权限判断和功能开关。假设一个后台管理系统有三种权限读、写、执行常见的写法是三个boolean字段但字段一多就麻烦。用位标志可以这样public final class Permission { public static final int READ 1 0; // 1 public static final int WRITE 1 1; // 2 public static final int EXEC 1 2; // 4 // 判断是否有某个权限 public static boolean has(int perm, int mask) { return (perm mask) ! 0; } // 追加权限 public static int grant(int perm, int mask) { return perm | mask; } // 移除权限 public static int revoke(int perm, int mask) { return perm ~mask; } // 翻转权限有就变成没有没有就变成有 public static int toggle(int perm, int mask) { return perm ^ mask; } }这个方法我在实际项目里用过最大的收益不是花哨而是扩展性。要加一个“审核”权限只需要加一个常量不用改表结构、不用加字段、不用改实体类。数据库里存一个int跨语言传递也方便。配合IntDef注解甚至可以在Android的lint阶段校验传入范围。2.2 hashCode里的位运算HashMap、ThreadLocal与31的由来读JDK源码时位运算出现频率最高的地方是散列。HashMap在计算桶下标时不会用hash % n而是用(n - 1) hash。前提是n必须是2的幂因为n - 1的二进制是低位全1比如容量16时15的二进制是1111和hash做与运算等价于取hash的低4位。为什么这样设计第一按位与比取模快第二当n是2的幂时取模运算天然可以把散列值的高位信息也利用进来配合前面扰动hash的高位分布更均匀。ThreadLocalMap也是这个套路先用魔数0x61c88647递增出hashCode再 (len - 1)得到数组下标。这个魔数是黄金分割比例相关的一个数能保证生成的散列值在2的幂长度下分布非常均匀。还有一个经典的是String.hashCode()里乘法31 * hashJIT会把它优化成(hash 5) - hash。因为x 5是x * 32再减一次x就是x * 31。所以不要奇怪HashMap相关面试题里为什么总出现移位这些东西在底层就是真实存在的。2.3 位图与状态标记BitSet、布隆过滤器的雏形另一个非常实用的场景是位图。Java标准库提供了BitSet底层是一个long[]数组每一位代表一个布尔值。比如要记录一亿个用户今天是否登录用boolean[]需要约100MB内存用BitSet只需要约12.5MB如果是int位图还能更省。BitSet online new BitSet(100_000_000); online.set(42); // 标记42号用户在线 boolean isOnline online.get(42); // true online.clear(42); // 下线布隆过滤器的思想也是位图的延伸一个元素用多个hash函数算出多个bit位置全部置1判断存在时只要有一个bit是0就说明一定不存在全都为1时只能说大概率存在。所以缓存防穿透、爬虫去重、推荐系统过滤已读内容底层都有位运算的影子。我在一个低内存设备上做在线状态统计时就是靠BitSet撑住的这是少数“位运算真的能救急”的场景。3. 面试高频位运算题四类题型与手写代码路径3.1 奇偶判断、交换数字与大小写翻转面试题里的位运算很大程度上是在考你是否真的理解“单个bit”的含义。判断奇偶(n 1) 0就是偶数因为最低位是1则是奇数。代码很简单但比n % 2 0更接近计算机的底层视角。不引入第三个变量交换两个数int a 3, b 5; a ^ b; b ^ a; a ^ b; // 结果 a 5, b 3原理就是异或的自反性x ^ y ^ y x。但我得说句实在话这种写法在生产代码里可读性很差面试里能答出来就好别真在项目里用。大小写翻转是另一个经典c ^ 32。因为ASCII里大写字母和小写字母刚好差32比如A是65a是97写成二进制就是第5个bit不同。对字符的int值异或32就可以在大小写之间来回切换。这个技巧在读源码时见过自己写很少用但理解了会很快乐。3.2 找出唯一出现一次的数字异或抵消的进阶用法LeetCode上“只出现一次的数字”是位运算题里的常青树。一个整型数组里除了一个数字出现一次其他数字都出现两次找出那个一次的数字。public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }核心是异或的运算律相同数字异或为00异或任何数等于它自身。所有成对的数字互相抵消最后剩下的就是落单那个。空间复杂度O(1)时间O(n)这是面试官想看到的答案。再往上考一档“有两个数字只出现一次其他都出现两次”这时候就不能简单异或了。思路是先把所有数异或一遍得到a ^ b因为a ! b所以a ^ b的二进制里至少有一位是1找到最低位的1作为分组依据把原数组按这一位是0还是1分成两组各自异或就能分别得到a和b。这个“分组异或”的思路值得写一遍public int[] singleNumbers(int[] nums) { int xor 0; for (int num : nums) xor ^ num; int mask xor (-xor); // 取最低位的1 int a 0, b 0; for (int num : nums) { if ((num mask) 0) { a ^ num; } else { b ^ num; } } return new int[]{a, b}; }注意xor (-xor)这个写法负数在补码体系下这个表达式能快速拿到最低位的1。这也是位运算题里特别常用的一个小技巧。3.3 数二进制中1的个数n (n-1) 循环统计一个整数二进制表示里有多少个1最常见的是n (n - 1)循环。这个操作每次会把最低位的1消掉循环几次就有几个1。public int bitCount(int n) { int count 0; while (n ! 0) { n (n - 1); count; } return count; }比如n 12二进制110012 11结果是88 7结果是0循环两次说明有两个1。这个算法比逐位判断快得多。但真的写代码时不需要自己实现Integer.bitCount(int i)在JDK里已经提供了底层用的是并行分组统计的思路先把相邻两位相加再把相邻四位相加一层层归约效率极高。面试时如果能把Integer.bitCount的分组思想讲明白绝对加分。简单说就是“分治加法”把32位分成16组每组2位统计1的个数再合并成8组、每组4位一直到一组32位。3.4 判断2的幂与向上取整到2的幂HashMap的tableSizeFor判断一个数是不是2的幂(n (n - 1)) 0同时要排除n 0。public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }顺着来一个工程里真实使用的升级版给定一个数返回大于等于它的最小2的幂。HashMap扩容时需要这个源码里的tableSizeFor是这样的思路static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : n 1; }原理是把最高位的1通过五次右移和或运算“复制”到所有低位让n变成全1最后加1进位得到一个2的幂。当初第一次看这段时觉得非常精妙理解了之后就明白HashMap为什么能保证容量永远是对齐到2的幂的。4. 一不留神就翻车位运算的优先级、负数与类型陷阱4.1 优先级比较运算比位运算更高位运算踩坑第一名是优先级。、|、^这些运算符的优先级低于和!低于关系运算符。也就是说if (a b 0) { // 实际执行的是 a (b 0)编译都过不了或者行为完全错误 }正确写法是if ((a b) 0)。类似的还有移位运算的优先级低于加减法a 2 1实际上是a (2 1)等于a 3。很多人第一次写位运算表达式时都会被这个坑绊倒。我的经验是位运算表达式一律加括号不要省省下的那点字符远不如多花一秒钟确认优先级值得。4.2 负数右移算术右移与逻辑右移的符号填充负数参与右移是第二个高频坑。-2的二进制是111...110带符号右移一位-2 1结果是-1因为高位填充的是符号位1而无符号右移-2 1结果是2147483647因为高位补的是0。C里的对负数到底是算术右移还是逻辑右移是“实现定义”的Java则明确区分了和这导致很多从C转Java的人一开始会懵。~n是按位取反结果是-(n 1)。~5 -6这在写权限移除代码时很容易出错。比如perm ~READ如果忘记~的语义把perm READ权限就从“移除”变成了“只保留这一个”逻辑截然不同。我的建议是涉及位运算的代码旁边一定要写注释尤其是~和这种不直观的运算符。4.3 移位距离取模与byte/short的整型提升Java的移位是按“移位距离 mod bit数”来算的。int是32位所以只会用到移位距离的低5位long是64位只会用到低6位。换句话说int a 1; int result a 32; // 实际按 a 0 处理结果是1不是0这个问题在循环里特别隐蔽如果一个循环变量从0递增到32某一次正好等于32你预期左移32位结果应该是0实际却是原值。处理这类边界最好的办法是显式判断移位距离或者用long测试。还有一个类型提升问题byte和short在做任何算术或位运算前会先提升为int结果也是int。所以short s -1; s s 1;会编译报错必须强转。复合赋值运算符如|、虽然没有显式类型报错但内部实际上也隐含了一次强制转换转换时会丢掉高位非常容易埋坑。按位或赋值a | b确实很方便但要确保操作数类型一致并且知道你正在修改的是哪个位。4.4 位运算代替取模的硬前提除数必须是2的幂网上有很多“用位运算代替取模”的优化说法误区在于这个结论有严格前提x (n - 1)等价于x % n只在n是2的幂时成立。当n 8时x 7和x % 8结果一样因为x的低3位就是余数。但当n 10时x 9根本不是余数比如13 9 9而13 % 10 3完全不对。所以HashMap才费那么大劲把容量对齐成2的幂。有热词问“判断字符串中是否不是字母和数字”能不能用位运算这个需求用ASCII范围判断比位运算更清晰比如c 0 c 9这样直接写出来任何人都能读懂。位运算真正适合的是“同一个bit位上的状态”而不是所有运算场景。判断字符范围这种事情别为了炫技硬上位运算维护成本会反咬一口。5. 什么时候真正值得用位运算性能真相与可维护性权衡5.1 JIT和CPU已经很快位运算不是银弹很多初学者以为把乘除改成移位就能让代码“飞起来”但现代HotSpot JVM的JIT编译器已经很聪明它会把x * 2识别成移位操作把x % 2的常见模式优化得很快。绝大多数业务代码的瓶颈在IO、锁竞争、数据库查询、网络序列化位运算带来的纳秒级差异在业务层根本感知不到。我在一个真实的统计接口里做过对比把某段循环里的取模改成位运算压测结果几乎没区别反而代码可读性明显下降。后来我把那段改了回去补了注释说明为什么当初想优化。性能优化的第一原则是先度量再动手而不是靠感觉。5.2 真正值得用的三个场景那么到底哪些场景值得用位运算第一个是底层数据结构和框架实现。HashMap的散列定位、LongAdder的Cell哈希、ThreadLocal的索引计算、ReentrantReadWriteLock里的读写状态用一个int变量表示这些都依赖位运算因为它们在极高频路径上执行并且一个int存两个状态能省内存、保证原子性。第二个是内存敏感的位图场景。一亿个布尔标记用BitSet比boolean[]省87.5%的内存这种场景收益是数量级的不是微乎其微。第三个是特定算法和传输协议。比如布隆过滤器、状态压缩DP用一个int表示一个集合、IP地址与int的互相转换、CRC校验和哈希散列的混合运算这些本身就是位运算定义出来的领域不用才奇怪。5.3 用标准库“曲线救国”说到日常开发标准库其实已经帮你封装好了大部分位运算需求。需要计数用Integer.bitCount需要最高位用Integer.highestOneBit需要前导零统计用Integer.numberOfLeadingZeros需要位图用BitSet。int x 80; int highest Integer.highestOneBit(x); // 64 int count Integer.bitCount(x); // 2 int floorPower Integer.highestOneBit(x); // 不大于x的最大2的幂 int ceilPower 1 (32 - Integer.numberOfLeadingZeros(x - 1)); // 向上取整到2的幂能用标准库就不要手写一是稳定二是代码意图清晰。JDK的维护者比你更了解边界行为的定义。5.4 可维护性自查表我自己在代码里用位运算之前会先过一遍这个自查表场景建议原因权限位、功能开关用位标志但常量必须命名清晰扩展性好省字段业务计算中求余/除法优先用%和/不加括号不放心可读性优先JIT会优化判断字符是否是字母数字直接用ASCII比较不需要炫技底层框架、高频散列放心使用位运算收益明确任何位运算表达式全部加括号避免优先级踩坑涉及负数右移和~旁边写注释语义不直观复合赋值运算符确认类型一致注意溢出隐含强转容易丢高位这张表不是死规矩而是提醒自己位运算是一种能力不是一种标签。用得对代码精炼且高效用得不对就是给自己和别人挖坑。最后再分享一点个人体会。我现在的习惯是遇到HashMap源码、布隆过滤器、权限位这种场景会主动用位运算其他业务判断一律先写最直白、最容易被理解的版本。如果某个循环压测后确实是热点再考虑用 (n - 1)或者移位去优化而且优化完必须配注释和测试。标准库里Integer.highestOneBit、Integer.bitCount、Integer.numberOfLeadingZeros这些方法其实已经把你手写位运算的大部分需求都覆盖了遇到类似需求先查一下标准库比自己从零开始写稳太多。位运算就像一把趁手的小螺丝刀用对地方很香但别因为有了它就想去拧家里每一颗螺丝。