c# - 使用位操作添加两个数字

Question

我正在研究 GeeksForGeeks 中的以下练习题:

Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).

C# 中给定的解决方案是:

public static 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;
}

看着这个解决方案，我明白了它的是如何发生的；我可以跟随调试器并在值变化出现之前预测它们。但是在经历了几次之后，我仍然不明白为什么会发生这种情况。如果在面试中出现这个问题，我将不得不依靠内存来解决它，而不是真正理解算法的工作原理。

有人可以帮助解释为什么我们在某些点使用某些运算符以及这些总数应该代表什么？我知道代码中已经有注释，但我显然遗漏了一些东西......

Answer 1

在每次迭代中，您有以下步骤:

carry <- x & y   // mark every location where the addition has a carry
x <- x ^ y       // sum without carries
y <- carry << 1  // shift the carry left one column

在下一次迭代中，x 保存进位的整个总和，进位在 y 中。这些进位被适本地向左撞了一列，就像你在纸上做加法一样。继续这样做，直到不再需要担心进位为止。

非常简单，这与您或我在纸上做的很像，除了，它不是从右到左工作，而是并行处理所有位。