Vue.js

Appearance

On this page

实战：两整数之和 ​

不使用加减运算符计算两个整数的和。

问题描述 ​

LeetCode 371. Sum of Two Integers

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

示例：

输入：a = 1, b = 2
输出：3

思路 ​

用位运算模拟加法：

  • 异或：不考虑进位的加法（0+0=0, 0+1=1, 1+0=1, 1+1=0）
  • 与后左移：计算进位
  5 = 0101
+ 3 = 0011

异或：0110 (不进位的和)
与后左移：0010 (进位)

继续相加直到没有进位

解法 ​

javascript
function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;  // 进位
    a = a ^ b;                    // 不进位的和
    b = carry;
  }
  return a;
}

执行过程 ​

a = 5 = 0101, b = 3 = 0011

第1轮：
  carry = (0101 & 0011) << 1 = 0001 << 1 = 0010
  a = 0101 ^ 0011 = 0110
  b = 0010

第2轮：
  carry = (0110 & 0010) << 1 = 0010 << 1 = 0100
  a = 0110 ^ 0010 = 0100
  b = 0100

第3轮：
  carry = (0100 & 0100) << 1 = 0100 << 1 = 1000
  a = 0100 ^ 0100 = 0000
  b = 1000

第4轮：
  carry = (0000 & 1000) << 1 = 0000
  a = 0000 ^ 1000 = 1000
  b = 0000

结果：a = 8 = 1000

等等，5+3=8？让我重新计算...

实际上正确结果应该是：

a = 5, b = 3

第1轮：
  a = 5 ^ 3 = 6
  b = (5 & 3) << 1 = 2

第2轮：
  a = 6 ^ 2 = 4
  b = (6 & 2) << 1 = 4

第3轮：
  a = 4 ^ 4 = 0
  b = (4 & 4) << 1 = 8

第4轮：
  a = 0 ^ 8 = 8
  b = (0 & 8) << 1 = 0

结果：8 ✓（5 + 3 = 8）

负数处理 ​

JavaScript 中负数用补码表示，位运算自动处理：

-1 + 1:
  -1 的 32 位补码：11111111111111111111111111111111
   1 的 32 位补码：00000000000000000000000000000001

经过多轮迭代后，进位逐渐向高位传播，最终溢出消失
结果：0

边界情况 ​

javascript
// 两个正数
getSum(5, 3);  // 8

// 正数 + 负数
getSum(5, -3);  // 2

// 负数 + 负数
getSum(-5, -3);  // -8

// 0 的情况
getSum(0, 5);   // 5
getSum(5, 0);   // 5
getSum(0, 0);   // 0

常见错误 ​

错误一：计算顺序错误 ​

javascript
// 错误：先修改 a，再用修改后的 a 计算 carry
function getSum(a, b) {
  while (b !== 0) {
    a = a ^ b;
    b = (a & b) << 1;  // 此时 a 已经被修改！结果错误
  }
  return a;
}

// 正确：先保存 carry，再更新 a
function getSum(a, b) {
  while (b !== 0) {
    const carry = (a & b) << 1;  // 先计算进位
    a = a ^ b;                    // 再计算无进位和
    b = carry;
  }
  return a;
}

错误二：混淆 XOR 和 OR ​

javascript
// 错误：用 OR 代替 XOR
a = a | b;  // 1 | 1 = 1，无法模拟加法

// 正确：用 XOR
a = a ^ b;  // 1 ^ 1 = 0，模拟无进位加法

扩展：实现减法 ​

javascript
// a - b = a + (-b) = a + (~b + 1)
function getSubtract(a, b) {
  // 取反加一得到负数
  const negB = getSum(~b, 1);
  return getSum(a, negB);
}

扩展：实现乘法 ​

javascript
// 模拟竖式乘法
function getMultiply(a, b) {
  let result = 0;
  let negative = (a < 0) !== (b < 0);
  
  a = Math.abs(a);
  b = Math.abs(b);
  
  while (b !== 0) {
    if (b & 1) {
      result = getSum(result, a);
    }
    a <<= 1;
    b >>>= 1;
  }
  
  return negative ? getSum(~result, 1) : result;
}

相关题目 ​

题目难度关键点
371. 两整数之和中等本题
29. 两数相除中等位运算实现除法
191. 位1的个数简单n & (n-1) 技巧
190. 颠倒二进制位简单位操作基础

总结 ​

  1. 核心原理：加法 = 无进位和（XOR）+ 进位（AND 左移）
  2. 迭代终止：当进位为 0 时结束
  3. 变量顺序：必须先计算进位，再更新无进位和
  4. 负数处理：补码表示，位运算自动处理

复杂度 ​

  • 时间：O(1)，最多 32 轮
  • 空间：O(1)

在 GitHub 上编辑此页