没有算术运算符的A+B，Python与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

但令人惊讶的是，它在测试用例中给了我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;
    }
};

我不知道该问什么，基本上问题是：

<为什么C++给出正确的输出^ {< CD3}}，而Python却不呢？
1. 如果我使用Python，如何修改该算法使其工作？

Answer 1

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

...11100

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

...00100

只是在左边重复0。

你的加法问题是

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

运算符^、<<和&在计算无限多个二进制数字时没有问题，但问题是有无限多个进位，而您一次只计算一个数字。这永远不会结束。

因此，你必须认识到这个算法何时会陷入这种情况，并采取其他措施来解释它。

---

<>你在C/C++中没有遇到这个问题，因为，例如，如果{{CD8}}是32位，那么除了最右边的31位数字之外的所有数字都会崩溃成一个比特，所以剩下的所有的都一次携带。

然而，从技术上讲，左移一个int的含义是将值作为整数，而不是位模式，因此，如果两个最重要的位carry永远不同，则调用未定义的行为，因为这样carry << 1将产生溢出）。

Answer 2

根据@Hurkyl的出色解释，我使用python实现了无限二的恭维表示这一事实，逐步完成了a=4和b=-4的算法：

Step 0:

a = ...(0)...000100
b = ...(1)...111100

carry = a & b = ...(0)...000100
a = a ^ b = ...(1)...111000
b = carry << 1 = ...(0)...001000

Step 1:

a = ...(1)...111000
b = ...(0)...001000

carry = a & b = ...(0)...001000
a = a ^ b = ...(1)...110000
b = carry << 1 = ...(0)...010000

Step 2:

a = ...(1)...110000
b = ...(0)...010000

carry = a & b = ...(0)...010000
a = a ^ b = ...(1)...100000
b = carry << 1 = ...(0)...100000

很明显，需要有一个有效的截断来模拟类似于32位有符号2的恭维整数。一旦进位气泡上升超过最高位，算法就需要停止。以下操作似乎有效：

MAX_BIT = 2**32
MAX_BIT_COMPLIMENT = -2**32

def aplusb(a, b):

    while b != 0:
        if b == MAX_BIT:
            return a ^ MAX_BIT_COMPLIMENT
        carry = a & b
        a = a ^ b
        b = carry << 1

    return a

结果：

>>> aplusb(100,-100)
0
>>> aplusb(100,-99)
1
>>> aplusb(97,-99)
-2
>>> aplusb(1000,-500)
500
>>> aplusb(-1000,8000)
7000

Answer 3

问题是负数，或者负数是如何表示的。在Python中，整数具有任意的精度，而C++的It是32位或64位。所以在Python中，必须单独处理负数，例如减法，或者手动限制位的数量。