难度: Easy
设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。
示例:
输入: a = 1, b = 1 输出: 2
提示：
a,b均可能是负数或 0- 结果不会溢出 32 位整数
Submission
运行时间: 23 ms
内存: 16.0 MB
MASK1 = 2**32
MASK2 = 2**31
MASK3 = 2**31 -1
class Solution:
def add(self, a: int, b: int) -> int:
a %= MASK1
b %= MASK1
while b!=0:
carry = ((a&b)<<1) % MASK1
a = (a^b)%MASK1
b = carry
if a & MASK2:
return ~((a^MASK2)^MASK3)
else:
return a
Explain
本题解利用位运算来实现加法。首先，通过异或操作 `a^b` 计算出不考虑进位的和，通过 `a&b` 获取需要进位的位置。将进位结果左移一位得到新的进位值。这个过程重复，直到没有新的进位产生（即进位值为0）。对于负数的处理，使用掩码将其转换为32位有符号整数。如果最高位为1表示结果为负数，需要将其转换回原本的负数表示方法。
时间复杂度: O(1)
空间复杂度: O(1)
MASK1 = 2**32 # 用于确保数字在32位整数范围内
MASK2 = 2**31 # 32位整数的符号位
MASK3 = 2**31 -1 # 32位整数的最大正整数值
class Solution:
def add(self, a: int, b: int) -> int:
a %= MASK1 # 限制a在32位整数范围内
b %= MASK1 # 限制b在32位整数范围内
while b != 0: # 当还有进位未处理时继续循环
carry = ((a & b) << 1) % MASK1 # 计算新的进位
a = (a ^ b) % MASK1 # 通过异或计算不考虑进位的和
b = carry # 将进位赋值给b，准备下一轮计算
if a & MASK2: # 如果最高位为1，说明结果为负数
return ~((a ^ MASK2) ^ MASK3) # 将其转换为负数的正确表示
else:
return a # 返回计算结果
Explore
在进行二进制加法时，异或运算可以用来模拟不带进位的加法，因为它只在两个比特位不同的时候产生1（即0+1或1+0）。与运算则用来确定哪些位置会产生进位，因为只有两个比特位都为1时（即1+1），才会在该位置产生进位。这使得位运算特别适合模拟加法过程，因为它可以分开处理加法的两个主要部分：求和与进位。
这三个掩码用于处理32位整数的边界条件和符号。MASK1 (2**32) 用于确保数字在32位整数范围内，防止溢出。在Python中，整数可以超过标准的32位大小，使用MASK1进行模运算可以限制结果保持在32位内。MASK2 (2**31) 是32位整数的符号位，用于检测结果是否为负数（即最高位是否为1）。如果最高位为1，结果应被视为负数。MASK3 (2**31 -1) 是32位整数中最大的正整数，用于在负数处理中将符号位以外的部分转换回原本的负数表示方法。
在二进制中，负数通常使用补码形式表示。如果计算的结果是负数，最高位会是1。在32位整数中，这意味着需要将这个表示转换成标准的负数形式。具体操作是首先通过异或操作 (a ^ MASK2) 移除符号位，然后将结果与MASK3异或，最后取反。这样能将补码形式的负数转换为其正确的负数值。