什么是a ^ b和（a＆b）<< 1？

Question

我在leetcode中做了这个问题。

请求：

计算两个整数a和b的总和，但不允许使用+和-运算符。

我不明白它提供的解决方案

有人可以解释一下此getSum功能的工作原理吗？

这是JS中的答案：

var getSum=function(a,b) {
    const Sum = a^b; //I can't understand how those two line's code can
    const carry = (a & b) << 1; //get the sum
        if(!carry) {
            return Sum
        }
    return getSum(Sum,carry);
};
console.log(getSum(5,1));

Answer 1

基本上是复制半加法器

将A和B的2位相加会产生2个输出：总和和进位如下所示

???????????????????????
? Input ?   Output    ?
???????????????????????
? A ? B ? carry ? sum ?
???????????????????????
? 0 ? 0 ?   0   ?  0  ?
???????????????????????
? 1 ? 0 ?   0   ?  1  ?
???????????????????????
? 0 ? 1 ?   0   ?  1  ?
???????????????????????
? 1 ? 1 ?   1   ?  0  ?
???????????????????????

从表中我们可以得到输出的逻辑：进位= A和B，sum = A xor B

XOR也称为无进位加法运算符，由？表示。+里面有符号

所以上面的代码片段是这样工作的

const Sum=a^b;              // sum = a xor b = a ? b
const carry=(a&b)<<1;       // carry = 2*(a and b), since we carry to the next bit
if(!carry){
    return Sum;             // no carry, so sum + carry = sum
}
return getSum(Sum,carry);   // a + b = sum + carry

因此a^b，同时将a和b中的每一位相加，而将a和b的非进位和保留在中Sum。然后，我们必须将进位加到无进位总和上，以得到最终结果，因为我们只有一个半加法器，而不是一个全加法器，所以a + b = a？b +携带

也可以看看

• 不带+运算符的两个数字相加（澄清）
• 不使用+运算符将两个数字相加的最佳方法是什么？
• 在不使用+或任何算术运算符的情况下将两个数字相加
• 不使用加法运算符将两个数相加

Answer 2

让我们通过例子学习。试想一下，a = 3和b = 5

用二进制表示，它们是a = 0011和b = 0101

XOR： a^b是XOR运算符。比较两个位时，0如果它们相同或1不同，则返回。01^10 => 11

因此，当我们执行操作时，a^b结果将是0110。

AND + SHIFT

a&b执行逻辑AND运算。仅当时返回1 a = b = 1。

在我们的例子中，结果是 0001

<<将其移动（0在右侧添加），结果变为0010将carry变量设置为true的结果。（只会0000是假的）。

下一个迭代：

一切重复，但是现在a = 0110和b = 0010（Sum以及carry从上次执行开始）

现在a^b = 0100和(a&b)<<1 = 0100

再次重复。

现在a^b = 0000和(a&b)<<1 = 1000

然后再次。

现在a^b = 1000和(a&b)<<1 = 0000。现在carry终于到了false。我们返回的1000是十进制8。

自从一切正常 3+5=8