不带+运算符添加两个数字(澄清)

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).需要将进位添加到该位置,因此算法再次运行.

算法重复直到不再有进位,在这种情况下,sum将包含正确的结果.

顺便说一下,return sum应该是return a,那么这两个sum和carry可能是普通的本地变量.