0371. 两整数之和

• 标签：位运算、数学
• 难度：中等

题目链接

• 0371. 两整数之和 - 力扣

题目大意

描述：给定两个整数 $a$ 和 $b$。

要求：不使用运算符 + 和 - ，计算两整数 $a$ 和 $b$ 的和。

说明：

• $-1000 \le a, b \le 1000$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：位运算

需要用到位运算的一些知识。

• 异或运算 a ^ b：可以获得 $a + b$ 无进位的加法结果。
• 与运算 a & b：对应位置为 $1$，说明 $a$、$b$ 该位置上原来都为 $1$，则需要进位。
• 左移运算 a << 1：将 $a$ 对应二进制数左移 $1$ 位。

这样，通过 a ^ b 运算，我们可以得到相加后无进位结果，再根据 (a & b) << 1，计算进位后结果。

进行 a ^ b 和 (a & b) << 1 操作之后判断进位是否为 $0$，若不为 $0$，则继续上一步操作，直到进位为 $0$。

注意：

Python 的整数类型是无限长整数类型，负数不确定符号位是第几位。所以我们可以将输入的数字手动转为 $32$ 位无符号整数。

通过 a &= 0xFFFFFFFF 即可将 $a$ 转为 $32$ 位无符号整数。最后通过对 $a$ 的范围判断，将其结果映射为有符号整数。

思路 1：代码

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MAX_INT = 0x7FFFFFFF
        MASK = 0xFFFFFFFF
        a &= MASK
        b &= MASK
        while b:
            carry = ((a & b) << 1) & MASK
            a ^= b
            b = carry
        if a <= MAX_INT:
            return a
        else:
            return ~(a ^ MASK)

思路 1：复杂度分析

• 时间复杂度：$O(\log k)$，其中 $k$ 为 $int$ 所能表达的最大整数。
• 空间复杂度：$O(1)$。