371. 两整数之和

🟠   🔖  位运算 数学  🔗 力扣 LeetCode

题目

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2

Output: 3

Example 2:

Input: a = 2, b = 3

Output: 5

Constraints:

• -1000 <= a, b <= 1000

题目大意

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

输入： a = 1, b = 2

输出： 3

示例 2：

输入： a = 2, b = 3

输出： 5

提示：

• -1000 <= a, b <= 1000

解题思路

可以利用二进制的性质：

• 异或运算 a ^ b：相当于不考虑进位的二进制加法。
  • 例如：5 ^ 3 = 6，对应二进制 0101 ^ 0011 = 0110。
• 与运算 a & b：用于计算进位，只有两位都为 1 时产生进位。
  • 例如：5 & 3 = 1，对应二进制 0101 & 0011 = 0001。
• 进位的左移 c << 1：将进位信息左移一位，模拟加法中的进位。

1. 初始时 a 和 b 为两个加数。
2. 当 b == 0 时，说明不再有进位产生，此时 a 即为结果。
3. 否则，将 c = a & b 计算出进位，将 a = a ^ b 更新为未进位加法的结果。
4. 将 b = c << 1 更新为进位信息，继续迭代直至 b == 0。

复杂度分析

• 时间复杂度：O(1)，最多进行 32 次位操作。
• 空间复杂度：O(1)，不使用额外的空间。

代码

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function (a, b) {
	let c;
	while (b !== 0) {
		c = a & b;
		a = a ^ b;
		b = c << 1;
	}
	return a;
};

相关题目

题号	标题	题解	标签	难度	力扣
2	两数相加	[✓]	递归 链表 数学	🟠	🀄️ 🔗