位运算

剑指 Offer 65. 不用加减乘除做加法

参考：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/

用到位运算，分解成两步：

（1）无进位：异或 （a^b）

（2）进位 :与+左移1位 (a&b<<1)

累加，直至不进位。

C++\JAVA【Python有所不同】

若数字 aaa 和 bbb 中有负数，则变成了减法，如何处理？
A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。

class Solution {
public:
    int add(int a, int b) {
        int c;

        while(b != 0){
            c = (a & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
};

这样做有一个缺点：leetcode的编译器比较严格，不能对负数进行左移，就是说最高位符号位必须要为0，才能左移。那么在a和b相 ‘与’ 之前，再’与’上一个最高位为0，其余位都为1的数 0x7fffffff，这样可以强制将最高位清零，然后再进行左移。

class Solution {
public:
    int add(int a, int b) {
        int c;

        while(b != 0){
            c = (a & 0x7fffffff & b) << 1;
            a ^= b;
            b = c;
        }
        return a;
    }
};

复杂度

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

Python 负数的存储

Python，Java 等语言中的数字都是以 补码 形式存储的。但 Python 没有 int , long 等不同长度变量，即在编程时无变量位数的概念。
获取负数的补码： 需要将数字与十六进制数 0xffffffff 相与。可理解为舍去此数字 32 位以上的数字（将 32 位以上都变为 000 ），从无限长度变为一个 32 位整数。
返回前数字还原： 若补码 aaa 为负数（ 0x7fffffff 是最大的正数的补码 ），需执行 ~(a ^ x) 操作，将补码还原至 Python 的存储格式。

a ^ x 运算将 1 至 32 位按位取反；

~ 运算是将整个数字取反；

因此， ~(a ^ x) 是将 32 位以上的位取反，1 至 32 位不变。

print(hex(1)) # = 0x1 补码
print(hex(-1)) # = -0x1 负号 + 原码 （ Python 特色，Java 会直接输出补码）
print(hex(1 & 0xffffffff)) # = 0x1 正数补码
print(hex(-1 & 0xffffffff)) # = 0xffffffff 负数补码
print(-1 & 0xffffffff) # = 4294967295 （ Python 将其认为正数）

class Solution:
    # ①在运算前，把负数的补码转换成高位为0的变换形式②在运算后，把负数的补码还原成高位为1的原始形式
    def add(self, a: int, b: int) -> int:
        x = 0xffffffff
        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)