LeetCode 371中等位运算
两整数之和 图解题解
这道题到底在问什么
不用 + 和 - 计算两个整数之和。
- 示例
- a=2, b=3 → 5
最优解：一步一步想明白
- 3十进制手算进位不适合机器位运算。
- 4a xor b 得到无进位和，(a & b) 左移得到进位；重复直到进位为 0。
- 5不准用 + 号。上行 a=2=0010，下行 b=3=0011。两个核心位运算：a^b = 不进位的和、(a&b)＜＜1 = 进位。
- 6a^b = 0010^0011 = 0001(各位相加、忽略进位)。a&b = 0010(都是 1 的位)，左移一位 = 0100(进位落到高一位)。
- 7把 a 换成不进位和 0001、b 换成进位 0100，再来一次。
- 8a^b = 0001^0100 = 0101(=5)；a&b = 0，左移还是 0 → 没有进位了。
- 9关键帧：加法 = 不进位和(^) + 进位(&＜＜1)，把进位反复并入，直到 进位 b = 0 就停。答案 = a = 0101 = 5。这正是硬件加法器的原理。
- 12一句话记住：a xor b 得到无进位和，(a & b) 左移得到进位；重复直到进位为 0。
- 21这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=bit 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：用 + 或 - 号
✓ 对：只用 ^、&、＜＜
题目禁止 +/-，必须异或求和、与求进位。
✗ 错：进位用 a&b 但忘了左移
✓ 对：(a&b)＜＜1
进位要进到高一位，所以左移 1 位。
✗ 错：负数/溢出处理
✓ 对：C++ 进位转 unsigned 左移；Python 用 32 位掩码
有符号左移溢出是未定义行为；Python 整数无限大要手动截断 32 位。
完整代码（Python / C++ / Java）
Python
class Solution:
def getSum(self, a, b):
mask = 0xffffffff
while b & mask:
carry = (a & b) << 1
a = (a ^ b) & mask
b = carry & mask
return a if a <= 0x7fffffff else ~(a ^ mask)C++
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
unsigned carry = ((unsigned)(a & b)) << 1;
a = a ^ b;
b = carry;
}
return a;
}
};Java
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
}套路模板 · 异或求和 + 进位
# 不用 + 做加法
while b != 0:
carry = (a & b) << 1 # 进位
a = a ^ b # 不进位和
b = carry # 进位并入，再来一轮
return a复杂度
时间复杂度
O(1)
位宽固定，进位最多传播 32 次
空间复杂度
O(1)
只用 a、b、carry 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两整数之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
a^b 得不进位和、(a&b)＜＜1 得进位；把进位并入再算，反复直到进位为 0，剩下的 a 就是和。
这道题为什么用「位运算」，换最直接的暴力解会差在哪？+
位运算抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。