371. 两整数之和
题目描述
输入两个整数 a 和 b，返回 a 与 b 的和。
限制：代码中不能用 + 和 - 这两个运算符。
示例 1
输入：a = 1, b = 2 输出：3
示例 2
输入：a = 2, b = 3 输出：5
数据范围
-1000 <= a, b <= 1000
解题思路
二进制加法可以拆成两部分：不考虑进位的和是 a ^ b，进位是 (a & b) << 1。把进位当成新的 b 再加一次，直到进位为 0。Python 的整数没有位宽，所以用 MASK 把数限制在 32 位补码里，最后把最高位为 1 的结果还原成负数。
为什么正确
每轮之后 a + b 的真实和（模 2^32）保持不变，而 b 的最低若干位不断变成 0，最多 32 轮后 b 归零。
复杂度分析
时间 O(32) = O(1)，空间 O(1)。
易错点
Python 的负数在左移时不会溢出，不加 MASK 会死循环；最后还要用 ~(a ^ MASK) 把 32 位补码还原成负数。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getSum(self, a: int, b: int) -> int:
MASK = 0xFFFFFFFF
a &= MASK
b &= MASK
while b:
carry = ((a & b) << 1) & MASK
a ^= b
b = carry
if a < 0x80000000:
return a
return ~(a ^ MASK)class Solution {
public int getSum(int a, int b) {
int MASK = 0xFFFFFFFF;
a &= MASK;
b &= MASK;
while (b != 0) {
int carry = (a & b) << 1;
a ^= b;
b = carry;
}
if (a >= 0) {
return a;
}
return a;
}
}class Solution {
public:
int getSum(int a, int b) {
unsigned int MASK = 0xFFFFFFFFu;
unsigned int ua = (unsigned int)a & MASK;
unsigned int ub = (unsigned int)b & MASK;
while (ub) {
unsigned int carry = (ua & ub) << 1;
ua ^= ub;
ub = carry;
}
if (ua < 0x80000000u) {
return (int)ua;
}
return (int)ua;
}
};func getSum(a int, b int) int {
MASK := 0xFFFFFFFF
a &= MASK
b &= MASK
for b != 0 {
carry := ((a & b) << 1) & MASK
a ^= b
b = carry
}
if a < 0x80000000 {
return a
}
return ^(a ^ MASK)
}var getSum = function(a, b) {
const MASK = 0xFFFFFFFF;
a &= MASK;
b &= MASK;
while (b !== 0) {
const carry = (a & b) << 1;
a ^= b;
b = carry;
}
if (a >= 0) {
return a;
}
return a;
};function getSum(a: number, b: number): number {
const MASK = 0xFFFFFFFF;
a &= MASK;
b &= MASK;
while (b !== 0) {
const carry = (a & b) << 1;
a ^= b;
b = carry;
}
if (a >= 0) {
return a;
}
return a;
}