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

Question

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

def getSum(self, a, b):

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

    return a ^ b

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

编辑：这是讨论的代码修复。

Answer 1

Python3个有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 的任何位打开与 b 的添加 1 位之一对齐，因此 a & b 始终为真，因此循环永远运行。

Answer 2

我猜这是一道作业题，所以我不想只给你一个有效的函数 --- 你会通过努力学习更多。

问题源于负整数的存储方式。出于说明目的，假设您正在处理 4 位有符号整数（而不是 32 位有符号整数或其他）。数字 +1 是 0001。数字 -1 是 1111。您应该可以坐下来用笔和纸手动运行使用这两个数字的函数。答案当然应该是 0000，但我认为您会通过使用笔和纸处理这个简化的案例来发现您的代码出了什么问题。

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

Infinite loop while adding two integers using bitwise operations?

python

bit-manipulation

bitwise-operators

python-3.x