371. 两整数之和（Sum of Two Integers）

频次 ★★★ · 难度 🟡 · 高频：阿里

题目

不用 +、-，求两整数之和。

思路

位运算：a ^ b 是无进位和，(a & b) << 1 是进位。迭代直到进位为 0。

代码

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;   // 进位
        a = a ^ b;                  // 无进位和
        b = carry;
    }
    return a;
}

复杂度

• 时间：O(1)。每轮至少把进位往左推一位，32 位整数最多 32 轮
• 空间：O(1)

边界条件

• b == 0：直接返回 a，不进循环
• 负数：Java 的 int 是补码，异或和与运算天然对补码成立，不需要任何特判。这是补码表示最漂亮的性质——加法器不区分正负
• a + b 溢出：结果按 32 位截断，与 Java 的 + 行为一致（都是模 2
• a == Integer.MIN_VALUE 且 b == Integer.MIN_VALUE：结果为 0（溢出后），与 + 一致
• 循环必然终止：进位每轮左移一位，32 轮后必被移出

变式

• 不用 + 求两数之差：a - b == a + (-b) == a + (~b + 1)
• 不用 * 求乘积：把乘法拆成「移位 + 加法」，b 的每一位为 1 就累加对应左移后的 a——即竖式乘法
• 不用 / 求商：倍增减法（从高位试商），本质是二分
• 461. 汉明距离：同样用异或找出不同位，但不处理进位

易错点

• 别在 C++ 里照抄这段代码。C++ 中有符号整数的左移溢出是未定义行为，(a & b) << 1 在负数上会踩 UB，必须转成 unsigned 再算。Java 明确规定 int 溢出按补码截断，所以这段代码只在 Java 里天然安全
• a = a ^ b 必须在 carry 算完之后，否则 a 已被改写，carry 就错了。三行的顺序是绑死的
• 循环条件是 b != 0（进位为 0 才结束），不是 carry != 0——最后一次赋值 b = carry 之后才判
• 别写成递归 return b == 0 ? a : getSum(a ^ b, (a & b) << 1); 之后又忘了 Java 没有尾递归优化——虽然深度只有 32，无所谓，但要知道原因

面试追问

• 异或为什么是「无进位加法」：单看一位，0+0=0、0+1=1、1+0=1、1+1=0（进位另算）——这张真值表就是异或。加法 = 异或（本位）+ 与后左移（进位），把两部分反复相加直到没有进位，就是完整的加法。
• 这就是硬件加法器吗：是。这段循环是行波进位加法器（ripple-carry adder）的软件模拟，进位一位一位往上传。真实 CPU 用超前进位加法器（carry-lookahead）把进位并行算出来，把延迟从 O(位数) 降到 O(log 位数)。
• 为什么补码下不需要区分正负：补码的定义就是「模 2^n 意义下的加法」。-1 是 0xFFFFFFFF，-1 + 1 在模 2^32 下就是 0（进位溢出被丢弃）。符号位不是特殊位，它就是最高位，参与普通加法。 这正是补码取代原码/反码的理由。
• 面试里怎么快速验证：手算 getSum(3, 5)。3=011, 5=101 → xor=110(6)，carry=(001)<<1=010(2) → 下一轮 6^2=4，carry=(6&2)<<1=100(4) → 再一轮 4^4=0，carry=(4&4)<<1=1000(8) → 0^8=8，carry=0，返回 8。✓

关联题

• 同套路：136. 只出现一次的数字（异或的拓展应用）