之前在面试现场，我问过一位候选人 LeetCode 191 这道题：统计一个整数的二进制表示里有多少个 1。他很快写了个循环右移的版本，但当我追问“能不能把 32 次循环降到只循环 1 的个数那么多次”时，空气安静了几秒。位运算就是这样，看起来像是冷门技巧，实际上每一次刷题都绕不开，而且面试官特别喜欢往里挖一层。它考的不是背 API，而是你有没有真正理解整数在计算机里的样子。
这篇不打算泛泛讲位运算理论，直接围绕四道经典题目展开：191. 位1的个数、231. 2的幂、190. 颠倒二进制位、371. 两整数之和。这四题难度都不高，但每道题都对应一个非常核心的位运算性质，吃透了它们，后面再碰位运算相关的题目基本都能一眼看出方向。无论你是刚准备面试，还是刷题刷到瓶颈想换个角度突破，这四题都值得花一个晚上认真搞明白。
1. 位运算这关躲不掉：先把底料备齐
1.1 面试为什么爱考位运算
位运算题目看起来花样很多，但底层考察的点其实特别集中：第一，你是否了解整数在内存中是以二进制补码形式存在的；第二，你能不能跳出“十进制思维”，用位视角去看一个数；第三，你有没有能力在常数时间内完成某些判断或统计，把时间复杂度从 O(log n) 甚至 O(n) 压到 O(1)。
举个例子，判断一个数是不是 2 的幂，常规思路是不断除 2，时间复杂度 O(log n)。但如果用n & (n-1)，一次位运算就能出结果。这种“降维打击”式的解法，正是很多公司在算法面试里想看到的思维层次。另外，位运算在底层系统里频繁出现：状态压缩、权限位标记、Hash 散列、图像处理、树状数组，甚至数据库的位图索引，全都建立在同一套机制上。所以面试官爱考位运算，不是因为它偏，而是因为它真的很实用。
1.2 基础运算符与补码常识
先把工具表列出来，后面所有题目都离不开这几个操作符。
| 运算符 | 含义 | 记忆要点 |
|---|---|---|
& | 按位与 | 两位都是 1 才为 1，有 0 则 0 |
| | 按位或 | 两位有一个 1 就为 1 |
^ | 按位异或 | 相同为 0，不同为 1 |
~ | 按位取反 | 0 变 1，1 变 0 |
<< | 左移 | 右边补 0，相当于乘 2 |
>> | 算术右移 | Java 中符号位填充，相当于除以 2 取整 |
>>> | 无符号右移 | 高位补 0，Java 专属 |
这里重点说补码。Java 的int是固定 32 位的，负数以补码形式存储，比如-1在 32 位视角下就是111...111（32 个 1）。Python 不同，它的整数没有固定长度，负数在概念上可以一直向左延伸出无穷多个 1，所以处理负数的位运算时经常要主动加一个掩码，模拟 32 位环境。这也是很多人写 Python 版位运算题会卡住的原因。
需要随手记下的四组核心性质，后面会反复用到：
x & (x - 1)：消除最低位的 1。x & -x：提取最低位的 1。x ^ x = 0、x ^ 0 = x：自己异或自己清零。x ^ 0xFFFFFFFF：对低 32 位全部取反。
这四组性质就像是位运算世界的“乘法口诀”，背熟它们，做这四道题会很顺。
2. 191. 位1的个数：三种套路一次吃透
2.1 题目要点与零基础入口
题目要求很简单：输入一个无符号整数，返回它的二进制表示中有多少个 1。比如00000000000000000000000000001011里有 3 个 1，所以答案是 3。
有一个容易绕弯的地方：Java 里其实没有无符号int，但位模式是完全一样的。换句话说，就算传入一个负数，你也只需要把它当成 32 位的二进制串来看，内存里是什么样就统计什么样。比如-1的 32 位补码是全 1，结果应该是 32。这个理解到位了，代码就不容易写偏。
2.2 逐位检查法：先保证对
最直白的思路是：每次看最低位是不是 1，然后右移一位，重复 32 次。右移的操作在 Java 里要用>>>，因为如果是负数，普通的>>会在高位补 1，虽然当前这位的取值不受影响，但要养成用无符号右移的习惯。
public int hammingWeight(int n) { int count = 0; while (n != 0) { count += n & 1; n >>>= 1; } return count; }这段代码里n & 1只保留最低位，是 1 就加进去，不是 1 就加 0。循环次数是固定的 32 次，因为 Java 的int只有 32 位。时间复杂度严格说是 O(32)，也就是常数时间，空间复杂度 O(1)。这个版本的好处是几乎不可能出错，适合作为面试时的兜底答案。
2.3 Kernighan 位计数法：把循环次数降为 1 的个数
逐位检查虽然正确，但有点“笨”：如果整数只有 1 个 1，它依然要循环 32 次。Kernighan 位计数法就是冲着这个问题去的，核心就一句话：n &= n - 1会消除掉最低位的那个 1。
为什么能消除？举个例子，n = 6，二进制是110。n - 1 = 5，二进制是101。两者相与，得到100，也就是 4。原本最低位的那个 1 被消掉了。再对 4 执行一次，4 & 3 = 0，两个 1 全部消除，所以 6 的二进制里有 2 个 1。
public int hammingWeight(int n) { int count = 0; while (n != 0) { n &= n - 1; count++; } return count; }循环次数不再是固定的 32，而是二进制中 1 的个数。极端情况全是 1 时依然是 32 次，但平均下来快很多。这个技巧在真实项目中非常常见，比如统计一个集合中有几个元素被选中、判断权限标志位组合等。
2.4 工程爽快方案：内置 bitCount / popcount
实际工程里，Java 直接调用Integer.bitCount(n)，C++ 用__builtin_popcount，Python 用bin(n).count('1')也能实现。这些内置实现通常会查表或使用分治算法，性能很高。但面试的时候不建议一开始就抛内置函数，因为面试官想看的是你能否手写原理。比较稳妥的做法是：先讲清楚 Kernighan 的原理，然后补充一句“在工程上我会直接用内置方法，因为它经过充分优化且可读性更好”。
| 解法 | 循环次数 | 可读性 | 适用场景 |
|---|---|---|---|
| 逐位检查 | 固定 32 次 | 高 | 面试兜底 |
| Kernighan | 1 的个数次 | 高 | 手写面试题、嵌入式 |
| 内置 bitCount | 常数 | 极高 | 生产环境 |
3. 231. 2 的幂：一个二进制特征解决两种写法
3.1 先分清边界：0、负数、大数
判断一个整数是不是 2 的幂，看起来是数学题，其实是二进制特征题。2 的幂在二进制里有一个明显的身份标识：只有一个位是 1，其他位全是 0。比如 1 是1，2 是10，4 是100，8 是1000。
边界条件必须一次想清楚。0 不是 2 的幂，负数也不是，所以判断条件里n > 0不可缺少。很多人在n & (n - 1) == 0这条路上翻车，就是因为忽略了 0 也满足这个等式，最后返回了错误结果。
3.2 方案一：n & (n-1) 消除唯一的 1
既然 2 的幂只有一个 1，那就用上一题学到的技巧：n & (n - 1)消除最低位的 1。如果消除之后变成 0，说明原来只有一个 1，那就一定是 2 的幂。
public boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }比如n = 8，二进制1000，n - 1 = 0111，相与得到0000，返回 true。n = 12，二进制1100，n - 1 = 1011，相与得到1000，不是 0，返回 false。这个写法已经是最优解，时间复杂度 O(1)。
3.3 方案二：n & -n 提取最低位再比较
另一种思路来自 lowbit 操作。n & -n能提取出最低位的 1。如果n本身就是 2 的幂，那么它唯一的那个 1 就是最低位的 1，提取出来应该等于它自己。
public boolean isPowerOfTwo(int n) { return n > 0 && (n & -n) == n; }拿n = 16验证，-16的补码表示与 16 相与后仍得 16，条件成立。拿n = 24验证，24的二进制是11000，最低位的 1 是1000，也就是 8，不等于 24，返回 false。两种方案都很好，区别只在于一个消除最低位，一个提取最低位。面试时如果你能说出两种写法，并解释它们的等价性，会显得对位运算非常熟练。
3.4 语言差异提醒：Python 无限长与 JS 32 位限制
Python 里写这个题目时，n > 0条件同样不能省。Python 的整数是无限长的，负数位运算时会表现为无限长的补码，但在这个题里只要先用n > 0拦住负数和 0，后面的位运算就不会出问题。JavaScript 则要注意，位运算符会先把操作数转成 32 位有符号整数，超出范围的部分会被截断，所以如果输入接近2^31附近，某些写法可能踩坑。稳妥起见，可以提前用常规判断拦截，或者直接用Math.log2这类接口来佐证。
4. 190. 颠倒二进制位：从逐位搬到分治
4.1 最直观的字符串法不是不能用
看到“颠倒二进制位”，脑子里第一个反应通常是：把数字转成二进制字符串，翻转，再转回整数。这个思路没有错，但需要处理好两个细节：前导零补齐和语言对负数的字符串表示。
可以用伪代码描述这个过程：
bin = 转成二进制字符串 bin = 左侧补零到 32 位 result = reverse(bin) 转成整数代码很简单，但面试时我建议把它当作“理解题意”的辅助，而不是最终提交方案。一是转换过程涉及多次字符串操作，性能一般；二是不同语言对负数转二进制的处理不一致，容易踩坑。作为第一思路和面试官讲清楚，再引导到逐位操作上，是比较自然的答题节奏。
4.2 常规逐位翻转：循环 32 次
真正的常规解法是逐位搬移：每次取出原数的最低位，放进结果的最低位，然后把结果左移一位腾出位置，原数右移一位准备取下一位。循环 32 次后，原数的最高位就跑到了结果的最低位，实现颠倒。
public int reverseBits(int n) { int result = 0; for (int i = 0; i < 32; i++) { result = (result << 1) | (n & 1); n >>>= 1; } return result; }核心步骤拆开看：n & 1取出当前最低位；result << 1给新位腾位置；|运算把该位放进去；n >>>= 1用无符号右移处理原数。注意这里千万不能用>>，否则遇到负数时高位补 1，取位逻辑就全乱了。这个方法复杂度 O(32)，已经能通过全部测试，工程上也够用。
4.3 分治交换：面向 32 位的并行手法
逐位翻转没问题，但 32 次循环仍然可以优化成常数条指令。思路很像归并排序的逆过程：先把相邻的 1 位交换，再交换相邻的 2 位，再交换相邻的 4 位，然后是 8 位，最后交换前后 16 位。
public int reverseBits(int n) { n = ((n & 0x55555555) << 1) | ((n >>> 1) & 0x55555555); n = ((n & 0x33333333) << 2) | ((n >>> 2) & 0x33333333); n = ((n & 0x0F0F0F0F) << 4) | ((n >>> 4) & 0x0F0F0F0F); n = ((n & 0x00FF00FF) << 8) | ((n >>> 8) & 0x00FF00FF); return (n << 16) | (n >>> 16); }要理解它，重点看第一行：0x55555555的二进制是01010101...，偶数位是 1，奇数位是 0。(n & 0x55555555) << 1把偶数位的 1 左移到奇数位；(n >>> 1) & 0x55555555把奇数位的 1 右移到偶数位。两半拼起来，相邻两位就完成了交换。后面每行把块大小翻倍，逻辑完全一样。最终经过 5 轮，整个 32 位就逆序了。
这个写法第一次看会觉得很烧脑，但它其实是很多底层优化库里的标准套路，例如 CPU 指令集优化、Z-order 曲线映射等场景。面试时能写出来是加分项，但前提是先把逐位法写对，否则容易因一个小掩码错误陷入调试泥潭。
4.4 现场怎么选：先稳后快
我个人面试答题的顺序建议是：先快速给出逐位翻转版本，确认边界条件，让代码跑通；如果面试官追问“能不能更快”，再升级到分治交换。直接上手分治的问题在于，那 5 行掩码一旦有一个数字写错，整个结果就乱了，而且很难一眼定位错误。先把正确的基线版本放在那儿，心理压力会小很多，优化时也更从容。LeetCode 的测试用例里，逐位翻转完全够用，没必要一开始就追求炫技。
5. 371. 两整数之和：用加法器思路解掉“禁用加法”
5.1 半加器核心：异或是不进位加法，与是进位标记
这道题要求不用加法运算符实现两数相加。听起来很魔幻，但如果从数字电路底层看，加法本来就是用异或和与运算拼出来的。
两个二进制位相加的结果有两部分：本位和进位。a ^ b能算出不考虑进位的“本位和”，因为异或的规则是相同为 0、不同为 1，恰好对应 0+0=0、0+1=1、1+0=1、1+1=0。那 1+1 产生的进位去哪里了？就是a & b，只有两个都是 1 时才会进位。进位还要向左移动一位，因为二进制里要向高一位进 1，所以完整公式是：
- 本位和：
a ^ b - 进位：
(a & b) << 1
然后用这个进位继续和本位和相加，直到进位变成 0。可以把它想象成做竖式加法：先算当前位，再把进位加到上一位，反复迭代。
5.2 Java 场景的循环实现
Java 版本很干净，因为int本身就是 32 位补码，负数也天然兼容这个逻辑。
public int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a = a ^ b; b = carry; } return a; }每次循环里，a被更新为无进位和，b被更新为进位。当进位为 0 时，加法完成。负数为什么没问题？比如-1 + 1，在 32 位补码下就是0xFFFFFFFF ^ 0x00000001得到 0，进位也是 0，直接返回 0。这正好说明补码设计有多优雅，加法和减法在底层共用一套电路。
5.3 Python 的 32 位补码模拟
Python 版本麻烦在整数无限长。负数左移会产生无穷无尽的进位位，循环永远不会停。解决思路是强行把整数限制在 32 位范围内：每一步都做& 0xFFFFFFFF。
class Solution: def getSum(self, a: int, b: int) -> int: MASK = 0xFFFFFFFF a &= MASK b &= MASK while b: carry = ((a & b) << 1) & MASK a = (a ^ b) & MASK b = carry if a > 0x7FFFFFFF: return ~(a ^ MASK) return a最后那个if是把 32 位无符号表示还原成 Python 有符号整数。当结果大于0x7FFFFFFF时，说明最高位是 1，按 32 位补码来看它是个负数。~(a ^ MASK)的作用是：先对低 32 位取反得到补码的绝对值减一，再整体取反恢复成 Python 里的负数。这段逻辑会绕一点，我的个人技巧是拿0xFFFFFFFF当作 -1 的模拟值，亲手在纸上走一遍-1 + 1，马上就能理解。
5.4 面试追问图谱：负数、递归、无符号
这道题特别容易被追问。面试官通常会在你写完循环版后接着问：
- 负数怎么处理？Java 直接依赖补码；Python 靠掩码模拟 32 位。
- 循环为什么一定会终止？因为进位每次左移一位，最多 32 次后就变成 0。
- 能不能用递归写？可以，但 Java 没有尾递归优化，递归过深可能栈溢出，循环更稳。
- 减法怎么做？加法是
add(a, ~b + 1)，补码的本质就是用加法统一加减法。
如果这些追问都能答上来，这道题基本就拿满分了。我个人还建议自己私下扩展一下：用位运算实现乘法、判断两个数符号是否相同。这些扩展题能帮你把异或和与的性质用得更熟。
6. 四道题串成一张考点地图
6.1 每道题钉住一个位运算性质
做完这四道题，回头看会发现它们各自主打一个核心性质，合起来正好是一张位运算考点地图。
| 题号 | 核心性质 | 一句话方法论 |
|---|---|---|
| 191 | x & (x - 1)消除最低位的 1 | 统计消耗 1 的次数 |
| 231 | 2 的幂只有一个 1 | n & (n - 1) == 0或n & -n == n |
| 190 | 位与位之间可以并行交换 | 逐位翻转是基线，分治交换是优化 |
| 371 | a ^ b不含进位和，(a & b) << 1是进位 | 循环合并直到进位为 0 |
另外还隐藏了两条贯穿始终的线索：x ^ x = 0可以用来找出现一次的元素，x & -x可以提取最低位的 1。这两条线索分别通到 LeetCode 136（只出现一次的数字）和树状数组的 lowbit 操作，以后碰到相关题目会非常敏感。
6.2 复习顺序与扩展题清单
这四道题我建议按 231 -> 191 -> 190 -> 371 的顺序刷。231 是热身，用一行位运算找到感觉；191 开始引入循环和计数；190 升级到分治；371 挑战加法器思维。每一题都比前一题多一点复杂度，但知识是连贯的。
扩展题可以继续加：136 只出现一次的数字、268 丢失的数字、338 比特位计数、342 4的幂。这些题用到的性质基本都能在本文这四题里找到影子。复习的时候，我强烈建议隔几天用另一门语言重写一遍，特别是 371，Java 版和 Python 版的味道完全不同，这种语言差异本身就是对位运算理解的检验。
7. 高频翻车点与自查清单
7.1 常见问题速查表
刷题和面试里，有些错误出现频率高得惊人。我把它们整理成一张速查表，遇到症状直接查原因和修法。
| 症状 | 原因 | 处理办法 |
|---|---|---|
| 负数统计 1 时死循环 | 用了>>，负数高位补 1 | 改用>>>无符号右移 |
| Python 写 371 时死循环 | 整数无限长，进位左移无穷无尽 | 全程& 0xFFFFFFFF模拟 32 位 |
| JavaScript 下结果变负数 | 位运算默认转 32 位有符号整数 | 结果用>>> 0转回无符号视角 |
| 231 判断 0 返回 true | 忘了n > 0条件 | 必须同时保证正数 |
| 字符串翻转时结果不对 | 前导零没有补齐 32 位 | 先补零再翻转，或者干脆不用字符串法 |
| 190 分治有一行出错 | 掩码写错位宽 | 先用逐位法作基线，再逐步替换 |
7.2 提交前必跑的特例
实践经验告诉我，位运算题在提交前一定要跑几个固定特例：0、1、-1、2147483647、-2147483648。0 和 1 看似简单，却能验证边界条件；-1 全是 1，能检测右移类型和取位逻辑；2147483647 是最大正数，验证高位是否被正确处理；-2147483648 只有最高位是 1，专门用来测试分治交换和符号处理。这四个值跑通了，绝大多数隐含错误都会现原形。
我个人刷完这四题的体会是：位运算考的不是记忆力，而是你对整数底层的敏感度。第一次写 371 的 Python 版时，我也在最后的符号还原那里卡了大半个小时，后来把所有数都按 32 位无符号视角画一遍，思路立刻清晰了。最后建议你别急着背最终代码，按我上面的顺序把每种解法手写一遍，遇到奇怪结果就把数字打印成十六进制观察规律。等你能一眼看出12 & -12 == 4、并且想清楚为什么的时候，这四道题就算真正吃透了。
