位运算实现加法
📌 定义
不使用 + 和 - 运算符，使用位运算实现两个整数的加法。
示例:
输入: a = 1, b = 2
输出: 3
输入: a = -1, b = 1
输出: 0
输入: a = 5, b = 7
输出: 12
核心思路
利用异或和与运算模拟二进制加法：
- 异或（XOR）：计算不考虑进位的和
- 与（AND）+ 左移：计算进位
- 重复：直到没有进位为止
示例: 5 + 7 = 12
二进制: 0101 + 0111 = 1100
步骤1:
不带进位的和: 0101 ^ 0111 = 0010
进位: (0101 & 0111) << 1 = 0101 << 1 = 1010
步骤2:
不带进位的和: 0010 ^ 1010 = 1000
进位: (0010 & 1010) << 1 = 0010 << 1 = 0100
步骤3:
不带进位的和: 1000 ^ 0100 = 1100
进位: (1000 & 0100) << 1 = 0000 << 1 = 0000
进位为0，结果: 1100 (12)
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 迭代法 | O(log n) | O(1) | 最多32次循环 |
| 递归法 | O(log n) | O(log n) | 递归栈空间 |
| 查表法 | O(1) | O(2^32) | 不现实 |
Go 代码
Go 实现
package main
import "fmt"
// 方法1: 迭代法
func getSum(a int, b int) int {
for b != 0 {
// 不带进位的和
sum := a ^ b
// 进位
carry := (a & b) << 1
a = sum
b = carry
}
return a
}
// 方法2: 递归法
func getSumRecursive(a int, b int) int {
if b == 0 {
return a
}
// 不带进位的和
sum := a ^ b
// 进位
carry := (a & b) << 1
return getSumRecursive(sum, carry)
}
// 方法3: 处理32位整数
func getSum32(a int32, b int32) int32 {
for b != 0 {
sum := a ^ b
carry := (a & b) << 1
a = sum
b = carry
}
return a
}
func main() {
testCases := [][2]int{
{1, 2},
{5, 7},
{-1, 1},
{10, 20},
}
for _, tc := range testCases {
a, b := tc[0], tc[1]
result := getSum(a, b)
fmt.Printf("%d + %d = %d\n", a, b, result)
}
}思路展开
二进制加法详解
半加器（不考虑进位输入）:
A | B | Sum | Carry
--|---|-----|------
0 | 0 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 1 | 0
1 | 1 | 0 | 1
观察:
Sum = A ^ B（异或）
Carry = A & B（与）
完整示例：5 + 7
a = 5 (0101)
b = 7 (0111)
=== 第1次迭代 ===
sum = 0101 ^ 0111 = 0010
carry = (0101 & 0111) << 1
= 0101 << 1
= 1010
a = 0010
b = 1010
=== 第2次迭代 ===
sum = 0010 ^ 1010 = 1000
carry = (0010 & 1010) << 1
= 0010 << 1
= 0100
a = 1000
b = 0100
=== 第3次迭代 ===
sum = 1000 ^ 0100 = 1100
carry = (1000 & 0100) << 1
= 0000 << 1
= 0000
a = 1100
b = 0000
=== 结束 ===
b = 0，返回 a = 1100 (12)
负数处理详解
Python中整数无限长度，需要模拟32位:
正数示例: 5
32位表示: 0000...0101
MASK后: 0000...0101
<= MAX_INT，直接返回
负数示例: -1 + 1
-1的32位补码: 1111...1111
1的32位: 0000...0001
第1次:
sum = 1111...1111 ^ 0000...0001 = 1111...1110
carry = (1111...1111 & 0000...0001) << 1
= 0000...0001 << 1
= 0000...0010
第2次:
sum = 1111...1110 ^ 0000...0010 = 1111...1100
carry = (1111...1110 & 0000...0010) << 1
= 0000...0010 << 1
= 0000...0100
...（继续直到carry=0）
最终结果: 0000...0000 (0)
经典题目
LeetCode 问题
- 两整数之和 - LeetCode 371
- 两数相减 - 使用加法实现减法
- 两数相乘 - 使用加法实现乘法
- 两数相除 - 使用减法实现除法
扩展问题
- 不使用乘除法实现乘法
- 位运算实现减法、乘法、除法
⚖️ 优缺点
优点
- ✅ 底层实现：理解计算机底层加法原理
- ✅ 无需运算符：满足特殊限制
- ✅ 性能好：位运算速度快
缺点
- ❌ 可读性差：不如直接使用+
- ❌ 负数复杂：需要特殊处理
- ❌ 溢出风险：需要小心处理
🎨 应用场景
💡 优化技巧
💡 为什么使用 XOR 和 AND？
数学证明:
二进制加法规则:
0 + 0 = 0 (和=0, 进位=0)
0 + 1 = 1 (和=1, 进位=0)
1 + 0 = 1 (和=1, 进位=0)
1 + 1 = 10 (和=0, 进位=1)
观察:
- 和的规律: 相同为0，不同为1 → XOR
- 进位的规律: 都为1时产生 → AND
验证:
A | B | A^B | A&B | (A&B)<<1
--|---|-----|-----|----------
0 | 0 | 0 | 0 | 0
0 | 1 | 1 | 0 | 0
1 | 0 | 1 | 0 | 0
1 | 1 | 0 | 1 | 10
完全符合二进制加法规则！