0371. Sum of Two Integers.md

题目描述

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

我的思路

这一题不能使用加法操作，那么只能回归计算机的本质，使用位操作。在草稿纸上进行两个二进制数相加时，我发现：不考虑进位的加，0+0=0，0+1=1, 1+0=1，1+1=0，这就是“异或”的运算规则；只考虑进位的加，0+0=0, 0+1=0, 1+0=0, 1+1=1，这其实这就是“与”的运算规则。

附Python中位运算符：

运算符	描述
&	与
|	或
^	异或
~	按位取反
<<	左移：运算数的各二进位全部左移若干位，高位丢弃，低位补0
>>	右移：把">>"左边的运算数的各二进位全部右移若干位

但提交后发现，其他语言可以按照这个方法做，唯独Python不行。上网找到原因：Python 对于负数的存储方式和 c++/c/java 不一样，其他语言中负数都用补码来存储，Python里的数是无所谓Overflow的，即没有位数限制，因此也就无所谓补码。

代码里的将一个数对0x100000000取模（Python的取模运算结果恒为非负数），是希望该数的二进制表示从第32位开始到更高的位都同是0，以在0-31位上模拟一个32位的int。对于输出的a我们也要进行截断，如果a是正数则直接输出a；否则需要进行对应操作来获得a的补码。

代码

class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b != 0:
            carry = a & b
            a = (a ^ b) % 0x100000000
            b = (carry << 1) % 0x100000000
        return a if a <= 0x7FFFFFFF else a | (~0x100000000+1)