使用位运算实现两数相加

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

看到这个解决方案，我理解了如何进行操作；我可以跟随调试器并在值变化之前预测它们的改变。但是经过多次演练后，我仍然不理解为什么会发生这种情况。如果这在面试中出现，我将只能依靠记忆来解决问题，而不是真正理解算法的工作原理。

有人能解释一下为什么我们在某些点上使用特定的运算符以及这些总数应该表示什么吗？ 我知道代码中已经有注释，但显然我还是缺少了一些东西...

- user3175088

---

@MickyD 电脑已经有了程序，那么为什么还要学习编程呢？毕竟，我们做的大部分事情都已经完成了，对吧？ - spender

@spender 别胡说八道。 - user585968

@harold "没有问题需要解决" - user585968

我投票关闭此问题，因为它是一道面试题；没有问题需要解决；而且它只会吸引那些想要展示自己聪明才智的人，正如赞同、评论和当前答案所显示的那样。[ask] - user585968

@MickyD 那不是一个关闭原因。Ukkonen后缀树算法的流行解释也不是一个“要解决的问题”。当然，这个问题本可以更好地构建。 - harold

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 中。这些进位被正确地向左移动一列，就像你在纸上做加法一样。重复这个过程直到不再存在需要考虑的进位位。

简要来说，这个算法执行加法的方式就像我们在纸上做加法一样，不同的是它并不是从右往左依次计算每一位数，而是同时计算所有位数。

- Prune

---

<= 可能有点令人困惑。也许使用算法伪代码中经常看到的 <- 会更清晰明了。 - גלעד ברקן

@Prune，谢谢您的解释！这让我一切都恍然大悟！谢谢！ - user3175088

@Prune 我认为你在代码片段的第二行应该放置一个异或运算符，而不是加法运算符？ - njuffa

Answer 2

十进制算术比二进制算术更加复杂，但是也许比较一下可以帮助理解。

通常教授的加法算法是逐位相加，需要时要记得“进位一”。在上述算法中，实际情况并非如此——所有数字都会被相加并允许溢出，然后所有进位都被收集起来，以便在下一步全部应用。在十进制中，它看起来像这样：

123456
777777
------ +
890123
001111 << 1
011110
------ +
801233
010000 << 1
100000
------ +
901233
000000 done

在二进制算术中，不带进位的加法就是异或。

- harold

Answer 3

这里涉及到的是关于内存中二进制数学的案例： https://www.wikihow.com/Add-Binary-Numbers 通常在使用C#进行编程时，你不需要过多关注“它在内存中的表示方式”的层面。有55%的情况下，这样做并不值得努力；有40%的情况下，直接使用内置函数更好；而剩下的5%，你应该问问自己为什么不用原生C++、汇编语言或者其他具备类似低级能力的编程语言来开始。

- Christopher