按位进位应用

Question

说我天真，但在这方面我总是很挣扎。所以我只是浏览代码，在没有 + 运算符的情况下添加两个数字并撞到了这段代码：

int Add(int x, int y)
{
    // Iterate till there is no carry  
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y;  

        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y; 

        // Carry is shifted by one so that adding it to x gives the 
        // required sum
        y = carry << 1;
    }
    return x;
}

现在我明白了，他是如何计算进位的，但为什么 y!=0 以及这段代码如何获得两个数字相加的结果？

Answer 1

先说基础。两个位的异或运算与它们和的底部数字相同。And'ing 两位与它们总和的最高位相同。

A | B | A&B | A^B | A+B
-----------------------
0 | 0 |  0  |  0  |  00
0 | 1 |  0  |  1  |  01
1 | 0 |  0  |  1  |  01
1 | 1 |  1  |  0  |  10

如您所见，异或结果与总和的最后一位数字相同。您还可以看到，当 A 为 1 且 B 为 1 时，和的第一位数字仅为 1。

[如果你有一个有两个输入和两个输出的电路，其中一个是exclusive or输入的，另一个是and输入的，它被称为半加器 - 因为没有设施也输入进位（来自前一位）]

因此，要对两位求和，您需要计算 XOR 以获得结果的最低位，并计算 AND 以获得结果的最高位。

对于一对数字中的每一对位，我可以通过执行 XOR 和 AND 来计算这两位的总和。使用四位数字，例如 3 和 5

3 0011
5 0101
------
  0110 3^5 = 6 (low bit)
  0001 3&5 = 1 (high bit)

为了将 3 和 5 视为单个数字而不是四位的集合，这些高位中的每一个都需要被视为进位并添加到左侧的下一个低位。我们可以通过将 3&5 左移 1 位并添加到我们通过重复两个操作来完成的 3^5 来做到这一点

6    0110
1<<1 0010
     ----
     0100 6^(1<<1) = 4
     0010 6&(1<<1) = 2

不幸的是，其中一个添加导致生成另一个进位。所以我们可以重复操作。

4    0100
2<<1 0100
     ----
     0000 4^(2<<1) = 0
     0100 4&(2<<1) = 4

我们还有一个carry，所以我们又走了一遍。

0    0000
4<<1 1000
     ----
     1000 4^(4<<1) = 8
     0000 4&(4<<1) = 0

这一次，所有的进位都是 0，所以更多的迭代不会改变任何东西。我们已经完成了。