使用位操作将两个数字相加

Question

我正在解决GeeksForGeeks的以下练习问题：

编写一个函数 Add() 返回两个整数之和。该函数不应使用任何算术运算符（+、++、–、-、.. 等）。

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 中。这些进位正确地向左撞了一列，就像你在纸上做加法一样。继续这样做，直到没有更多的进位需要担心。

简而言之，这与您或我在纸上所做的一样多，不同的是，它不是从右到左工作，而是并行处理所有位。