LeetCode 剑指 Offer 65. 不用加减乘除做加法
目录
题目描述
题意分析
给两个整数
a和b，要求返回它们的和，但四则运算符+、-、*、/全部禁用。换句话说，唯一可用的工具是赋值、比较和位操作，题目实质上是让你把「加法」这件事本身拆开重新实现一遍。约束透露的信号很明确：既然算术符号被封死，剩下的合法手段只有作用在二进制表示上的操作，那么解法必然要从「两个数的二进制位如何合成结果的二进制位」这个角度切入，而不是在数值层面绕弯（比如用数组下标、字符串拼接去模拟进位，这些写法既笨重又违背出题意图）。
取值范围是 $a, b \in [-1000, 1000]$，包含负数。这一点很关键：任何「先取绝对值、算完再补符号」的分支设计都会把代码撑得很长，而 Java 的
int与 Go 的int都以补码存储，负数在位层面和正数没有区别，说明存在一套统一处理正负的写法。边界情况：
a或b为 0 时应当直接返回另一个数；a与b互为相反数时结果为 0；一正一负相加时会发生大量高位借位，必须确认循环仍然会终止而不是死转。
解法：异或求和，按位与求进位
核心思路
二进制加法可以拆成两部分：
a ^ b：每一位只计算本位结果，不处理进位；(a & b) << 1：找出同时为1的位，并把进位送到高一位。因此，可把“
a与b相加”改写为“无进位和与进位相加”，反复执行，直到进位为0。循环不变量是：在固定字长的补码运算下，每轮的a与b之和都等于原始结果；当b == 0时，答案全部落在a中。正数、负数共用同一套逻辑，因为补码加法本来就是模 $2^w$ 的位运算。每轮进位都会向更高位移动，固定字长下最终会溢出边界并归零，所以循环一定结束。
解题步骤
- 当
b != 0时，说明还有进位需要合并。- 先计算
carry = (a & b) << 1，必须在覆盖a之前保存。- 用
a ^= b得到无进位和。- 令
b = carry，下一轮继续合并。- 进位清零后返回
a。例如
5 + 7：第一轮得到无进位和2、进位10；第二轮得到8和4；第三轮得到12和0，答案为12。
代码实现
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$ 为整数位宽；Java
int的 $w=32$，因此在本题中也可记为 $O(1)$。- 空间复杂度：$O(1)$，只使用一个进位变量。
关键点总结
- 异或对应“不进位加法”，按位与再左移对应“进位”。
- 循环退出条件是进位
b为零，而不是部分和a为零。- 固定字长补码让正负数可以统一处理，无需拆符号。
- 位运算顺序有依赖：必须先用旧的
a、b算出进位。
易错点总结
- 先更新
a再计算进位：会丢失原始位信息。- 忘记把
a & b左移一位：进位仍停留在原位。- 循环条件写成
a != 0 && b != 0：1 + 1第一轮的部分和为零，会提前退出。- 对负数取绝对值后分支处理：既多余，也容易在最小整数处溢出。
- 在 Python 中原样照搬：Python 整数没有固定字长，负数场景必须额外使用位宽掩码；Java、Go 无此问题。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 371. 两整数之和 | 中等 | 同一模板的英文版，值域更大，常被追问 Python 掩码写法 |
| 面试题 17.01. 不用加号的加法 | 简单 | 同一模板，但更常被要求给出递归而非迭代的形式 |
| 67. 二进制求和 | 简单 | 允许用算术符，改为在字符串上逐位模拟进位 |
| 415. 字符串相加 | 简单 | 十进制大数加法，进位是显式变量而非位运算副产物 |
| 43. 字符串相乘 | 中等 | 把乘法拆成错位相加，进位处理放在竖式的每一列 |
| 29. 两数相除 | 中等 | 禁用除号，改用倍增左移逼近商，边界在 INT_MIN 溢出 |
| 剑指 Offer 56 - I. 数组中数字出现的次数 | 中等 | 用异或的自反性消去成对元素，再按最低位 1 分组 |
| 191. 位1的个数 | 简单 | 考 n & (n - 1) 消最低位 1，与本题共享补码直觉 |