难度: Medium
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2 输出：3
示例 2：
输入：a = 2, b = 3 输出：5
提示：
-1000 <= a, b <= 1000
Submission
运行时间: 19 ms
内存: 15.9 MB
class Solution:
def getSum(self, a: int, b: int) -> int:
mask1,mask2,mask3 = 4294967296,2147483648,2147483647
a %= mask1
b %= mask1
while b!=0:
tmp = ((a&b)<<1)%mask1
a = (a^b)%mask1
b = tmp
return ~((a^mask2)^mask3) if a&mask2 else a
Explain
这个题解使用位运算来计算两个整数的和，具体思路如下： 1. 使用掩码 mask1 对 a 和 b 取模，将它们限制在 32 位整数范围内。 2. 使用一个 while 循环计算 a 和 b 的和： - 用 a&b 计算 a 和 b 的进位，并将结果左移一位（乘以 2），再对 mask1 取模。 - 用 a^b 计算 a 和 b 的无进位和，再对 mask1 取模。 - 将进位赋值给 b，无进位和赋值给 a。 - 循环直到进位 b 为 0。 3. 最后判断 a 的最高位是否为 1（即是否为负数），如果是则对 a 进行取反并减一的操作，否则直接返回 a。
时间复杂度: O(n)
空间复杂度: O(1)
```python
class Solution:
def getSum(self, a: int, b: int) -> int:
mask1,mask2,mask3 = 4294967296,2147483648,2147483647
a %= mask1 # 对 a 取模，限制在 32 位整数范围内
b %= mask1 # 对 b 取模，限制在 32 位整数范围内
while b!=0:
tmp = ((a&b)<<1)%mask1 # 计算进位
a = (a^b)%mask1 # 计算无进位和
b = tmp # 将进位赋值给 b
return ~((a^mask2)^mask3) if a&mask2 else a # 判断 a 是否为负数，如果是则取反并减一，否则直接返回 a
```
Explore
掩码mask1用于确保变量a和b的值被限制在32位整数范围内，其值为`4294967296`，等于`2^32`，这是因为在Python中整数可以超过标准的32位整数范围。掩码mask2用于确定整数a是否为负，其值为`2147483648`，即`2^31`，代表32位整数的最高位。如果a的最高位为1，即a&mask2的结果非零，则a为负数。掩码mask3用于在a为负时，将其转换为标准的32位二进制补码形式，其值为`2147483647`，即`2^31 - 1`，用于与a进行位运算，以正确计算负数的值。
在计算进位时使用左移操作，是因为在二进制加法中，进位需要向左移动一位（即乘以2）。例如，1加1产生的进位应当影响下一位的结果。取模mask1操作是为了保证计算结果不会超出32位整数的范围，避免在Python中整数自动扩展到更多位带来的问题。这样可以确保算法在模拟32位整数运算时的准确性和一致性。
在二进制中，负数通常使用补码形式表示。补码是通过取反（所有位上的0变为1，1变为0）然后加一来得到的。在题解中，如果a的最高位为1，表示a为负数，使用取反操作（`~((a^mask2)^mask3)`）是为了将32位正数转换为其对应的负数补码形式。这里首先将a与mask2异或，用于将32位中的最高位反转，然后与mask3异或来反转其余位，最后使用`~`操作符取反。这样的操作确保了负数在32位整数内正确表示其补码形式。
在每次循环中，进位b是通过计算a和b的位与`&`然后左移一位得到的。这意味着，若没有两个位同时为1的情况，进位b将会是0。每次循环，进位信息向更高位移动，减少了低位的进位需求。因此，随着循环的继续，进位数b会逐渐减少到0，因为没有更多的进位需要处理，从而停止循环。这保证了算法最终会停止，且a将包含最终的加法结果。