澄清算法的解决方案

Question

我正在处理如下问题：

“编写一个添加两个数字的函数，不应该使用+或任何算术运算符。

在基座10中，把两个数相加，则可以在加入过程分成两个步骤：

1）加法而不携带

2）只有结转值

添加两个一起。解决方案基本上是这样做的，但是在1）的值和2）的值上递归，直到没有更多的携带值。我不明白这个直觉 - 我们怎么知道最终结转的价值将是零？

下面是解决方案：

int Add(int x, int y) 
{ 
    if (y == 0) 
     return x; 
    else 
     return Add(x^y, (x & y) << 1); 
} 

Answer 1

如果我们使用整数表示具有固定数量的比特（例如，32位整数）的，那么我们可以推论如下：

在任何给定Add的调用中，假设y结束于n零值位。 （例如，如果y的二进制表示中1000结尾，则Ñ为3）

然后x & y结束在至少n零值比特，因为它将具有零值比特无论y确实。

而且(x & y) << 1结束在至少Ñ   +   1个零值比特的，因为它转变一切向左并增加了一个零位结束。 （例外：如果y == 0，则零位的数量是“最大值”，并且这个移位是空操作，但是在那种情况下，我们不会达到else）。

因此，每个递归调用增加尾随零值位的数量至少为1。由于我们假设有一个固定的位数，这意味着y最终会变成零，因为非零位从开始移位。

---

当它发生时，该算法仍然是正确的，即使我们使用了一个无符号整数表示，允许位的无限数量的，但在这种情况下，它是一个有点棘手显现。关键的观察是：

• 上述说法，每个递归调用增加y尾随零值比特的数量，仍然成立。所以如果y不是最终变为零，那么它必须无限制地增长。
• x和y的总和从递归调用到下一个递归调用是不变的;和x永远不会变成负数（因为整数表示甚至不支持）;所以y永远不会超过那个总和。

这两个事实合起来表明y最终必须为零。