python - 使用按位运算将两个整数相加时无限循环？

Question

我正在尝试使用 python 代码解决一个问题，这需要我在不使用“+”或“-”运算符的情况下添加两个整数。我有以下代码，非常适合两个正数:

def getSum(self, a, b):

    while (a & b):
        x = a & b
        y = a ^ b
        a = x << 1
        b = y

    return a ^ b

如果输入是两个正整数或两个负整数，这段代码可以完美运行，但当一个数字为正而另一个为负时，它就会失败。它进入无限循环。知道为什么会发生这种情况吗？

编辑:这是 link讨论对此的代码修复。

Answer 1

Python 3 有 arbitrary-precision integers ("bignums") .这意味着任何时候 x为负，x << 1将使x一个两倍大小的负数。从右边移入的零只会使数字越来越大。

在二进制补码中，正数有一个 0在最高位和负数中有一个 1在最高位。这意味着，当只有一个 a和 b为负，a 的最高位和 b会有所不同。因此，x将为正 ( 1 & 0 = 0 ) 和 y将为负 ( 1 ^ 0 = 1 )。因此新的a将是积极的 ( x<<1 ) 和新的 b将为负 ( y )。

现在:任意精度的负整数实际上有无限多个前导 1位，至少在数学上是这样。所以a是一个越来越大的正数，每次迭代扩大 2。 b越来越领先1添加的位能够按位执行 &和 ^与 a .因此 a 的任何位与添加的 1 之一对齐位 b , 所以 a & b始终为真，因此循环永远运行。