bit-manipulation - 不带+运算符的两个数字相加(澄清)

Question

我知道我们可以使用二进制加法器的逻辑，其中Sum = a XOR b和Carry = a AND b
我也有一个解决方案:

int add(int a, int b)
{
     if(b == 0)
         return sum;
     sum = a ^ b;
     carry = (a & b) << 1;
     return add(sum,carry);
}

我在这里不明白的是为什么每次递归时都会将进位移位或乘以2？

Answer 1

我觉得这很难解释，但这是一个尝试。一点一点地考虑，只有4种情况；

0+0=0 
0+1=1 
1+0=1 
1+1=0 (and generates carry)

两条线处理不同的情况

sum = a ^ b

处理大小写0 + 1和1 + 0，sum将包含简单的大小写，所有位的总和为1。

carry = (a & b) << 1

(a＆b)部分查找情况为1 + 1的所有位位置。由于加法运算结果为0，因此重要的是进位，并且将其移至左侧的下一个位置(<< 1)。需要将进位添加到该位置，以便算法再次运行。

重复该算法，直到不再有进位，在这种情况下，总和将包含正确的结果。

顺便说一句， return sum应该是 return a，然后 sum和 carry都可以是常规局部变量。