LeetCode 371. 两整数之和
目录
题目描述
题意分析
题目目标：给定两个 32 位有符号整数 a 和 b，返回它们的和，但整个过程中不允许使用
+和-运算符。
核心约束：禁用加减法这条限制本身就是最强的信号——它把「求和」从一个原子操作变成了必须自己搭建的过程，剩下可用的只有位运算、比较和赋值，因此必然要回到硬件层面，用逻辑门的方式复现加法器。另一个信号是数据规模：题目保证结果落在 32 位有符号整数范围内，说明位数是常量，不存在大数问题，循环次数天然有上界。
边界处理：a 或 b 可能为负数，必须依赖补码表示让减法自动变成加法，不能对符号做特殊分支；某一方为 0 时应当立刻返回另一方；两数相加可能在中间步骤触碰到 Integer.MIN_VALUE 或产生高位溢出，需要确认语言的移位与溢出语义不会破坏结果；Go 的 int 是 64 位，与 Java 的 32 位 int 行为不同，但由于最终答案在 32 位范围内且补码运算逐位一致，两者收敛到同一个值。
解法：位运算模拟加法
核心思路
二进制加法可拆成两部分：
a ^ b得到不考虑进位的逐位和，(a & b) << 1得到待加入的进位。不断对这两部分重复相同过程，直到进位为 0。不变量：每轮开始时，当前两个变量按机器补码解释后的和，与原始输入之和相同。异或保留不进位部分，与后左移保留所有进位，因此一次更新只重新分配了总和。
终止性：进位的最低有效位每轮至少向高位移动一位；机器整数位宽有限，移出最高位后进位归零。Java 最多 32 轮，Go 最多为当前
int位宽轮数。正确性：循环结束时
b=0，不变量给出当前a就是原始两数之和。正负数都使用相同补码规则，无需符号分支。
解题步骤
- 当
b!=0时，同时基于旧值计算sum=a^b和carry=(a&b)<<1。- 用
sum替换a、carry替换b，继续处理剩余进位。b归零后返回a。
a=3,b=5的状态依次为(3,5) -> (6,2) -> (4,4) -> (0,8) -> (8,0)，最终返回 8。边界
a=-2,b=3依靠补码同样收敛到 1；若先覆盖a再计算进位，会丢失旧值并破坏结果。
代码实现
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int sum = a ^ b;
int carry = (a & b) << 1;
a = sum;
b = carry;
}
return a;
}
}
func getSum(a int, b int) int {
for b != 0 {
sum := a ^ b
carry := (a & b) << 1
a = sum
b = carry
}
return a
}
复杂度分析
- 时间复杂度：$O(w)$，
w为整数位宽；机器位宽固定，因此通常记为 $O(1)$。- 空间复杂度：$O(1)$。
关键点总结
- 异或计算无进位和，与运算后左移计算进位。
- 两个结果必须同时由旧的
a、b计算，因此要使用临时变量。b始终表示尚未合并的进位，归零就是终止条件。- 固定位宽补码让正数和负数使用同一套逻辑。
- Java 与 Go 的整数位宽可能不同，但循环上界都由各自固定位宽保证。
易错点总结
- 先更新
a再算进位：进位读取了新值，3+5会算错。- 忘记将
(a&b)左移：进位留在原位，1+1无法收敛。- 循环条件检查
a而不是b：0+7会直接错误返回 0。- 为负数单独分支：补码已经统一符号语义，额外分支更容易在最小整数处出错。
- Go 固定循环 32 次：
int可能是 64 位，应直接以进位是否为 0 作为条件。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 65. 不用加减乘除做加法 | 简单 | 完全同构的题面，但常见于 Python 解答，需要额外掌握 32 位截断掩码的写法 |
| 面试题 17.01. 不用加号的加法 | 简单 | 同样禁用加号，可顺带练习递归版本的位运算加法 |
| 29. 两数相除 | 中等 | 把禁用运算符的思路推到除法，需要用倍增减法并单独处理 MIN_VALUE 溢出 |
| 67. 二进制求和 | 简单 | 同样是二进制加法，但输入是字符串且长度不限，进位要靠字符逐位模拟而非位运算 |
| 415. 字符串相加 | 简单 | 十进制大数加法，重点从位运算技巧转为高精度进位与结果拼接 |
| 191. 位1的个数 | 简单 | 同一类位运算基本功，核心技巧是 n & (n-1) 逐个消去最低位的 1 |