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

问题描述

我知道我们可以使用二进制加法器的逻辑，其中Sum = a XOR b和Carry = a AND b

I know that we can use the logic of binary adder where Sum = a XOR b and 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?

What I don't understand here is why is the carry bit shifted, or multiplied by 2 during each recursion?

推荐答案

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

I find this a bit tricky to explain, but here's an attempt; think bit by bit addition, there are only 4 cases;

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

这两行处理不同的情况

sum = a ^ b

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

Handles case 0+1 and 1+0, sum will contain the simple case, all bit positions that add up to 1.

carry = (a & b) << 1

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

The (a & b) part finds all bit positions with the case 1+1. Since the addition results in 0, it's the carry that's important, and it's shifted to the next position to the left (<<1). The carry needs to be added to that position, so the algorithm runs again.

算法重复执行，直到没有进位为止，在这种情况下，总和将包含正确的结果.

The algorithm repeats until there are no more carries, in which case sum will contain the correct result.

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

Btw, return sum should be return a, then both sum and carry could be regular local variables.

这篇关于不带+运算符的两个数字相加(澄清)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！