之前在面试现场我问过一位候选人 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 变 11 变 0左移右边补 0相当于乘 2算术右移Java 中符号位填充相当于除以 2 取整无符号右移高位补 0Java 专属这里重点说补码。Java 的int是固定 32 位的负数以补码形式存储比如-1在 32 位视角下就是111...11132 个 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_popcountPython 用bin(n).count(1)也能实现。这些内置实现通常会查表或使用分治算法性能很高。但面试的时候不建议一开始就抛内置函数因为面试官想看的是你能否手写原理。比较稳妥的做法是先讲清楚 Kernighan 的原理然后补充一句“在工程上我会直接用内置方法因为它经过充分优化且可读性更好”。解法循环次数可读性适用场景逐位检查固定 32 次高面试兜底Kernighan1 的个数次高手写面试题、嵌入式内置 bitCount常数极高生产环境3. 231. 2 的幂一个二进制特征解决两种写法3.1 先分清边界0、负数、大数判断一个整数是不是 2 的幂看起来是数学题其实是二进制特征题。2 的幂在二进制里有一个明显的身份标识只有一个位是 1其他位全是 0。比如 1 是12 是104 是1008 是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二进制1000n - 1 0111相与得到0000返回 true。n 12二进制1100n - 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恰好对应 000、011、101、110。那 11 产生的进位去哪里了就是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 每道题钉住一个位运算性质做完这四道题回头看会发现它们各自主打一个核心性质合起来正好是一张位运算考点地图。题号核心性质一句话方法论191x (x - 1)消除最低位的 1统计消耗 1 的次数2312 的幂只有一个 1n (n - 1) 0或n -n n190位与位之间可以并行交换逐位翻转是基线分治交换是优化371a ^ 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的幂。这些题用到的性质基本都能在本文这四题里找到影子。复习的时候我强烈建议隔几天用另一门语言重写一遍特别是 371Java 版和 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、并且想清楚为什么的时候这四道题就算真正吃透了。