二进制加法运算小技巧

二进制加法

• 位运算回顾 & （位与） ： 都为1 结果为 1 否则为 0 ｜ （位或） ： 都为0 结果为 0 否则为 1 -- 有 1 结果就是 1 ^ （异或） : 相同为 0 不同为 1 ～（取反） ： 0变1 1变0
• 二进制加法运算 以 7 + 8 = 15 为例 即： 111

• 1000 = 1111 关键点：涉及到进位操作该如何处理 如 1111 + 111 = ？

详细运算过程总结

1. 首先考虑需要进位的情况，在二进制运算中 1 + 1 需要进行进位。

1. 首先进行 异或 ^ 运算，获取无需进位的二进制数

1 1 1 1
^
0 1 1 1
=
1 0 0 0

2. 这个时候拿到的结果，对应二进制数的等于1的位是不需要进位的
3. 然后考虑需要进位的情况，什么样的情况需要进位？都为1的情况

1 1 1 1
&
0 1 1 1
=
0 1 1 1

4. 此时需要进位对应的二进制数是0 1 1 1

1. 那么此时该如何计算？

原始需要进行计算的两个数

---a：1 1 1 1
---b：0 1 1 1

异或结果
--- 1 0 0 0

位与结果：记为 x
--  0 1 1 1


很显然对于二进制的加法运算，需要进位的对应二进制位需要向左移一位
即    x << 1
得到  1 1 1 0

接下来操作已经得到的   异或结果  和  需要进位的二进制位  进行异或运算
即
1 0 0 0
^
1 1 1 0
=
0 1 1 0
此时得到的结果是最终需要保留的进位1

进行位与运算
1 0 0 0
&
1 1 1 0
=
1 0 0 0 << 1 = 1 0 0 0 0

然后
1 0 0 0 0
^
0 1 1 0
=
1 0 1 1 0 = 22 = a + b = 15 + 7 = 22

二进制加法总结

1. 首先通过两个数的异或运算得到一个二进制数，该数字如果不为0，其对应二进制位 等于1的位置表示该位不需要进位
2. 通过两个数进行位与运算，得到一个二进制数，该数字如果不为0，其对应二进制位 等于1的位置表示需要进行进位的位置，所以让其向左移动一位

1. 然后利用此时得到的数 与 步骤一运算得到的数 进行 异或运算——得到需要最终保留的二进制位数 记为结果 A
2. ............................................................................. 进行 位与运算——得到最终需要进位的二进制数，需要进位的二进制数，很显然需要向左移动一位 记为结果 B
3. 此时最终 A ^ B 即为最终结果.

public int twoSum(int a, int b) {
    while(b != 0) {
        int ans = a ^ b;
        int curry = a & b << 1;
        a = ans;
        b = curry;
    }
    return a;
}