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;
    }
};

不知道具体应该问什么，基本上都是这样的问题：

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

Answer 1

问题是负数，或者它们的表示方式。在 Python 中，整数具有任意精度，而 C++ 整数是 32 位或 64 位。所以在 Python 中，你必须处理负数，例如分别做减法，或者手工限制位数

Answer 2

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

...11100

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

...00100

只是向左重复 0。

你的加法问题是

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

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

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

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

但是，从技术上讲，左移 int 的含义是将值作为整数而不是位模式，因此您正在调用 未定义的行为 如果两个最高有效位 carry 不同，因为那样 carry << 1 会产生溢出）。

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

Answer 4

如果禁止 1 位二进制数学运算 (^)，请使用一元运算！

from itertools import chain

def unary(x):
    "Unary representation of x"
    return ''.join(['x' for _ in range(0,x)])

def uplus(x, y):
    "Unary sum of x and y"
    return [c for c in chain(x,y)]

def plus(i, j):
    "Return sum calculated using unary math"
    return len(uplus(unary(i), unary(j)))

Answer 5

我的解决方案：

def foo(a, b):
"""iterate through a and b, count iteration via a list, check len"""
    x = []
    for i in range(a):
            x.append(a)
    for i in range(b):
            x.append(b)
    print len(x)

如前所述，按位更好。

Answer 6

那是因为 python 通常不使用 32 位有符号整数。

参见：ctypes.c_int32

接受的解决方案：

class Solution:
"""
@param a: The first integer
@param b: The second integer
@return:  The sum of a and b
"""
def aplusb(self, a, b):
    import ctypes
    a = ctypes.c_int32(a).value
    a = ctypes.c_int32(a).value
    while b != 0:
        carry = ctypes.c_int32(a & b).value
        a = ctypes.c_int32(a ^ b).value
        b = ctypes.c_int32(carry << 1).value

    return a

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

A + B without arithmetic operators, Python vs C++

python

c++

algorithm

bit-manipulation