剑指offer【65】：不用加减乘除做加法（位运算+python存储负数）

题目：

思路+代码：

思路：
a + b == (a ^ b) + ((a & b ) << 1)
1.两个数 异或操作结果 == 两个数二进制无进位和 ; a ^ b
2.两个数 与操作结果 == 两个数的进位结果 ; a & b ) << 1
3.两个结果相加即为两个数的和；
4.return a; 是因为当无进位时，说明上一轮计算的无进位和(a)，已经是最终结果

时间复杂度：最差情况下（例如 a= 0x7fffffff , b=1 时），需循环 31 次，使用 O(1) 时间；每轮中的常数次位操作使用 O(1)
空间复杂度：O(1)

class Solution:
    #   思路：
    #   a + b == (a ^ b) + ((a & b ) << 1)
    #   1.两个数 异或操作结果  ==  两个数二进制无进位和 ;   a ^ b   
    #   2.两个数 与操作结果 == 两个数的进位结果 ;    a & b ) << 1   
    #   两个结果相加即为两个数的和；  
    #   return a; 是因为当无进位时，说明上一轮计算的无进位和(a)，已经是最终结果

    def add(self, a: int, b: int) -> int:
        
        x = 0xffffffff  # 32位1
        a, b = a & x, b & x
        while b !=0:
            a, b = (a ^ b), (a & b) << 1 & x
        return a if a <= 0x7fffffff else ~(a ^ x)  # 0x7fffffff 是最大的正数的补码；

python二进制note：

1. 负数第32位符号位为1，且高位也都是为1；0x7fffffff 是最大的正数的补码；
2. 一个数 和 0xffffffff 进行异或操作，等同于取反；只有两个数相等时异或才为0
3. 获取负数的补码：需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字，从无限长度变为一个 32 位整数。
4. 负数的32位以上的位取反就是python存储的负数格式，请问这句话怎么理解？
   python 存储负数的形式比较特殊，因为 python 的数字没有 32 / 64 位等概念，而高位的数字取决于此数字是正数还是负数，是正数则为 0 ，是负数则为 1
5. 取数字的后32位就是负数的补码，如果a一开始为负数，最后结果也是负数，为什么要将32位以上取反呢？
   因为 python 里也是用补码存储数字，初始计算时，a 跟0xffffffff 进行异或使得，a（负数）高位异或操作后变成了0，所以计算结束后，存储a需要恢复成python存储负数格式进行: ~(a ^ 0xffffffff)；
6. python存储负数麻烦，返回前数字： 若补码 a 为负数（ 0x7fffffff 是最大的正数的补码 ），需执行 ~(a ^ x) 操作，将补码还原至 Python 的存储格式。 a ^ x 运算将 1 至 32 位按位取反； ~ 运算是将整个数字取反；因此， ~(a ^ x) 是将 32 位以上的位取反，即由 0 变为 1 ， 1 至 32 位不变。