DeepSeek LeetCode 371. 两整数之和 Java实现

LeetCode 371. 两整数之和

题意

不使用运算符 + 和 -，计算两个整数 a、b 之和。

思路：位运算模拟加法

加法的两个部分：

1. 无进位相加：a ^ b（异或，相同为 0，不同为 1）
2. 进位：(a & b) << 1（与运算后左移一位）

不断将「无进位和」与「进位」相加，直到进位为 0。

Java 的 int 是 32 位补码，溢出会自动截断，因此负数同样适用。

Java 实现

classSolution{publicintgetSum(inta,intb){while(b!=0){intcarry=(a&b)<<1;// 计算进位a=a^b;// 无进位相加b=carry;// 把进位加到下一轮}returna;}}

示例

以 a = 1, b = 2 为例：

轮次 a b carry
初始 1 2 -
1 1 ^ 2 = 3 (1 & 2) << 1 = 0 0

b == 0，返回 3。

以 a = -1, b = 1 为例，循环若干轮后进位也会变为 0，最终返回 0。

复杂度

维度 复杂度
时间 O(1)（最多循环 32 次）
空间 O(1)

递归写法（可选）

classSolution{publicintgetSum(inta,intb){if(b==0)returna;returngetSum(a^b,(a&b)<<1);}}

注意点

· << 1 后可能溢出，但 Java 的 int 会自动丢弃高位，正好符合补码加法。
· 循环条件用 b != 0，不要写成 b > 0，否则负数进位会出错。