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

问题描述 投票：26回答：4

我在leetcode做这个question。

请求：

计算两个整数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));
javascript bitwise-operators
4个回答
26
投票

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

在二进制表示法中，他们是a = 0011和b = 0101

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

因此，当我们做a^b结果将是0110。

AND + SHIFT

a&b执行逻辑AND操作。它只在a = b = 1时返回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以来一切正常

35
投票

它基本上复制了half-adder

添加2位A和B产生2个输出：一个和和如下所示的进位

╔═══════╤═════════════╗
║ Input │   Output    ║
╠═══╤═══╪═══════╤═════╣
║ A │ B │ carry │ sum ║
╟───┼───┼───────┼─────╢
║ 0 │ 0 │   0   │  0  ║
╟───┼───┼───────┼─────╢
║ 1 │ 0 │   0   │  1  ║
╟───┼───┼───────┼─────╢
║ 0 │ 1 │   0   │  1  ║
╟───┼───┼───────┼─────╢
║ 1 │ 1 │   1   │  0  ║
╚═══╧═══╧═══════╧═════╝

从表中我们得到输出的逻辑：carry = 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中添加每个位，在Sum中留下a和b的非进位和。然后我们必须将进位加到无余和以得到最终结果，因为我们只有一个半加法器而不是一个加法器，它做了+ b =a⊕b+进位

也可以看看

2
投票
 int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
int carry = (p & q) << 1; // Left Shift, 1+1=2
if (carry != 0) {
    return getSum(result, carry);
}
return result;

从p = 5开始，q = 6。然后XOR将是，

0101
0110
------
0011

因此，XORing导致（0011）实际上是十进制的3。然后我们得到了AND和p和q，

0101
0110
-------
0100

通过ANDing 5和6得到4（二进制100），现在如果我们把这个值移动1，我们得到

 0100<<1=1000

所以我们在第一次递归后获得8（二进制1000）。结果（进位变量）不为零，让xor值和进位值再次递归。

getSum(3, 8);

所以，做第一次XORing，我们得到，

0011
1000
-------
1011

这次XORing产生了11（1011二进制），所以我们现在执行AND，

0011
1000
-------
0000

对于ANDing 3和8，我们得到所有ZERO，所以这次左移运算符也导致ZERO，因为我们在这里没有1，这可以通过左移零来给我们一个值。当进位变量现在为零时，我们到达递归的末尾，并且XORed值将是Sum，即11（二进制中的1011）。

希望你得到程序的工作。您可以通过学习按位操作来了解更多信息，因为它是机器进行算术运算的方式。

0
投票

^是XOR，是一种按位操作。在单个位上，规则是0 ^ 0 = 0，0 ^ 1 = 1，1 ^ 0 = 0和1 ^ 1 = 0，并且您只需在处理多位值时在相应的位上执行它。这个名称是“exclusive or”的缩写，来自A ^ B是1的事实，当且仅当A或B是1，而不是两者。但是，谈论它的另一个名字⊕更有意思。 ⊕是+但略有不同。你会注意到⊕的规则类似于加法规则：0 + 0 = 0，0 + 1 = 1，1 + 0 = 1和1 + 1 = 10。 ⊕是+，除了1 ⊕ 1 = 0;也就是说，⊕是+，除非没有携带。这适用于多个位：011 + 001 = 100，因为你将1带到两个地方的那个地方，然后再将1带到四肢。然后，011 ⊕ 001 = 010，因为你只是不携带。

现在，当真正添加时，你什么时候携带？在二进制中，答案非常简单：当给定位置有两个1s时，你将1带到下一个地方。这很容易理解为按位AND，&。 1 & 1 = 1和0否则。对于011 + 001，没有携带的添加给011 ⊕ 001 = 010，我们可以告诉我们需要携带一个1从那个地方，因为011 & 001 = 001。 (a & b) << 1的转变变成了一个数字“我需要从哪里携带？”进入“我需要在哪里添加载体？”：(011 & 001) << 1 = 010;我需要在两个地方添加一个进位。

所以，在getSum，我们想知道a + b。我们在没有携带a ^ b的情况下计算加法，我们找到了需要用(a & b) << 1添加进位的位置。现在，我们只需要将这两者加在一起。好吧，我们已经有了将数字加在一起的功能;它被称为getSum。所以，我们基本上只是编写function getSum(a, b) { return getSum(a ^ b, (a & b) << 1); }，除非我们确保在没有任何东西可以进行短路的情况下，从而使我们免于无限递归。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.