python - A + B 没有算术运算符，Python vs C++

Question

我试图解决一个老问题:

Write a function that add two [integer] numbers A and B. You should not use + or any arithmetic operators.

最好的解决方案是这样的，引自“LintCode-A+B Problem”:

For a + b in any base, we can treat the plus as two part: 1. a + b without carry; 2. the carry generated by a +b. The a+b then equals to part 1 plus part 2. If part1+part2 generates more carry, we can then repeat this procedure, until there is no carry.

我能理解这个算法并且一切看起来都很好，所以我在 lintcode 上进行了测试代码粘贴在下面。

class Solution:
    """
    @param a: The first integer
    @param b: The second integer
    @return:  The sum of a and b
    """
    def aplusb(self, a, b):

        while b != 0:
            carry = a & b
            a = a ^ b
            b = carry << 1

        return a

但令人惊讶的是，它在测试用例 [100, -100] 中给了我 Time Limit Exceeded 错误。所以我在本地运行它并为每个循环打印 a、b:

(-8, 8)
(-16, 16)
(-32, 32)
(-64, 64)
(-128, 128)
(-256, 256)
(-512, 512)
(-1024, 1024)
(-2048, 2048)
(-4096, 4096)
(-8192, 8192)
(-16384, 16384)
(-32768, 32768)
(-65536, 65536)
(-131072, 131072)
...

计算是正确的，所以我认为这个算法不适用于这样的输入，但是当我用 C++ 编写相同的算法时，它就可以了:

class Solution {
public:
    int aplusb(int a, int b) {
        while (b!=0){
            int carry = a & b;
            a = a^b; 
            b = carry << 1;
        }
        return a;
    }
};

我不知 Prop 体应该问什么，基本上问题是:

1. 为什么 C++ 给出正确的输出 0 而 Python 没有？
2. 如果我使用 Python，如何修改此算法以使其正常工作？

Answer 1

-4 的二进制 2 的补码表示是

...11100

是的，我的意思是无限多1的左边；这是一个二进制重复数字。从技术上讲，4也是重复数字:

...00100

只是重复0在左边。

你的加法问题是

   ...11100
+  ...00100
--------------------
   ...00000

运营商^ , << , 和 &用无限多的二进制数字计算没有问题，但问题是有无限多的进位，而您一次计算一个数字。这永远不会结束。

因此，您必须认识到该算法何时会陷入这种情况并采取其他措施来解决此问题。

---

你不会在 C/C++ 中遇到这个问题，因为，例如，如果 int是 32 位，那么除了最右边的 31 位之外的所有数字都被折叠成一个位，所以它会一次完成剩余的进位。

但是，从技术上讲，int 左移的含义是根据值作为整数，而不是作为位模式，所以如果两个最高有效位 carry，您将调用 未定义行为永远不同，因为那时carry << 1会产生溢出)。