题目描述
不使用运算符 + 和 - ,计算两整数 a 、b 之和。
示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
解法
之前在Leetcode 137. 只出现一次的数字 II中提到过二进制的异或运算相当于不进位加法,二进制的与运算相当于捕获进位点。则两整数相加,等同于两整数异或运算的值,加上与运算左移一位的值,迭代执行,直到进位点为零。所以该题目可以通过异或运算和与运算替代加法的执行。
因为在python中整数不会溢出,所以要模拟32位二进制的位运算,需要每次运算后对
mask=0x100000000
执行取余运算,来获取后32位二进制。 并且需要注意,32位二进制能够表示的最大数是max_int=0x7fffffff
,即首位符号位为0。所以最后python表示的返回值,若大于max_int
,则需要将该python返回值处理成与后32位二进制表示值相等的结果。 因为此时python值大于max_int
值,所以从右向左的第32位二进制位1,也就是32位二进制下的负数,此时需要做的处理操作,就是把第32位和左边的所有位(不确定python是多少位)都处理成1,也就是把32位二进制的下的负数,变成python下的负数。 参考LeetCode上的一种处理方式,对0~31位进行取反,然后对所有位进行取反,以此完成32位及之后的所有位置1的操作。
class Solution:
def getSum(self, a: int, b: int) -> int:
mask=0x100000000
max_int=0x7fffffff
min_int=0x80000000
while b:
a,b=(a^b)%mask,((a&b)<<1)%mask
return a if a<=max_int else ~((a%min_int)^max_int)
参考