LeetCode 剑指 Offer 65. 不用加减乘除做加法
题目描述
题意分析
计算两个整数的和，但函数体中不能使用加、减、乘、除运算符。输入可能包含零和负数，不能只处理正整数。
二进制加法可以拆成两部分：各位先不考虑进位得到的结果，以及需要送往更高一位的进位。前者可以用异或计算，后者可以用按位与再左移计算，反复合并这两部分即可。
解法：异或求和，按位与求进位
核心思路
[!blue]
先看某一位的两个二进制数字：只有其中一个为
1时，本位结果是1，不会进位；两个都为1时，本位留下0，向高一位进1。因此a ^ b给出所有位不考虑进位的结果，a & b标记会产生进位的位置，再左移一位得到(a & b) << 1。两部分合起来始终等价于原来的加法，但无进位结果与进位还可能在某些位同时为
1，需要继续处理。每轮先用旧的a、b保存carry，再令a更新为异或结果、b更新为carry，把同一个问题转成“部分和与剩余进位相加”。当
b == 0，已经没有需要合并的进位，a就是结果。不能因为a == 0就停止，部分和为零时仍可能有尚未加入的进位；也不能先覆盖a再计算按位与，否则会丢失原来两个数同时为1的位置。Java 和 Go 的整数都有固定的位宽，负数以补码表示，位运算同样作用于所有二进制位。因此不需要单独区分正负，结果与对应固定宽度整数加法一致；超出最高位的进位按该位宽舍去。
每轮新的进位只能来自旧进位中的某些位再向左移动，不会向低位退回。只要进位还非零，它的最低有效位就会继续升高，最多经过一个字长的传播就会清零，因此循环能够结束。
解题步骤
- 只要
b非零，就继续合并两个操作数。- 先用旧值计算
carry = (a & b) << 1。- 更新
a = a ^ b，得到不含本轮进位的部分和。- 令
b = carry，下一轮只处理仍需加入的进位。- 当
b为零时返回a。
代码实现
class Solution {
public int add(int a, int b) {
while (b != 0) {
// 必须先用旧操作数保存进位，再覆盖无进位和
int carry = (a & b) << 1;
a ^= b;
// 下一轮第二操作数只表示仍需合并的进位
b = carry;
}
return a;
}
}
func add(a int, b int) int {
for b != 0 {
// 必须先用旧操作数保存进位，再覆盖无进位和
carry := (a & b) << 1
a ^= b
// 下一轮第二操作数只表示仍需合并的进位
b = carry
}
return a
}
复杂度分析
- 时间复杂度：$O(w)$，
w为整数位宽，每轮进位至少向更高位推进一次。Javaint为 32 位，Goint位宽由平台决定；固定字长下也可记作 $O(1)$。- 空间复杂度：$O(1)$，只使用一个进位变量，原操作数直接更新。
关键点总结
[!green]
- 先保存进位，不能读已被异或覆盖的旧值。
- 终止条件是进位零，不是部分和零。
易错点总结
[!yellow]
- 先更新异或结果再算进位：进位必须根据旧操作数中同时为
1的位置计算。- 按位与后不左移：进位应进入更高一位，留在原位置不符合二进制加法规则。
- 部分和为零时提前结束：是否完成取决于剩余进位，而不是当前部分和的值。
- 把负数当作无限长二进制处理：本实现依赖 Java/Go 固定位宽，符号位和最高位进位都遵循该位宽的规则。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 67. 二进制求和 | 简单 | 同样把每位的和与进位分开，本题通过异或和按位与直接并行处理机器字。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！