用位运算模拟全加器的实现

题目链接-来源：力扣（LeetCode）

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

思路：

禁用四则运算实现加法，则我们不用另辟蹊径，可以直接回归计算机的本质，利用位运算实现一个全加器。
全加器的实现需要按位进行，为了方便计算进位，我们可以从最低位开始。
每一轮循环，我们需要 3 个参数，当前位的「加数」 ba、「被加数」bb，以及前一位的「进位」Cin。利用这些参数，我们需要生成 当前位的和 bit，以及当前位的进位 Cout，同时将 bit 累加到结果 res 当中。
我们可以用一个辅助参数 digit 记录当前所在的位，初始为 1，每一轮左移，用其分别与 a、b 作「与」运算，即可获得当前位的 ba、bb。
当前位的和 bit 可以通过 ba、bb、Cin 作「异或」运算获得。
由于我们的 bit 每次都在不同的位上，所以累加操作可以通过与 res 直接进行 「或」运算实现。
进位 Cout 的计算也不难，我们需要 ba、bb、Cin 中至少 2 个数为 ‘1’ 才能进位，因此将其两两作「与」运算，将结果再进行连续「或」运算即可。注意 Cout 需要输出到下一位作为 Cin，因此我们要将其进行「左移」操作。
循环中止条件也可用 digit 作标志，由于 digit 最多只有 32 位，当其移位 32 次后即溢出，所有位上均为 0。
由于负数用补码表示，导致其加法计算的位运算实现与正数无异，为我们的实现带来了方便，无需额外考虑。

时间复杂度：O(1)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int add(int a, int b) {
        int res = 0, digit = 1, carry = 0;
        while (digit != 0 || carry != 0) {
            int ba = a & digit, bb = b & digit;
            int bit = carry ^ ba ^ bb;
            res |= bit;
            carry = ((ba & bb) | ((ba ^ bb) & carry)) << 1;
            digit <<= 1;
        }
        return res;
    }
}