Leetcode 371. 两整数之和

题目描述

不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​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)

参考

位运算详解以及在 Python 中需要的特殊处理