LeetCode 371中等位运算
两整数之和 图解题解
这道题到底在问什么
给两个整数 a、b，在不使用运算符 + 和 − 的情况下返回它们的和。
- 输入
- a = 23, b = 45
- 输出
- 68
最优解：一步一步想明白
- 3核心三句话：① 异或得到「不考虑进位时每一位的和」；② 与之后左移得到「该往高位进的 1」；③ 把进位不断加回去，没有进位时 a 就是答案。下面逐轮套这条规则。
- 4把 a=23、b=45 写成 7 位二进制（高位在左，不足补 0）。下面两行「无进位和」「进位」待算，整张表 4 行 × 7 列，维度从头到尾不变。
- 5第 1 轮开始。现在 a=23、b=45（紫色两行）。接下来逐位看：每一位上 a、b 的两个比特要做两件事——异或得本位、与得进位。
- 6异或 a^b：每一位「相同得 0、不同得 1」，这正是不考虑进位时该位的和。得到无进位和 = 0111010 = 58（绿色行）。但两个 1 相加该进位的事还没算。
- 7与 a&b：只有「两位都是 1」的位才得 1，那正是要进位的位（0000101）。进位要进到更高一位，所以左移一位 << 1，得进位 = 0001010 = 10（紫色行）。
- 8把无进位和与进位当成新的 a、b：a ← 58、b ← 10。进位还不是 0，说明还有 1 要往上进，回到第 2 轮继续加。
- 9第 2 轮开始。现在 a=58、b=10（紫色两行）。接下来逐位看：每一位上 a、b 的两个比特要做两件事——异或得本位、与得进位。
- 10异或 a^b：每一位「相同得 0、不同得 1」，这正是不考虑进位时该位的和。得到无进位和 = 0110000 = 48（绿色行）。但两个 1 相加该进位的事还没算。
- 11与 a&b：只有「两位都是 1」的位才得 1，那正是要进位的位（0001010）。进位要进到更高一位，所以左移一位 << 1，得进位 = 0010100 = 20（紫色行）。
- 12把无进位和与进位当成新的 a、b：a ← 48、b ← 20。进位还不是 0，说明还有 1 要往上进，回到第 3 轮继续加。
- 13第 3 轮开始。现在 a=48、b=20（紫色两行）。接下来逐位看：每一位上 a、b 的两个比特要做两件事——异或得本位、与得进位。
- 14异或 a^b：每一位「相同得 0、不同得 1」，这正是不考虑进位时该位的和。得到无进位和 = 0100100 = 36（绿色行）。但两个 1 相加该进位的事还没算。
- 15与 a&b：只有「两位都是 1」的位才得 1，那正是要进位的位（0010000）。进位要进到更高一位，所以左移一位 << 1，得进位 = 0100000 = 32（紫色行）。
- 16把无进位和与进位当成新的 a、b：a ← 36、b ← 32。进位还不是 0，说明还有 1 要往上进，回到第 4 轮继续加。
- 17第 4 轮开始。现在 a=36、b=32（紫色两行）。接下来逐位看：每一位上 a、b 的两个比特要做两件事——异或得本位、与得进位。
- 18异或 a^b：每一位「相同得 0、不同得 1」，这正是不考虑进位时该位的和。得到无进位和 = 0000100 = 4（绿色行）。但两个 1 相加该进位的事还没算。
- 19与 a&b：只有「两位都是 1」的位才得 1，那正是要进位的位（0100000）。进位要进到更高一位，所以左移一位 << 1，得进位 = 1000000 = 64（紫色行）。
- 20把无进位和与进位当成新的 a、b：a ← 4、b ← 64。进位还不是 0，说明还有 1 要往上进，回到第 5 轮继续加。
- 21第 5 轮开始。现在 a=4、b=64（紫色两行）。接下来逐位看：每一位上 a、b 的两个比特要做两件事——异或得本位、与得进位。
- 22异或 a^b：每一位「相同得 0、不同得 1」，这正是不考虑进位时该位的和。得到无进位和 = 1000100 = 68（绿色行）。但两个 1 相加该进位的事还没算。
- 23与 a&b：只有「两位都是 1」的位才得 1，那正是要进位的位（0000000）。进位要进到更高一位，所以左移一位 << 1，得进位 = 0000000 = 0（紫色行）。
- 24进位 = 0 了！没有要进的位，循环结束。此时 a = 68 = 1000100 就是最终答案。23 + 45 = 68。
- 25进位归零后 a 就是和：23 + 45 = 68。整个过程只用了异或 ^、与 &、左移 << 三种位运算，一次没用 +。
⚠️ 容易写错的地方
✗ 错：把进位忘了左移
✓ 对：进位是 (a & b) << 1，必须左移一位
进位天生要进到「更高一位」
✗ 错：循环条件写成 a != 0
✓ 对：应判 b（进位）是否为 0
没有进位才算加完，和留在 a 里
✗ 错：Python 不加掩码处理负数
✓ 对：32 位掩码 + 还原补码
Python 整数无限位长，负数补码需手动模拟
完整代码（Python / C++ / Java）
Python
def getSum(a, b):
mask = 0xFFFFFFFF
while b & mask:
a, b = a ^ b, (a & b) << 1
a &= mask
# 处理 Python 无限位长的负数补码
return a if a <= 0x7FFFFFFF else ~(a ^ mask)C++
int getSum(int a, int b){
while(b != 0){
unsigned carry = (unsigned)(a & b) << 1;
a = a ^ b;
b = (int)carry;
}
return a;
}Java
int getSum(int a, int b){
while(b != 0){
int carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}复杂度
时间
O(1)
32 位整数最多进位 32 轮，与输入大小无关
空间
O(1)
只用了几个临时变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两整数之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么异或就是「无进位的加法」？+
一位加法：0+0=0、0+1=1、1+0=1、1+1=10（本位 0，进位 1）。只看本位结果就是 0/1/1/0，正是异或；进位 1 出现在两位都是 1 时，正是与。
这个循环为什么一定会停？+
每进一轮，进位都至少左移一位、向高位推进；32 位整数最多 32 位，进位最终被移出/变 0，循环必然终止。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 两整数之和 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。