1. 题目分析与位运算设计思路1.1 这道题到底在考什么LeetCode 371题“两整数之和”我估计凡是刷过题的人都见过。题目本身一句话就能说完不能用加号“”和减号“-”实现两个整数相加的函数。很多人第一次看到这道题时觉得挺玄乎心想“不让用加号那还能怎么加”实际上它考的不是什么奇技淫巧而是计算机底层加法器的实现原理。计算机里的所有整数运算最终都是通过二进制完成的。我们在教科书上学的加法竖式放到电路里就是一套固定的逻辑门组合半加器负责处理一位加法全加器负责处理带进位的加法。LC371这道题本质上是让你用软件把这一套硬件逻辑重新实现一遍。掌握了这道题你不仅仅是在LeetCode上多拿下一道题而是把这几件事一次打通了异或运算模2加法的本质到底是什么进位是怎么产生、怎么向前传播的位运算里的无进位加法和进位信息如何配合有符号整数在C语言里做位运算时那些刁钻的坑所以这道题适合三类人正在刷题准备面试的求职者、在学习计算机组成原理或C语言的在校生以及虽然工作多年但一直对位运算“一知半解”的开发者。1.2 加法的二进制本质拆解我们先回到最底层的加法逻辑。假设有两串二进制数做逐位加法时某一位上有三种情况两个都是0结果位是0不产生进位一个是0一个是1结果位是1不产生进位两个都是1结果位是0产生进位1向高位移送。这个逻辑如果用逻辑门去描述结果位就是两个比特的异或相同为0不同为1。进位位就是两个比特的与只有两个都是1时才进位。这个结论是整道题的根基。把每一位的结果和进位分开看我们可以得到一个重要思路两个整数相加的结果 两个整数逐位异或的结果 进位信息左移一位后的结果。因为进位是向更高的一位传播的所以“先算出哪些位置需要进位”然后把进位的结果左移一位再和“无进位加法的结果”继续相加直到不再有进位为止。这里我打个比方。想象你在手算两位数加法比如17 18。个位上7加8等于15写5进1十位上1加1再加进位1等于3结果是35。如果用位运算的思路理解就是先算个位的“无进位和”得到5再算“进位值”得到10因为个位的进位实际是向十位进的1也就是数值上的10两者相加15得到的是7加8的结果。然后再把这15和十位上的10继续做同样的处理直到进位为0。这个“反复拆解、直到进位消失”的过程就是LC371的核心算法框架。你不需要一次算完只需要不断重复两步算无进位和算进位然后继续下一次迭代。2. 核心实现与代码推导2.1 迭代实现从直观到代码先上最常规的迭代版本以C语言为例int getSum(int a, int b) { while (b ! 0) { int carry ((unsigned int)(a b)) 1; a a ^ b; b carry; } return a; }这里面有两个关键操作a ^ b算的是无进位加法的结果(a b) 1算的是进位信息左移一位后的值。while循环的条件是b ! 0也就是“还有进位需要处理”就不再停。为什么这短短几行代码能处理任意整数因为每一次循环b进位值的最高有效位至少会左移一位也就是说进位的二进制表示里最低位的那个1会不断往高位移动。同时由于数值的二进制位是有限的进位最终必然会变为0循环就终止了。我举个例子手动验证一下算 5 3也就是二进制 101 011。初始a 101b 011a b 001左移一位得到 010这是进位信息a ^ b 110无进位和为 110把结果赋值a 110b 010第二次循环a b 010左移一位得到 100a ^ b 100无进位和为 100赋值a 100b 100第三次循环a b 100左移一位得到 1000a ^ b 000无进位和为 000赋值a 000b 1000第四次循环a b 0a ^ b 1000赋值a 1000b 0循环结束返回 a 8计算过程可能看起来啰嗦但电脑执行这几次循环的时间远比你想象中短。实际测试中不论数字多大循环次数不会超过整数类型的位数加一也就是32次左右。2.2 递归实现把迭代优雅化理解了迭代写法之后递归写法就完全顺理成章了。递归的本质和迭代一样只是把要重复的计算变成了函数调用int getSum(int a, int b) { return b 0 ? a : getSum(a ^ b, ((unsigned int)(a b)) 1); }这里有个比较有意思的点递归的方式在代码上更简洁但在某些编译器上可能因为递归调用产生额外的栈开销。LeetCode上两种写法都能过但实际项目里我更推荐迭代版本原因后面讲C语言UB问题时会提到。递归版本的退出条件是b 0和迭代版本完全对应。每次调用时第一个参数变成无进位和第二个参数变成进位左移的结果参数的含义始终清晰。这种写法的好处是逻辑和数学定义一一对应读代码的人很容易通过“无进位和 进位”这个框架理解它。2.3 为什么递归/循环一定会终止有一些朋友可能会担心一个问题万一进位信息一直不为0程序不就死循环了吗这个担心是多余的前提是我们处理的是固定位宽的整数。假设你是32位整数初始时进位信息a b的二进制表示中最高的1所在位置假设是第k位。左移一位之后这个最高的1一定会出现在第k1位或者更高位。也就是说carry的“有效位范围”在每次循环中都会严格向高位移动至少一位。当这个位置超出32位整数的表示范围时进位不管是被截断还是被舍弃都会变成0。因此循环必然在有限次数内结束最坏情况下不超过32次。这个性质和C语言的类型体系紧密相关如果是固定位宽的无符号整数左移导致的超出位宽的1会被“截断”也就是丢弃如果是有符号整数情况复杂一点下一节专门讲。3. C语言中有符号整数与无符号整数的位运算专题3.1 有符号整数右移左移的未定义行为我把这个专题单独作为一个大章节来写因为这是我实际编码中踩过坑、也在很多人的代码评审里见过的问题。C语言标准规定对有符号整数进行“左移操作”时如果左移导致符号位发生变化或者把1移到了符号位这个行为是未定义的。更严格地说对有符号整数的右移操作如果被移入的是符号位具体是算术移位还是逻辑移位是由实现定义的。我简化一下你只需要记住一个核心结论千万不要对有符号负数做左移操作也别指望右移负数时的行为在所有编译器上一致。回到LC371这道题如果直接写(a b) 1当a和b都是负数时a b的结果是有符号的负数对这个负数做左移在某些条件下就触发了未定义行为。你可能在自己的机器上跑得好好的但换一个编译平台、换一个优化等级结果可能就不同了。这类bug在面试时不容易暴露但在真实工程里是定时炸弹。所以正确做法是先把a b转换成无符号整数再进行左移。无符号整数的左移是明确定义的移出去的位直接丢弃不会触发任何UB。这就是代码里((unsigned int)(a b)) 1的由来。3.2 为什么转换成无符号整数后负数也能正确相加这个问题如果没想透你会觉得代码是在“碰运气”。其实补码表示在这里扮演了关键角色。现代计算机处理有符号整数几乎都用补码表示。对于一个负数比如 -2在32位整数下它的二进制补码表示是 0xFFFFFFFE。它的每一位和正整数在形式上没有特别之处按位异或、按位与都是定义良好的操作。我们把a和b当作无符号整数做运算时只是在“怎么解释这串比特”上做了切换不会改变底层的比特内容。加法过程中的进位传播、位与、位异或全部只和比特位有关和整数的“正负符号”无关。所以用无符号类型完成进位计算后再通过赋值回到int比特内容不变最终结果就是正确的有符号值。你可以这么理解补码的存在让“减法和加法”在二进制层面是统一的。正数和负数的加法在比特层面就是普通二进制加法进位规则完全一致。唯一不同之处在于我们如何解释最高位当成符号位还是数值位。位运算本身不关心解释方式所以用无符号类型做中间计算完全可行。3.3 编译器优化与UB的实际影响有些人不重视UB觉得“反正我跑起来结果是对的”。我给你展示一个实际发生过的情况。假设你写了一个未转类型的版本int getSum(int a, int b) { while (b ! 0) { int carry (a b) 1; a a ^ b; b carry; } return a; }在某款编译器加上-O2优化后编译器可能认为“对有符号整数左移未定义所以我直接假设这段代码不会被执行到”从而做出激进的优化把整个循环优化掉或者生成一个完全不符合你预期的结果。调试时你可能花好几个小时也找不到原因因为你单步执行时程序又表现正常。这绝不是危言耸听C语言历史上很多严重漏洞都源于未定义行为的滥用。所以在LC371的实现中((unsigned int)(a b)) 1不是“画蛇添足”而是严谨性的体现。面试时如果你能主动讲出这一点会让面试官觉得你不是背题而是真的理解底层机制。4. 常见问题与排查技巧实录4.1 循环无法终止的问题我在帮别人看代码时遇到过一个问题有人写的版本是这样的int getSum(int a, int b) { while (b) { int carry (a b) 1; a ^ b; b carry; } return a; }在LeetCode的测试数据下这段代码基本都能过。但换到某些平台上特别是当a和b都是某些特定负数组合时carry有可能变成一个负数左移后在某些编译器上触发未定义行为继而导致循环无法按预期收敛。排查方法是打印每一步的a和b的值观察 carry 是否持续向高位移动。如果某一步之后 carry的二进制表示不再“变干净”先检查类型转换。另外如果题目平台从32位换到64位整数carry可能不会在预期次数内变成0。比如long long类型时循环次数会相应增加代码逻辑不变但要注意类型转换时统一用unsigned long long。4.2 超出有效位后被截断的正确理解有人会问如果进位左移后溢出了那个被丢弃的1是不是就丢了会不会导致结果错答案是不会。这里要理解一个关键点两个n位二进制数的和最多只需要n1位来表示。如果两个数都是无符号整数且超出了取值范围那属于溢出结果本来就不在类型能表示的范围内。在LC371里题目并没有要求处理溢出后的正确结果LeetCode的测试数据也都在int能表示的范围内。所以进位溢出被截断是合理的它表示“加法结果不需要考虑这个更高位的进位了”。假如你真的需要处理溢出的完整结果那就得用更大的位宽来保存进位比如把两个int的和存到long long里。但那是另一个话题了LC371的框架下不需要。4.3 调试位运算的几个实用技巧我在调试这类算法题时会用几个小技巧分享给大家用十六进制打印中间值比二进制好看。例如printf(%x %x\n, a, b);手动把测试用例拆成小二进制数在纸上推导。比如测试 -2 3写成补码形式 0xFFFFFFFE 0x00000003走一遍异或和进位就能看出负数运算的奥妙。用单元测试覆盖边界0 00x7FFFFFFF 1-1 -1INT_MAX INT_MIN。这些边界用例能暴露大多数实现问题。另外提醒一句LeetCode上有的语言比如Python里整数是无限精度的不存在固定位宽的截断所以实现会略有不同。如果你用Python做这题需要手动用掩码0xFFFFFFFF模拟32位无符号整数的截断行为否则b可能永远不为0。这也是为什么网上很多Python版本的LC371代码写起来比C/C版本“脏”一些的原因。5. 位运算在实际开发中的进一步应用5.1 从LC371到减法、乘法LC371的框架不仅适用于加法稍微改造一下就能实现减法和乘法。减法可以通过a - b a (~b 1)实现也就是先对b取反加一得到相反数再调用加法逻辑。乘法本质上就是重复加法和移位参考二进制竖式乘法每次判断b的最低位是否为1是则把a加到结果中然后把a左移一位、b右移一位。我在这里写一个基于LC371思想的乘法实现int multiply(int a, int b) { int result 0; unsigned int x a 0 ? -a : a; unsigned int y b 0 ? -b : b; while (y) { if (y 1) { result getSum(result, x); } x 1; y 1; } return (a 0) ^ (b 0) ? -result : result; }这只是一个示例实际有更精巧的写法但核心思想仍然是“拆解为位操作”。建议你在理解了加法实现后自己动手试试减法你会发现思路瞬间打开了。5.2 树状数组、状态压缩和位运算的其他经典场景位运算在工程里最常见的一个场景是树状数组英文叫Binary Indexed Tree。它通过lowbit操作——也就是取一个整数二进制表示中最右侧的1——来实现高效的单点更新和区间查询。lowbit(x) x (-x)这个公式本质上也依赖补码表示和位与运算和LC371用的是同一块知识基础。另一个高频场景是状态压缩DP。当你需要表示一组物品的选或不选时用一个整数的各个二进制位来存储状态是最节省空间的方案。比如旅行商问题里dp[mask][i]表示已经访问过的城市集合为mask时当前在城市i的最小花费mask就是一个位运算操作频繁的状态表示。字节序处理、权限系统、哈希函数、布隆过滤器这些通通离不开位运算。掌握LC371不仅仅是为了刷题更是为将来阅读底层代码、理解标准库实现打基础。5.3 常见的位运算速查技巧最后整理一个我在开发中实际用到的位运算技巧清单判断奇偶x 1比x % 2通常更快乘以2的幂x n除以2的幂x n但需要注意负数时行为差异取绝对值(x ^ (x 31)) - (x 31)一个经典位运算技巧判断是否为2的幂x 0 (x (x - 1)) 0交换两个变量不需要临时变量a ^ b; b ^ a; a ^ b;这些技巧不代表每一条都比普通写法好但理解其原理后你在读别人代码时不会发懵也有助于在面试时展示出你对底层细节的敏感度。LC371就是一个非常好的起点通过它建立的“加法异或进位”“进位会不断左移直到消失”的思维模型能让后续所有位运算相关的学习事半功倍。
