Java位运算刷题全攻略：原理、技巧与易错点

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 为 -1，x ^ -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 对应 4，12 & (-12)确实等于 4。这个操作在树状数组、状态压缩里都会反复出现。

3.3 移位与掩码：bitmask 状态压缩

如果说前面的题还在玩单个整数，那状态压缩就是位运算真正展示实战价值的地方。它的核心思想是用一个整数的二进制位来表示一组开关状态，比如八个棋子的摆放状态、某些任务是否已完成、集合的子集等等。

经典的题目是“子集枚举”。给定一个数组，求所有子集。常规递归写法需要维护一个临时列表，而用位掩码可以更直接地表示“某个元素选或不选”。假设数组长度为 n，总共有1 << n个子集，每个子集对应一个范围在0到(1 << n) - 1的整数掩码：

public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; for (int mask = 0; mask < (1 << n); mask++) { List<Integer> 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 练习顺序建议

如果你是从零开始，我强烈建议按下面的顺序走，每一步都不要急着跳：

1. 先熟悉运算符语义，写 10 道最基础的计算题，比如判断奇偶、交换变量、取绝对值。
2. 再练n & (n - 1)和 lowbit 相关题目，包括 2 的幂、4 的幂、1 的个数、最低位 1 的位置。
3. 然后练异或性质相关题，包括 single number、missing number、两个单数。
4. 接着是掩码和位移相关题，比如子集枚举、二进制倒序、位拆分合并。
5. 最后再碰状态压缩的复杂题，比如带记忆化搜索的旅行商、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 & (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都会犹豫。保持一个比较舒服的节奏是：每天三道位运算小题，周日把这一周的错题重新做一遍，重点不是数量，而是每个核心操作都能脱口而出、随手写出正确代码。这样坚持一个月，再看到“位运算算法题目练习”里的各种题型，你基本都能快速定位到它到底在考哪一个基础操作，思路也会比之前清晰很多。