LeetCode 面试题 17.01. 不用加号的加法

2026-03-28 HGNULB 约 8 分钟

文章信息 3 个分类 2 个标签

分类

题目描述

✅ 面试题 17.01. 不用加号的加法

题意分析

题目目标：给定两个 32 位有符号整数 a 和 b，返回它们的和，但整个过程中不允许使用 + 和 - 运算符。
核心约束：禁用加减法这条限制本身就是最强的信号——它把「求和」从一个原子操作变成了必须自己搭建的过程，剩下可用的只有位运算、比较和赋值，因此必然要回到硬件层面，用逻辑门的方式复现加法器。另一个信号是数据规模：题目保证结果落在 32 位有符号整数范围内，说明位数是常量，不存在大数问题，循环次数天然有上界。
边界处理：a 或 b 可能为负数，必须依赖补码表示让减法自动变成加法，不能对符号做特殊分支；某一方为 0 时应当立刻返回另一方；两数相加可能在中间步骤触碰到 Integer.MIN_VALUE 或产生高位溢出，需要确认语言的移位与溢出语义不会破坏结果；Go 的 int 是 64 位，与 Java 的 32 位 int 行为不同，但由于最终答案在 32 位范围内且补码运算逐位一致，两者收敛到同一个值。

解法：位运算模拟加法

核心思路

一个自然的念头是用循环把 b 一个一个地累加到 a 上（b 为负就反向），但这既用到了加减法本身，又需要 $O(|b|)$ 次迭代，在 b 取到 10^9 量级时完全不可行。瓶颈在于我们把加法当成了黑盒，只能一次挪一步。
换个角度：小学竖式加法其实分成两件事——每一位「不进位地相加」，以及把产生的进位挪到高一位再加回去。落到二进制上，这两件事各自都有现成的位运算表达。对某一位而言，两个比特不进位相加的结果恰好是异或：0+0=0、0+1=1、1+0=1、1+1=0（进位另算），这正是异或的真值表。而只有两个比特同时为 1 时才产生进位，这正是与运算；进位要作用到高一位，所以还要左移一位。
于是得到不变量：在循环的每一轮开始时，a + b 的真实值恒等于最初两个输入之和。每轮把 a 更新为 a ^ b（无进位和），把 b 更新为 (a & b) << 1（待处理的进位），这一步只是把同一个总和在两个变量之间重新分配，总和不变，不变量得以保持。循环的终止性来自另一个观察：进位每轮至少向左移动一位，最低位的 1 会不断被推向高位，最多 32 轮之后 b 必然被移空成 0。当 b 变成 0 时，「没有待处理的进位」，此时 a 就是完整的和。

解题步骤

第一步：以 b != 0 作为循环条件。 为什么盯着 b：b 在循环中承载的语义是「还没被吸收的进位」，它归零就等价于加法收敛。为什么不用固定 32 轮：多数情况下进位远早于 32 轮就消失，用条件判断可以提前退出；同时这个写法也天然覆盖了 b 初始就是 0 的情况——一次循环都不进，直接返回 a。

第二步：先算 sum = a ^ b，即不考虑任何进位时逐位相加的结果。 为什么异或就是无进位和：逐位看，异或在两位相同时给 0、不同时给 1，与二进制加法丢掉进位后的结果完全一致。为什么这一步必须用临时变量而不能直接赋给 a：下一行计算进位时还要用到 a 的旧值，先覆盖 a 会让进位算错。

第三步：算 carry = (a & b) << 1，得到本轮产生的全部进位。 为什么是与：只有两位都是 1 时才向上进位，与运算精确标出了所有这样的位置。为什么要左移一位：进位的价值属于更高一位，不左移就相当于把进位加回了原位。为什么负数的左移不会出问题：补码下的移位和加法都是模 2^32 的运算，符号位被当作普通比特参与，最终结果自动落在正确的补码表示上，因此不需要为负数写任何特判。

第四步：把 sum 赋给 a、carry 赋给 b，进入下一轮；循环结束后返回 a。 为什么返回 a 而不是别的：退出时 b 为 0，不变量说 a + b 等于答案，代入即得 a 就是答案。

以 a = 3, b = 5 走一遍。 二进制 a = 0011，b = 0101。第一轮：sum = 0011 ^ 0101 = 0110（十进制 6），carry = (0011 & 0101) << 1 = 0001 << 1 = 0010（十进制 2）；更新为 a = 6，b = 2。第二轮：sum = 0110 ^ 0010 = 0100（4），carry = (0110 & 0010) << 1 = 0010 << 1 = 0100（4）；更新为 a = 4，b = 4。第三轮：sum = 0100 ^ 0100 = 0000（0），carry = (0100 & 0100) << 1 = 0100 << 1 = 1000（8）；更新为 a = 0，b = 8。第四轮：sum = 0000 ^ 1000 = 1000（8），carry = (0000 & 1000) << 1 = 0；更新为 a = 8，b = 0。循环条件不再满足，返回 8，正是 3 + 5。注意每一轮 a 与 b 之和始终是 8，这就是不变量在起作用。再看一个带负数的例子 a = -2, b = 3：a 的补码是 …11111110，b 是 …00000011。第一轮 sum = ...11111101（-3），carry = (...11111110 & ...00000011) << 1 = 2 << 1 = 4；a = -3，b = 4。第二轮 sum = -3 ^ 4，-3 是 …11111101，异或 100 得 …11111001（-7），carry = (...11111101 & 100) << 1 = 4 << 1 = 8；a = -7，b = 8。第三轮 sum = -7 ^ 8：-7 是 …11111001，异或 1000 得 …11110001（-15），carry = (...11111001 & 1000) << 1 = 8 << 1 = 16；a = -15，b = 16。可以看出 a 与 b 之和恒为 1，进位持续左移，最终在符号位处被移出，b 归零，a 收敛到 1，正是 -2 + 3。

