Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • -1000 <= a, b <= 1000

解题思路

解题思路

这道题要求不使用加减运算符计算两数之和，核心思路是利用位运算模拟加法过程。

位运算加法原理

加法可以分解为两个步骤：

  1. 异或运算（XOR）：计算不考虑进位的和

    • 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0, 1 + 1 = 0（不考虑进位）
    • 这正是异或运算的结果

  2. 与运算加左移：计算进位

    • 只有 1 + 1 = 10 会产生进位
    • (a & b) << 1 计算所有进位位置

算法流程

重复执行以下步骤直到没有进位：

  1. 计算不含进位的和：sum = a ^ b
  2. 计算进位：carry = (a & b) << 1
  3. 更新 a 为 sum，b 为 carry
  4. 当 carry 为 0 时，a 就是最终结果

注意事项

不同语言处理负数的方式不同：

  • C++/C#：直接使用位运算即可
  • Python：需要处理负数的符号扩展问题
  • JavaScript：需要使用 32 位整数运算

推荐解法：迭代位运算法，时间复杂度 O(1)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Python 中需要处理 32 位整数
        mask = 0xFFFFFFFF
        
        while b != 0:
            carry = ((a & b) << 1) & mask
            a = (a ^ b) & mask
            b = carry
        
        # 处理负数
        if a > 0x7FFFFFFF:
            return ~(a ^ mask)
        return a

public class Solution {
    public int GetSum(int a, int b) {
        while (b != 0) {
            uint carry = (uint)(a & b) << 1;
            a = a ^ b;
            b = (int)carry;
        }
        return a;
    }
}

var getSum = function(a, b) {
    while (b !== 0) {
        let carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(1)
空间复杂度O(1)

说明：虽然有 while 循环，但由于整数位数固定（32位），循环次数是常数，因此时间复杂度为 O(1)。

相关题目