在Python 3中使用按位运算添加两个整数时的无限循环

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

Python 3具有任意精度的整数("bignums").这意味着任何时候x都是负数,x << 1将产生x两倍幅度的负数.从右侧移入的零将使数字越来越大.

在二进制补码中,正数具有0最高位,负数具有1最高位.这意味着,当只有一个a而且b是负数时,顶部的a和b将会有所不同.因此,x将为正(1 & 0 = 0)y并将为负(1 ^ 0 = 1).因此,new a将为positive(x<<1),而new b将为negative(y).

现在:任意精度负整数实际上具有无限数量的前导1位,至少是数学上的.所以a是一个越来越大的正数,每次迭代扩展2. b不断变得越来越领先1位加入能进行按位&和^使用a.因此,无论a打开的位是否与其中一个1位相加b,所以a & b总是如此,因此循环将永远运行.