位运算进位的应用

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，这段代码是如何实现两个数字相加的结果的呢？

- Puneet Goswami

---

阅读有关半加器和全加器的内容-这里的逻辑基本上是硬件实现加法的直接翻译。 - Paul R

只要 y 非零，继续添加（部分）y 似乎是合乎逻辑的：如果为零，则完成，因为对于所有 x，x + 0 == x。 - unwind

只需尝试一个示例，您就会理解:p - kaldoran

铅笔和纸在这里也非常好用。 - Jabberwocky

当您将两个数字相加时，可能会得到一个进位位；当将其与下面的两个数字相加时，您可能会再次得到一个进位位，以此类推。这就是循环的作用。当没有更多进位时，循环停止。 - n. m.

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。

如果有一个由两个输入和两个输出组成的电路，其中一个输出是输入的异或结果，另一个输出是输入的与结果，则称其为半加器——因为没有输入进位（来自上一位数字）的设施。

因此，要对两个二进制位求和，可以通过异或计算获取结果的最低位，通过与运算获取结果的最高位。

对于每对数字中的每一对二进制位，可以通过异或和与运算来计算这两个二进制位的和。例如，使用四位数字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，因此再进行迭代也不会有变化。我们已经完成了。

- JeremyP

Answer 2

我将尝试用一个简单的3位示例来解释它（您可以跳过这个示例，直接查看粗体字标记的实际解释，该解释从现在开始我们将介绍如何从发布的代码中实现相同的流程开始）。

假设我们想要将x=0b011和y=0b101相加。首先，我们将最低有效位相加：1+1 = 0b10

carry: x10
x:     011
      +
y:     101
      -----
       xx0

然后我们加上第二位（按照书上的说法，我们需要加上前一阶段的进位，但我们也可以在以后的阶段跳过它）：1+0 = 0b1

carry: 010
x:     011
      +
y:     101
      -----
       x10

对第三位执行相同的操作：0+1 = 0b1

carry: 010
x:     011
      +
y:     101
      -----
       110

现在我们有carry = 0b010和一些部分结果0b110。 还记得我之前的评论吗？我们会在稍后处理进位。现在就是这个“稍后”的阶段了。现在我们将进位加到我们得到的部分结果上（请注意，如果我们在早期阶段分别为每个位添加进位，则结果相同）。最低有效位的加法：

NEW carry:    x00
carry:        010
             +
part. res.:   110
             -----
              xx0

二进制加法：

NEW carry:    100
carry:        010
             +
part. res.:   110
             -----
              x00

第三位加法：

NEW carry:      100
carry:          010
               +
part. res.:     110
               -----
new part. res.  100

现在 carry = NEW carry, part. res. = new part. res.，我们再次进行相同的迭代。

对于最低有效位（LSB）

NEW carry:    x00
carry:        100
             +
part. res.:   100
             -----
              xx0

对于第二个比特：

NEW carry:    000
carry:        100
             +
part. res.:   100
             -----
              x00

第三位：

NEW carry:   1000 --> 000 since we are working with 3 bits only
carry:        100
             +
part. res.:   100
             -----
              000

现在NEW carry为0，所以我们已经完成了计算。最终结果是0b000（溢出）。

我确定我没有发现任何东西。现在让我们看看如何从发布的代码中实现相同的流程：

partial result是没有carry的结果，这意味着当x和y在同一位置具有不同的位时，这些位的总和将为1。如果相同的位是相同的，则结果将为0（1+1 => 0，carry 1和0+0 => 0，carry 0）。

因此，partial result是x ^ y（请参见XOR操作的属性）。在发布的代码中，它是x = x ^ y;。

现在让我们来看一下进位（carry）。只有当两个二进制位都是1时，我们才会从单个二进制位加法中得到进位。因此，在以下表达式中，将设置进位位为1的位被标记为1：x & y（仅在相同位置上设置的位将保持为1）。但是，进位应该添加到下一个（更高位）二进制位！

carry = (x & y) << 1; // in the posted code it is y = carry << 1

迭代会一直执行，直到carry为0（就像我们的例子一样）。

- Alex Lop.