Java 位运算算法题目练习这个话题我前前后后断断续续刷了两三百道踩了不少坑也慢慢摸到了一些门道。很多新手一看到位运算就头疼觉得这东西要么是脑筋急转弯要么就是竞赛选手炫技用的实际工作里根本用不上。但真在自己做项目时遇到状态位合并、权限掩码、高效哈希、网络协议解析才明白这组运算符不是装饰品而是一套很底层的表达能力。这篇博客就把我刷位运算算法题的经验做个整理从最基本的运算符讲到经典题型的拆解思路再补上 Java 里面特别容易翻车的细节给准备系统练习或者面试前突击的朋友一份能直接照着用的路线。先说清楚这篇能解决什么问题如果你面对“统计二进制里 1 的个数”“找出现一次的数字”“判断是否为 2 的幂”这类题没有稳定思路看完应该能形成一套自己的分析框架如果你已经会做基础题后半部分的掩码设计、移位边界、调试技巧也值得快速过一遍。整篇内容尽量用大白话解释原理代码也都是可以直接复制到 IDE 里运行的完整示例不会只贴半截。1. 为什么练位运算练的本质是什么1.1 位运算不是“智商题”而是“表达力”我见过不少朋友把位运算归类为脑筋急转弯理由是很多题目的解法看起来太巧妙了比如“用异或找唯一出现一次的数字”正常人第一反应是用哈希表谁会想到一堆 ^ 符号但刷多了会发现所谓巧妙其实是对数据特性和运算符语义的深度理解。位运算题练的核心能力有两种状态表示能力把多个布尔状态压缩到一个整数里用一个 int 表示 32 个开关这在真实系统里很常见。运算语义理解、|、^、、、各自的行为边界、优先级、溢出表现只有通过大量精度不高的练习才可能内化。举个例子你要判断一个整数n是不是 2 的幂。最常见的解法是n 0 (n (n - 1)) 0。第一次看到的人会觉得这就是个奇技淫巧但如果你理解n - 1会把最低位的 1 变成 0、把更低位的所有 0 变成 1那么n (n - 1)实际上就是“消去最低位的 1”这个操作。理解到这个层面这题就不再靠背而是你自己也能推出来的结论。练位运算练的正是这种从“记住公式”到“理解公式为什么成立”的转化。1.2 按性质分三类刷题才有章法我给自己整理位运算题目时习惯分成三类每一类的训练目标完全不同特性类考察单个运算符的语义比如与、或、非、异或的性质常见的题有取绝对值、交换两个数、判断奇偶。技巧类考察二进制模式的观察比如 lowbit、n (n - 1)、二分查找中最右侧的 1、位图排序。应用题把位运算当作工具嵌到更复杂的上下文里比如回溯算法里的状态压缩、分支限界、错误检测校验和。很多刷题网站上的“位运算专题”其实把这三类混在一起出顺序也不科学。我的建议是自己按这个顺序重排先把运算符语义打牢再练高频技巧最后去碰状态压缩这种应用题否则很容易在某道 hard 题上卡住产生“我不适合学算法”的错觉。2. 基础特性与高频题型拆解2.1 基础运算符与 Java 里的易错场景先快速过一遍 Java 里的位运算符别看简单后面所有题都建立在它们上面按位与两位都是 1 才得 1。|按位或任意一位是 1 就得 1。^按位异或两位不同得 1相同得 0。~按位取反包括符号位一起翻转。左移低位补 0。右移高位补符号位。无符号右移高位补 0。最容易在 Java 里翻车的其实是右移和二进制的补码表示。以-4为例int 是 32 位-4的二进制也就是11111111111111111111111111111100。-4 1会往高位补 1结果是-2但-4 1会往高位补 0结果就变成了一个很大的正数2147483646。这个差异在很多题里会直接导致结果不对尤其是做无符号场景的数据处理时必须搞清楚你到底要保留符号还是把数字当纯位模式看待。2.2 判断奇偶、交换变量、绝对值这几个基础操作虽然简单却是检验你对位运算语义是否理解的小测验。判断奇偶(n 1) 1表示奇数(n 1) 0表示偶数。为什么不用n % 2 1因为负奇数取余的结果在 Java 里是-1如果写成n % 2 1对-3会得到 false这是个非常隐蔽的坑。位运算版本对负数也一样只看最低位是否为 1反而语义更干净。交换两个整数不引入临时变量int a 3, b 7; a a ^ b; b a ^ b; a a ^ b;原理是三步异或的自反性a ^ b ^ b a。虽然实际开发中我完全不推荐用这种方式交换变量因为可读性差编译器对临时变量的优化已经很好了但面试或者考试里出现这种写法时你要能看懂并解释清楚。取绝对值经典的位运算版本如下int abs(int x) { int sign x 31; // 全 0 或全 1 return (x ^ sign) - sign; }如果 x 是正数sign 为 0结果就是 x如果 x 是负数sign 为 -1x ^ -1等于对 x 取反再减 -1 相当于加 1正好算出了补码意义下的绝对值。但注意Integer.MIN_VALUE的绝对值按 int 是表示不了的这个版本同样会溢出所以题目通常要求你处理不了就返回原值或特殊值。2.3 二进制位统计、汉明距离与二进制倒序统计一个 int 里有多少个 1也就是常说的 popcount是位运算题里辨识度最高的一类。最简单的实现是逐位检查public int countBits(int n) { int count 0; while (n ! 0) { count (n 1); n 1; } return count; }注意这里我用的是而不是因为对负数右移如果补符号位循环会永远结束不了。逐位法时间复杂度是 O(位数)对 int 固定 32 次完全够用。进阶一点的用n (n - 1)每次消去最低位的 1循环次数只和 1 的个数相关public int countBits(int n) { int count 0; while (n ! 0) { n n (n - 1); count; } return count; }汉明距离就是两个整数的二进制位中不同的位数直接Integer.bitCount(x ^ y)一行搞定。很多刚开始练的朋友会在这里疑惑既然 Java 已经提供了Integer.bitCount为什么还要手写因为面试要求的是理解能力和思维过程库函数只能作为优化结论不能替代推导过程。二进制倒序则牵扯到分治思想以 8 位为例先把奇偶位互换再交换相邻两位再交换相邻四位类似一个反向的归并。这类题目适合用来理解位掩码的拼接但对绝大多数后端开发者来说知道思路比死记代码更重要。3. 几类经典题目的完整思路和 Java 实现3.1n (n - 1)系列消去最低位 1这个技巧是位运算题里出现频率最高的单点操作。它的含义是把整数 n 最低位的 1 变成 0其余位保持不变。所以判断 2 的幂如果 n 是正整数且n (n - 1) 0就是 2 的幂。统计 1 的个数每次消去一个 1直到 n 变成 0。判断一个数是否是 4 的幂先判断是否为 2 的幂再看这个唯一的 1 是否在偶数位上。我拿“判断一个整数是否为 2 的幂”来展开完整思路。第一反应很多人会写循环除以 2但位运算要求你直接从二进制模式出发。一个 2 的幂的二进制形式是 1000…0也就是只有一个位是 1其余全是 0。那么问题就变成“这个数的二进制里是否恰好只有一个 1”。利用n (n - 1)可以消去最低位的 1如果消完之后结果是 0说明原本只有一个 1也自然就是 2 的幂。public boolean isPowerOfTwo(int n) { return n 0 (n (n - 1)) 0; }这里为什么不把n 0去掉因为 0 和负数都不可能是 2 的幂而0 (-1) 0会造成误判。我见过很多初学的人在这里漏了正数条件测试一跑发现 0 也返回 true半天找不出原因。同样的思路延伸到“判断一颗完全二叉树是否满二叉树”一类场景可能比较绕但在算法题里n (n - 1)最常见的位置还是组合状态枚举、N 皇后回溯中的剪枝等。你只要记住一个直觉这个操作是“去掉最后一个 1”很多看似无关的题本质都在问你“能不能快速找到最后一个 1 并处理掉”。3.2 异或系列找不同、去重、缺失数字异或运算有三个性质建议直接背熟交换律和结合律意味着一堆数异或跟顺序无关。x ^ x 0同一个数异或自己会变 0。x ^ 0 x和 0 异或等于自己。这三条合在一起就能解决一大票“找唯一出现一次/找缺失数字”的问题。最常见的一道题给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现一次的元素。如果不用额外空间就可以把所有元素全部异或一遍成对出现的都会消成 0剩下的就是那个唯一的值。代码极短public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }换成“找出缺失的数字”也类似如果数组包含 0 到 n 中除了一个数之外的所有数你可以把下标和值一起异或缺失的那个自然就浮现出来。原因是每一个本该出现的数字都会出现两次一回在值里一回在下标里最后只剩下缺失数字本身。异或还有一个容易被忽略的用途找出两个只出现一次的数字。假设数组里只有两个数字出现一次其余都出现两次。第一步先全员异或得到a ^ b。因为 a 和 b 不相等所以这个结果至少有一位是 1。我们可以找到这个结果最低位的 1用它作为分组依据把数组分成该位为 1 和该位为 0 两组这样 a 和 b 必然被分到不同组再分别在组内异或就能分别求出两个目标值。这个过程听起来有点绕但拆开看仍然是三件事全员异或得到差异位用 lowbit 找到分组的掩码分组异或得到两个数。lowbit 的实现也很简单可以记成lowbit x (-x)。它对正整数来说结果是 x 二进制中最低位 1 所代表的数值。例如 12 的二进制是 1100最低位的 1 对应 412 (-12)确实等于 4。这个操作在树状数组、状态压缩里都会反复出现。3.3 移位与掩码bitmask 状态压缩如果说前面的题还在玩单个整数那状态压缩就是位运算真正展示实战价值的地方。它的核心思想是用一个整数的二进制位来表示一组开关状态比如八个棋子的摆放状态、某些任务是否已完成、集合的子集等等。经典的题目是“子集枚举”。给定一个数组求所有子集。常规递归写法需要维护一个临时列表而用位掩码可以更直接地表示“某个元素选或不选”。假设数组长度为 n总共有1 n个子集每个子集对应一个范围在0到(1 n) - 1的整数掩码public ListListInteger subsets(int[] nums) { ListListInteger result new ArrayList(); int n nums.length; for (int mask 0; mask (1 n); mask) { ListInteger current new ArrayList(); for (int i 0; i n; i) { if ((mask (1 i)) ! 0) { current.add(nums[i]); } } result.add(current); } return result; }这里的1 i就是“第 i 位为 1其他位为 0”的掩码用它和 mask 做按位与就能知道当前子集要不要包含第 i 个元素。这个写法在面试里不一定比回溯优雅但它的好处是逻辑清晰而且很容易和“枚举所有组合状态”的需求结合比如旅行商问题的动态规划状态就可以写成dp[mask][i]mask 表示已经访问过的城市集合i 表示当前所在城市。这种写法让状态转移方程变得很紧凑真正体现了位运算的表达力。掩码设计时我建议遵循一个习惯不要把两个不相关的状态塞进同一个 int 的不同位段里除非你真的做好了文档注释。实际项目里做权限系统经常有人把权限位定义成 1、2、4、8、16然后通过|来叠加权限通过来校验权限这本身没问题但一旦权限超过 31 个int 就装不下了得换 long。所以我在项目里定义权限常量时一定会写明每个位代表什么并且用十六进制表示比如0x0001、0x0002这样后续维护的人一眼就能看出位模式。4. 易错点、踩坑实录与调试方法4.1 符号位右移差异负数的坑前面已经提到过和的区别这里再用实际代码说明因为这是我刷题时真正卡过的地方。某次我在写一个“二进制位反转”的题目把输入逐位搬到新数字上代码里写了input 1结果测试负数时死循环或者得到完全错误的结果。后来才发现某个测试用例输入是负数而我希望的语义是“把输入当无符号位模式来看待”所以必须用而不是。看这段代码int n -8; int count 0; while (n ! 0) { count; n 1; }如果换成n 1-8会依次变成-4、-2、-1然后永远停在-1循环根本不会结束。这种问题定位起来很快但如果你不知道对负数会补 1第一次遇到时可能完全摸不着头脑。我的经验是在不需要考虑负数语义的位运算题里一律用右移只有在明确要保留符号的场景才用。同样的道理适用于把 int 转成二进制字符串。Java 自带Integer.toBinaryString它对负数会输出完整的 32 位补码表示这对调试很有帮助。建议在练习阶段多打印Integer.toBinaryString不要只盯着十进制结果看。4.2 运算符优先级和的惨案这个坑太常见了尤其是刚写位运算判断的人几乎都会踩一遍。看下面这段代码if ((n 1) 1) { // 奇数 }括号是必须的吗我直接说必须写。因为 Java 里的优先级高于如果你写成if (n 1 1) { // 编译错误或逻辑错误 }这会被解析成n (1 1)也就是n 1再一次和 1 比较其实不同上下文会有不同的编译错误但总而言之不会按照你以为的“先按位与再比较”来执行。类似的问题也出现在^、|上。最好的习惯就是所有位运算和逻辑判断混用的表达式一律用括号把位运算包起来。这并不丢人反而能避免掉一类非常隐蔽的 bug。除了取反~和加减法的优先级也值得注意例如x ~y很容易让人误解成(x ~) y好在语言层面不会允许这种写法。但当你写复杂表达式时比如(mask (1 i)) ! 0我会建议每一个位移、每一个按位与都单独加括号读代码的人不需要去查优先级表。4.3 调试位运算题的工具方法位运算题目最痛苦的地方在于你盯着1024、520这些十进制数字完全想象不出它们二进制长什么样。所以我做这类题时会在本地写几个调试小工具让整个过程舒服很多。第一个工具打印二进制位模式。public static void printBits(int n) { StringBuilder sb new StringBuilder(); for (int i 31; i 0; i--) { sb.append((n i) 1); } System.out.println(sb); }第二个工具验证位运算表达式。比如我不确定某个掩码算得对不对就直接写一段代码把每一步的掩码和中间结果打印出来。配合Integer.toBinaryString基本能定位绝大多数逻辑错误。第三个习惯边界值优先测试。位运算题要特别关注0、1、-1、Integer.MAX_VALUE、Integer.MIN_VALUE这几个数字。它们分别代表了全 0、全 1、符号位变化等极端情况。我在刷题时会在写完实现后立刻补一个 main 方法把这几个边界值全部跑一遍。比如测 popcount-1应该有 32 个 1如果函数输出不对肯定是移位方向或用错了。5. 怎么正确刷这类题避免重复劳动5.1 练习顺序建议如果你是从零开始我强烈建议按下面的顺序走每一步都不要急着跳先熟悉运算符语义写 10 道最基础的计算题比如判断奇偶、交换变量、取绝对值。再练n (n - 1)和 lowbit 相关题目包括 2 的幂、4 的幂、1 的个数、最低位 1 的位置。然后练异或性质相关题包括 single number、missing number、两个单数。接着是掩码和位移相关题比如子集枚举、二进制倒序、位拆分合并。最后再碰状态压缩的复杂题比如带记忆化搜索的旅行商、N 皇后位运算剪枝。这个顺序的核心逻辑是从“单运算符”到“单技巧”再到“组合应用”每步都在给下一步打底子。很多人刷题喜欢直接上 hard结果被状态压缩里叠加的 DFS、剪枝、位掩码绕晕最后放弃。我倒建议把 hard 题当成“综合应用题”前提是你已经把前面的零件都摸熟了。5.2 面试里的常见追问与应对思路我参加过不少面试也在面试别人时出过位运算题。这类题目其实是很好的“带出思维过程”的工具面试官不一定期待你一步到位而是想观察你有没有分析二进制模式的意识。常见的追问套路有这么几种“你这里的解法用了额外空间吗”——引导你从哈希表转向异或或原地位运算。“数组里有两个数出现一次其他出现两次怎么办”——考验你能不能从异或结果反推差异位。“如果 n 特别大不能放在 int 里怎么办”——引导你考虑 long 或分段处理。“你写的n 1和n 1有什么区别”——考察对符号位的理解。我的建议是在面试里不要急着把最优解法一下子抛出来。可以先把最简单的思路说出来比如哈希表然后分析复杂度再平稳过渡到位运算版本。这个“过渡”本身就能展示你对问题的理解深度比直接默写答案效果好得多。面试官最怕的其实是候选人背了一堆解法但说不清为什么这里能用异或、那里必须用。另一点很实际面试题里的位运算大多不会特别复杂更多是考验边界意识和编码习惯。比如写(n (n - 1)) 0时能不能想起来补上n 0写循环右移时能不能想起来用。这些细节比“记住多少个公式”更能在面试中拉开差距。5.3 项目实战中怎么把位运算用好刷题归刷题位运算最终还是要落地到真实项目里。我自己的实际体会是最能直接迁移过去的是三类场景权限掩码系统用 long 表示一组权限开关|追加权限校验权限 ~撤销权限。状态对象压缩在内存敏感的场景下把多个布尔字段合并成一个整数比如某个协议报文头里十几个标志位。高效哈希和检测布隆过滤器、奇偶校验、循环冗余校验里全是位运算的影子。举一个我在项目中做过的权限判断例子。权限常量定义如下public static final long READ 1L 0; public static final long WRITE 1L 1; public static final long DELETE 1L 2;给某用户加权限就是permission | WRITE;校验权限是(permission WRITE) ! 0撤销权限是permission ~WRITE;。代码非常简洁而且每加一种权限只需要新增一个常量不会出现一堆布尔字段互相纠缠。但这个方案也有一个坑long 只有 64 位如果权限种类超过 64 个就不能硬塞在单个 long 里得换成 BitSet 或分区设计。所以我在代码注释里会写清楚当前系统最多支持多少个权限位以及为什么采用位掩码而不是布尔字段。你会发现项目里写得好的位运算代码都有一个共同点不是因为它巧妙而是因为它有明确的边界定义和注释。这一点恰恰是刷题时容易被忽略的工程素养。6. 常见问题速查与经验总结6.1 位运算题型与解题要点速查表我根据自己的刷题记录整理了一张速查表每次练习前看一遍能很快进入状态。题目类型核心操作关键注意点判断奇偶n 1对负数也有效不会出现取余的 -1 问题判断 2 的幂n 0 (n (n - 1)) 0别忘了正数条件统计 1 的个数n (n - 1)循环负数要用移位避免死循环找唯一出现一次的数全员异或依赖x ^ x 0找两个出现一次的数全员异或 lowbit 分组lowbit x (-x)取最低位 1x (-x)注意输入为 0 时结果是 0子集枚举掩码从 0 到(1 n) - 1数组长度不超过 30防止溢出二进制倒序分治换位用常量掩码比逐位拷贝更快交换两个整数a ^ b; b ^ a; a ^ b;平时项目不建议用这张表里的一半内容本质上都是三个基础操作的组合n (n - 1)、x (-x)、全员异或。所以我不建议死记每道题而是建议记住这三个基础操作再通过练习把它们组装到不同题型里。6.2 我踩过的坑和修正记录最后分享几个这一年里让我印象深刻的踩坑瞬间第一次是统计 1 的个数时用了死在负数用例上。修正是把n 1改成n 1之后负数也能正常统计出 32 个 1。第二次是在子集枚举时数组长度是 31我写了1 31结果变成了Integer.MIN_VALUE循环条件直接崩了。修正是先判断数组长度或者改用1L n来做外层循环边界。这种问题平时不容易遇到但只要数据规模跨过边界就是灾难性的。第三次是我在检查某个权限掩码时漏写了括号写成if (permission WRITE ! 0)编译器直接报错。从那以后我给自己定下规矩任何位运算与逻辑判断混写的表达式一律加括号不要依赖记忆中的优先级表。还有一个小小的优化心得如果一段位运算逻辑在循环里被调用百万次以上可以去看一下Integer.bitCount的源码它用了分治思想通过一组常量掩码并行计算性能会比逐位统计明显更好。虽然是 JDK 内置方法但理解它的原理能让你的位运算水平再上一个台阶。6.3 怎么判断自己真的学会了很多人刷完题会有一个错觉觉得“看懂了”就是“会了”。我的判断标准很简单把解题代码关掉合上编辑器自己在纸上写一遍核心表达式然后给旁边的人解释每一步为什么这么写。如果中间卡壳了或者只能说出“这是套路”但说不出原理那就说明还没真正吃透。这时候不要急着刷下一道回到二进制模式本身拿一张草稿纸把数字写成二进制再演算一遍。位运算题是所有算法题里最适合纸上推演的题型一旦建立了这种直觉后面遇到状态压缩和掩码设计会轻松很多。另外我习惯在刷完每道题后追加一个小问题“如果这个数字变成 long 类型我的写法还成立吗” 这个自问非常有效因为 int 和 long 的差异会逼着你重新审视符号位扩展和溢出边界。比如1 i在 i 超过 31 时会出问题你一旦思考 long 版本自然就会写1L i很多隐患就从源头消失了。我个人在实际操作中的体会是位运算题不需要每天刷很多但一定要保持手感。连续一周不碰再回头写lowbit都会犹豫。保持一个比较舒服的节奏是每天三道位运算小题周日把这一周的错题重新做一遍重点不是数量而是每个核心操作都能脱口而出、随手写出正确代码。这样坚持一个月再看到“位运算算法题目练习”里的各种题型你基本都能快速定位到它到底在考哪一个基础操作思路也会比之前清晰很多。