核心思路是将加法拆分为无进位相加与进位处理两步:a^b得无进位和,(a&b)

核心思路是把加法拆成两个独立步骤:先算每位相加但不进位的结果,再单独处理进位,然后把这两部分继续相加——直到进位为 0。
异或运算得到无进位和
二进制中,相同位相加不进位的规律正好对应异或(^):
- 0 ^ 0 = 0 → 0 + 0 = 0
- 0 ^ 1 = 1 → 0 + 1 = 1
- 1 ^ 0 = 1 → 1 + 0 = 1
- 1 ^ 1 = 0 → 1 + 1 = 0(进位 1,本位为 0)
所以 a ^ b 就是忽略所有进位时的加法结果。
与运算加左移得到进位值
只有两个位都是 1 时才产生进位,这由按位与(&)捕获:
- 1 & 1 = 1 → 这一位要进位
- 其他组合结果为 0 → 不进位
进位要加到高位,所以把 (a & b) 作为本轮进位值。比如 0b11 & 0b11 = 0b11,左移后变成 0b110,表示向高两位进位。
循环或递归合并两部分
把上一步的“无进位和”当作新 a,“进位值”当作新 b,重复前两步:
- 若用循环:当 b 变为 0 时停止,此时 a 就是最终和
- 若用递归:b == 0 时返回 a;否则调用 add(a ^ b, (unsigned int)(a & b)
注意:C/C++ 中对负数做左移可能未定义,建议转为 unsigned int 再移位,避免运行时异常。
支持负数的关键在补码
该方法天然支持负数,因为现代计算机用补码表示整数。补码下,加法电路逻辑统一,异或和与运算仍保持数学一致性。例如:
- 5 的补码(8 位):00000101
- -3 的补码(8 位):11111101
- 两者异或得 11111000,与运算后左移得 00000100,继续迭代可得 2 的补码 00000010
整个过程完全不依赖符号位判断,靠底层位操作自然收敛。


















