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

Question

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

pythonpython-3.xbit-manipulationbitwise-operators

7

我正在尝试使用Python代码解决一个问题，需要我在不使用“+”或“-”运算符的情况下添加两个整数。我有以下代码可以完美地处理两个正数：

def getSum(self, a, b):

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

    return a ^ b

如果输入是两个正整数或两个负整数，则此代码能够完美运行，但当一个数字为正数而另一个数字为负数时会失败。它会进入无限循环。有任何想法为什么会发生这种情况吗？

编辑：这里是链接，讨论了修复此问题的代码。

- Mr Matrix

你使用了哪些测试值来测试 a 和 b？在循环期间打印或观察 a 和 b 的值 - 它们是否落入重复模式？此外，a 或 b 是否为负操作数会有影响吗？ - cxw

3个回答

0

我遇到了同样的问题。更准确地说：只有当一个数字为正数，另一个数字为负数且 positive >= abs(negative) 时，才会出现无限循环。正如 @cvx 所说，这是因为有额外的进位位 - 其他语言忽略溢出，但 Python 将这个额外的 1 添加到数字中，它变得越来越大，而 b 永远不会变成零。

因此，解决方案是使用掩码：让我们忽略这个额外的位：

def getSum(a: int, b: int) -> int:
    mask = 0xffffffff
    while b&mask > 0:
        carry = a & b
        cur_sum = a ^ b
        a = cur_sum
        b = carry << 1

    return a&mask if b>0 else a

同时最后一行非常重要！因为Python也会将1添加到a中，而Python会将其视为负值。我们应该跳过这些位并仅获取a的最后一部分作为正数。

更多信息请参见：https://leetcode.com/problems/sum-of-two-integers/discuss/489210/Read-this-if-you-want-to-learn-about-masks

- Mikhail_Sam

-2

我猜这是一道作业题，所以我不想直接给你一个可行的函数 --- 通过努力去解决问题，你会学到更多。

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

- kloppen

欢迎来到本站，并感谢您的回答！我同意通过实践学习是最好的方式。当您在线时，请查看tour，了解更多有关如何编写可能会获得赞同的答案的信息。祝您愉快！ - cxw

感谢回答kloppen。我从未想要可工作的代码，我只是想理解发生了什么。这不是一道家庭作业问题。 :) - Mr Matrix

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cxw · Accepted Answer

Python 3具有任意精度整数（"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始终为真，因此循环永远运行。