LeetCode 371. 两整数之和
题目描述
题意分析
在实现中不使用加法和减法运算符，求两个整数的和。输入可能为负数，不能只处理无符号数或另按符号分类相加。
可以直接模拟二进制加法：先同时算出各位不考虑进位的结果，再把产生的进位继续合并。题目输入范围内的最终结果能够由普通整数保存。
解法：位运算模拟加法
核心思路
[!blue]
先只看同一位的两位相加：恰有一个
1时，本位为1且不进位；两个都是1时，本位变为0并向高一位进位；两个都是0时均为零。因此a ^ b同时给出所有位的无进位结果，a & b找出会产生进位的位置，再左移一位将进位送到应加入的高位。将
a视为当前无进位结果，b视为尚待合并的另一部分。每轮先从同一份旧值算出sum = a ^ b和carry = (a & b) << 1，再分别赋给a、b。新产生的进位还可能与高位已有的1冲突，所以需要重复，不能只做一轮。在固定 $w$ 位补码中，新旧两部分的总和始终模 $2^w$ 同余。中间值按有符号数解释时可能越过通常的数值范围，但保留下来的位模式仍然代表同一个加法结果。负数使用相同补码规则，因此无需单独的符号分支。
只要新进位非零，它最低的置位就比旧
b的最低置位至少高一位：按位与不会制造更低的1，随后左移又前进一位。固定宽度下最多传播 $w$ 轮，进位就会消失。此时b == 0，全部结果已经合并在a中，返回它即可。
解题步骤
- 只要
b != 0，先计算旧a、b的异或值并保存。- 再由旧值计算按位与左移后的进位，确保没有提前覆盖任何操作数。
- 用这两个临时值更新
a、b，继续处理进位。- 当
b == 0时返回a；若初始b就是零，无需进入循环。
代码实现
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)$。
关键点总结
[!green]
- 两个新值都必须来自旧状态。
- 进位属于下一位，需要左移。
- Java 与 Go 的整数位宽可能不同，按进位是否为零结束。
易错点总结
[!yellow]
- 先更新 a 再计算 carry：丢失旧的重合位。
- 进位不左移：产生的进位仍停在原位，没有按二进制位权加入高一位。
- 用 a 是否为零控制循环：零与非零数相加时可能提前结束。
- 固定只做少量轮次：长进位链可能尚未处理完。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 67. 二进制求和 | 简单 | 同样把每位的和与进位分开，本题通过异或和按位与直接并行处理机器字。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！