代码实现

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int sum = a ^ b;
            int carry = (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }
}

func add(a int, b int) int {
    for b != 0 {
        sum := a ^ b
        carry := (a & b) << 1
        a = sum
        b = carry
    }
    return a
}

复杂度分析

时间复杂度：$O(1)$。凭什么：每一轮循环内部只有常数次位运算，而进位每轮至少左移一位，32 位整数最多 32 轮就会把进位全部移出，循环次数有与输入无关的常量上界。

空间复杂度：$O(1)$。凭什么：全程只用了 sum、carry 两个标量以及原地复用的 a、b，没有递归栈、没有数组、没有随输入增长的容器。

关键点总结

遇到「禁用某个基础运算符」的题，思路应当立刻转向该运算的底层实现方式。加法的底层就是全加器：异或出本位、与出进位、左移送高位，这三件事凑齐就是一个完整的加法器。

「把总量在两个变量之间搬运、总量本身不变」是一类极好用的不变量设计。本题中 a + b 恒为答案，每轮只是把进位从 b 挪进 a，收敛条件自然就是 b 归零，正确性和终止性都能一句话讲清。

终止性论证要单独给出，不能只说「循环直到 b 为 0」。这里的依据是进位单调左移、位宽有限，因此最多 32 轮，这类「势函数严格下降」的论证在位运算和数值迭代题里通用。

补码让减法自动成立，因此不要为负数写特判。同理，减法 a - b 可以直接写成 add(a, ~b + 1)，理解这一点就理解了为什么这套逻辑不区分正负。

面试视角：这道题面试官期待的不是背诵三行代码，而是看你能不能从竖式加法推到位运算，并解释清楚「为什么一定会停」。常见追问有三个——如何用同一套框架做减法（取反加一）、为什么 Python 写这题需要额外掩码（整数无限精度导致负数进位永不移出，需要手动截断到 32 位）、以及能否改成递归写法（b == 0 ? a : add(a ^ b, (a & b) << 1)），提前想好这三问会显得准备充分。

易错点总结

错误写法：先写 a = a ^ b 再算 carry = (a & b) << 1。用例 a = 3, b = 5 → 第二行用的已经是新 a = 6，算出 carry = (6 & 5) « 1 = 8，与正确的 4 不符，最终返回 14 而非 8。

错误写法：忘记把进位左移，写成 carry = a & b。用例 a = 1, b = 1 → carry 恒为 1，a 恒为 0，循环永远不结束，直接超时。

错误写法：循环条件写成 while (a != 0)。用例 a = 0, b = 7 → 一次都不进循环，返回 a = 0，正确答案是 7。

错误写法：为负数加符号特判，比如 b < 0 时改走减法分支。用例 a = -2, b = 3 → 特判分支自己又要实现减法，逻辑绕回原点且极易在 Integer.MIN_VALUE 处取反溢出，得到错误的 -2147483648。

错误写法：用无符号右移或算术右移代替左移来传播进位。用例 a = 2, b = 2 → 进位往低位跑，结果收敛到 0 或 1 这样的小值，正确答案 4 拿不到。

错误写法：把两个变量的更新写成 a = a ^ b; b = (a & b) << 1; 却省掉临时变量，且顺序颠倒成先更新 b 再更新 a。用例 a = 3, b = 5 → b 用旧值算对了进位，但随后 a 用的是新 b，异或结果变成 6 ^ 4 = 2，返回值错成 2。

错误写法：在 Go 里为了「更安全」把变量声明成 uint。用例 a = -2, b = 3 → 负数无法直接赋给 uint，编译期报错或强转后返回 18446744073709551615 这类巨大值，而不是 1。

错误写法：循环写成固定 32 次但退出后返回 b。用例 a = 3, b = 5 → 退出时 b 已是 0，返回 0，正确答案 8 存在 a 里。

相似题目

题目	难度	考察点
剑指 Offer 65. 不用加减乘除做加法	简单	完全同构的题面，但常见于 Python 解答，需要额外掌握 32 位截断掩码的写法
29. 两数相除	中等	把禁用运算符的思路推到除法，需要用倍增减法并单独处理 MIN_VALUE 溢出
67. 二进制求和	简单	同样是二进制加法，但输入是字符串且长度不限，进位要靠字符逐位模拟而非位运算
415. 字符串相加	简单	十进制大数加法，重点从位运算技巧转为高精度进位与结果拼接
191. 位1的个数	简单	同一类位运算基本功，核心技巧是 `n & (n-1)` 逐个消去最低位的 1