c - 按位进位应用

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

首先是基础知识。异或两位与它们的和的底部数字相同。并且'两个位与它们的总和的最高位相同。

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。

[如果你有一个有两个输入和两个输出的电路，其中一个是输入的异或，另一个是输入的和，它被称为半加器 - 因为没有设施也可以输入进位(来自前一个数字)。]

因此，要对两位求和，您可以计算 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

我们仍然有进位，所以我们再来一次。

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

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