LeetCode 371. Sum of Two Integers

题目描述

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

tag

模拟加法题 模拟 位运算

样例

1
2
输入: a = -2, b = 3
输出: 1

算法1

(位运算) O(1)
思路

在 Python 中,整数不是 32 位的,也就是说你一直循环左移并不会存在溢出的现象,这就需要我们手动对 Python 中的整数进行处理,手动模拟 32 位 INT 整型。

具体做法是将整数对 0x100000000 取模,保证该数从 32 位开始到最高位都是 0。

推荐总结https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
class :
def getSum(self, a: int, b: int) -> int:
if a == -b:
return 0
if abs(a) > abs(b):
a, b = b, a
if a < 0:
return -self.getSum(-a, -b)
while b:
c = a & b
a ^= b
b = c << 1
return a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def getSum(self, a: int, b: int) -> int:

MAX = 0x7FFFFFFF

MIN = 0x80000000


mask = 0xFFFFFFFF

while b != 0:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask


# then get 32-bit positive's Python complement negative
return a if a <= MAX else ~(a ^ mask)