写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
提示:
a, b 均可能是负数或 0
结果不会溢出 32 位整数
无进位加法:a+b = a^b
n=a⊕b
c=a&b<<1
非进位和:异或运算
进位:与运算+左移一位
s=a+b⇒s=n+c
循环求 n 和 c ,直至进位 c = 0;此时 s = n ,返回 n 即可。
正数与边界数 0xffffffff 按位与(&) 操作后 仍得到这个数本身的真值:
负数与边界数按位与(&) 操作后 得到的是对应二进制数补码的真值:
通过查看符号位(最高位,即与 0x7ffffffff )断a为正数还是负数(0x7ffffffff是最大正数的补码) print(hex(1)) # = 0x1 补码
print(hex(-1)) # = -0x1 负号 + 原码 (Python 特色,Java 会直接输出补码)
print(hex(1 & 0xffffffff)) # = 0x1 正数补码
print(hex(-1 & 0xffffffff)) # = 0xffffffff 负数补码
python需要获得负数的补码,所以& 0xFFFFFFFF
a ^ 0xFFFFFFFF是将 1 至 32 位按位取反,前面再加表示将整个取反,实际上 a ^ 0xFFFFFFFF表示将 32 位以上的位取反,即由 0 变为 1 , 1 至 32 位不变。
class Solution:
def add(self, a: int, b: int) -> int:
while b:
a, b = (a ^ b) & 0xFFFFFFFF, ((a & b) << 1) & 0xFFFFFFFF
return a if a <= 0x7FFFFFFF else ~ a ^ 0xFFFFFFFF