不用加减乘除做加法

每一位是咋算的呢？进位((a&b)>> 1)+本位异或

当进位是0的时候就得到结果了。。

那么能不能本位和是0呢？比如11 + 1

1

1

本位和

0

进位

10 

然后神奇的事情发生了，0+10 本位和 10 进位0 所以可以按照进位是0来终止流程

如果是负数怎么办？

比如说1 + -1

class Solution {
public:
    int add(int a, int b) {
        while (b) {
            int carry = (unsigned int)(a & b) << 1;
            a ^= b;
            cout << "carry is " << carry << " a is " << a << endl;
            b = carry;
        }
        return a;
    }
};

打印carry 和 a

carry is 2 a is -2
carry is 4 a is -4
carry is 8 a is -8
carry is 16 a is -16
carry is 32 a is -32
carry is 64 a is -64
carry is 128 a is -128
carry is 256 a is -256
carry is 512 a is -512
carry is 1024 a is -1024
carry is 2048 a is -2048
carry is 4096 a is -4096
carry is 8192 a is -8192
carry is 16384 a is -16384
carry is 32768 a is -32768
carry is 65536 a is -65536
carry is 131072 a is -131072
carry is 262144 a is -262144
carry is 524288 a is -524288
carry is 1048576 a is -1048576
carry is 2097152 a is -2097152
carry is 4194304 a is -4194304
carry is 8388608 a is -8388608
carry is 16777216 a is -16777216
carry is 33554432 a is -33554432
carry is 67108864 a is -67108864
carry is 134217728 a is -134217728
carry is 268435456 a is -268435456
carry is 536870912 a is -536870912
carry is 1073741824 a is -1073741824
carry is -2147483648 a is -2147483648
carry is 0 a is 0

经过一大堆循环，证明最终是可以的。。。

注意

LeetCode中国版的C++好像不支持负值左移，会报错:

runtime error: left shift of negative value -2147483648 (solution.cpp)

• 需要强转为无符号数（unsigned int）

本文地址：https://blog.csdn.net/m0_37313888/article/details/107384722