不用加号如何实现两数之和？（LeetCode 371）

简化版

不使用 +、- 运算符，实现两个整数相加。核心思想来自二进制加法：异或 a ^ b 是「无进位相加」（每一位相加不进位的结果），与再左移 (a & b) << 1 是「进位」（两个 1 相加才产生进位，进到高一位）。把「无进位和」与「进位」反复相加，直到进位为 0，此时的无进位和就是答案。用循环模拟这个过程。

详细版

int getSum(int a, int b) {
    while (b != 0) {                 // b 存放进位，进位为 0 时结束
        int carry = (a & b) << 1;    // 进位：两个 1 相加进到高位
        a = a ^ b;                   // 无进位和：异或
        b = carry;                   // 把进位当作新的 b 继续加
    }
    return a;
}

a ^ b：无进位相加（0+0=0, 1+0=1, 1+1=0 不管进位）——正是异或。
(a & b) << 1：进位——只有两位都是 1（a & b）才进位，进位要左移一位加到高位。
循环：把无进位和与进位继续相加，直到没有进位（b == 0）。
复杂度：O(1)（最多循环 32 次，位数上限）。

完整版教学

一、回到二进制加法的本质

想想小学列竖式加法：每一位相加，得到「本位数字」和「向前的进位」。二进制也一样，只是每位只有 0/1。考察一位相加的四种情况：

a 位	b 位	本位（无进位和）	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察这两列：

「本位」列恰好是 a XOR b（相同为 0、不同为 1）——这就是无进位相加。
「进位」列恰好是 a AND b（都为 1 才 1）——这就是进位，而进位要作用到高一位，所以要 << 1。

这正是数字电路里的半加器/全加器逻辑。

二、把「和 + 进位」反复迭代

一次异或和一次与移位，得到了「无进位和 a^b」和「进位 (a&b)<<1」。但真正的和 = 无进位和 + 进位——又是一个加法！不能用 +，怎么办？把它俩当作新的两个数，重复同样的过程：

新的 a = a ^ b（无进位和）；
新的 b = (a & b) << 1（进位）；
继续循环。

每一轮，进位会往高位移动、逐渐「消化」。因为整数位数有限（32 位），进位最多传播 32 次就会变成 0。当 b（进位）为 0 时，a 就是最终的和，返回它。

三、走一遍例子：5 + 3

a = 5 = 101，b = 3 = 011：

carry = (101 & 011) << 1 = 001 << 1 = 010；a = 101 ^ 011 = 110；b = 010。
carry = (110 & 010) << 1 = 010 << 1 = 100；a = 110 ^ 010 = 100；b = 100。
carry = (100 & 100) << 1 = 100 << 1 = 1000；a = 100 ^ 100 = 000；b = 1000。
carry = (000 & 1000) << 1 = 0；a = 000 ^ 1000 = 1000 = 8；b = 0 → 结束。

返回 a = 8。✔ 5 + 3 = 8。

四、负数为什么也对

用补码表示时，加法对有符号数和无符号数是统一的——a ^ b 和 (a & b) << 1 这套逻辑不区分符号，补码天然处理负数和溢出回绕。所以 getSum(-2, 3)、getSum(-1, -1) 都能正确得到结果，不需要特殊处理符号位。（在 Java 中溢出按 32 位回绕，与普通 + 行为一致。）

五、易错点

循环条件是 b != 0（进位没消完就继续），不是 a != 0。
进位要 << 1：a & b 得到的是「哪些位产生进位」，进位作用在高一位，必须左移。忘了左移是最常见错误。
赋值顺序：要先用旧的 a、b 算出 carry，再更新 a。代码里 carry 先算好、a = a^b、b = carry，顺序不能乱（若先改 a 再算 carry 就用错了值）。
减法：a - b = a + (-b)，而 -b = ~b + 1（也可用本方法实现），所以减法能转化成本题。

六、用“无进位和 + 进位”验证加法

对每一位，a^b 给出忽略进位的和，(a&b)<<1 给出应该加到高一位的进位。二者相加仍可能产生新进位，所以重复同一分解，直到 carry 为 0。循环不是近似过程；每一轮都保持数学上 a+b 的位模式总和不变。

计算 5 + 3：a=0101, b=0011
轮 1 sum=0110, carry=0010
令 a=0110, b=0010
轮 2 sum=0100, carry=0100
令 a=0100, b=0100
轮 3 sum=0000, carry=1000
轮 4 sum=1000, carry=0000，结果 8

校验维度	本题必须保持的结论
循环/递推不变量	在固定字宽模 `2^w` 意义下，新 a 与新 b 的和等于旧 a 与旧 b 的和。
边界条件	Java int 溢出本就按低 32 位补码保留，算法与普通 int 加法的溢出语义一致。
复杂度与代价	进位每轮向更高位移动，32 位 int 最多 32 轮，时间和空间均 O(1)。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

位运算题的代码通常很短，真正容易错的是把数学整数、固定宽度位模式和语言移位规则混在一起。本题应先复述这条不变量：在固定字宽模 2^w 意义下，新 a 与新 b 的和等于旧 a 与旧 b 的和。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“计算 5 + 3：a=0101, b=0011”开始手推，最后应得到“轮 4 sum=1000, carry=0000，结果 8”。
边界复核：Java int 溢出本就按低 32 位补码保留，算法与普通 int 加法的溢出语义一致。
代价复核：进位每轮向更高位移动，32 位 int 最多 32 轮，时间和空间均 O(1)。
用全 0、只有一个 1、最高位为 1 三类位模式检查掩码。
涉及负数时把值写成固定宽度补码，确认使用 >> 还是 >>>。
涉及左移时检查移位距离和溢出后是否仍符合题目的位模式语义。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“在固定字宽模 2^w 意义下，新 a 与新 b 的和等于旧 a 与旧 b 的和。”这条正确性主线不能省。

八、常见误区与追问

误区：异或本身就是加法。 异或只表示无进位和；同为 1 的位置必须通过 (a&b)<<1 生成进位。
误区：只计算一轮 xor 和 carry 就结束。 新产生的进位还可能与无进位和碰撞，需要迭代到 carry 为 0。
误区：负数必须先取绝对值。 补码加法对正负数使用同一套位规则，无需拆符号。
追问：为什么循环一定终止？ 固定 32 位下进位只会左移，超过最高位后被截断为 0。
追问：如何实现减法？ 可转成 a + (~b + 1)，其中加法仍由本题算法完成。
追问：算法会比 CPU 加法指令更快吗？ 不会；这是理解加法器和位语义的面试题，实际工程应直接使用 +。

九、加强记忆

不用 + 求两数之和 = 模拟二进制加法（全加器）：a ^ b 是无进位和（异或=不进位相加）、(a & b) << 1 是进位（都为 1 才进位、进到高位）。把「无进位和」与「进位」当新的两数反复相加，直到进位 b == 0，此时 a 即答案。补码让负数/溢出自动正确。牢记：进位必须 << 1、循环条件是进位不为 0、先算 carry 再更新 a。核心一句：异或管相加、与移位管进位，迭代到无进位。

简化版

详细版