A + B没有算术运算符,Python vs C++

Question

我试图解决一个老问题:

编写一个添加两个[整数]数字A和B的函数.不应该使用+或任何算术运算符.

最好的解决方案是这样的,引自" LintCode-A + B问题 ":

对于任何基数中的+ b,我们可以将加号视为两部分:1.a + b没有进位; 2.由a + b生成的进位.然后a + b等于第1部分加第2部分.如果part1 + part2产生更多进位,我们可以重复此过程,直到没有进位.

我可以理解这个算法,一切看起来都不错,所以我在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在测试用例中给了我错误[100, -100].所以我在本地运行它并为每个循环打印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;
    }
};

我不知道究竟应该问什么,基本上问题是:

1. 为什么C++提供正确的输出0而Python不提供？
2. 如果我使用Python,如何修改此算法以使其工作？

Answer 1

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

...11100

是的,我的确意味着无数1左边的人; 这是二进制重复数字.从技术上讲,4也是一个重复的数字:

...00100

它只是0在左边重复.

你的补充问题是

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

运算符^,<<并且&可以毫无困难地使用无限多个二进制数字进行计算,但问题是存在无限多个进位,并且您一次计算它们一位数.这永远不会完成.

因此,您必须认识到此算法何时会陷入这种情况并执行其他操作以解决此问题.

你不会在C/C++中遇到这个问题,因为,例如,如果int是32位,那么除了最右边的31位数字之外的所有数字都会折叠成一个位,所以剩下的所有数字都会在一旦.

但是,从技术上讲,左移a的意思int是将值作为整数而不是位模式,因此如果两个最高有效位不同,则调用未定义的行为carry,因为这样carry << 1会产生溢出).

Answer 2

问题是负数,或者它们是如何表示的.在Python中,整数有任意精度,而C++ int是32位或64位.因此在Python中,您必须单独处理负数,例如减法,或手动限制位数.

Answer 3

在@Hurkyl的精彩解释之后,我逐步完成了算法,a=4并b=-4使用了python实现无限二的恭维表示的事实:

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位带符号的二进制补码整数.一旦进位位冒出超过最高位,算法就需要暂停.以下似乎有效:

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