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

问题内容：

我试图解决一个老问题：

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

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

对于任意底数的a + b，我们可以将加号视为两个部分：1. a + b，不带进位；2. + 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;
    }
};

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

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

问题答案：

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

...11100

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

...00100

它只是0在左侧重复。

您的加法问题是

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

运营商^，<<以及&有没有麻烦无穷多个二进制数字计算，但问题是，有无限多的承载，而你计算它们 一次一个数字 。这将永远不会结束。

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

在C / C ++中，您不会遇到此问题，因为例如，如果int是32位，则除最右边的31位之外的所有数字都被折叠为一个位，因此它会将其余的全部一旦。

但是，从技术上讲，将an左移的意义int是将值表示为整数，而不是位模式，因此，如果两个最高有效位不同，则会调用
未定义的行为carry，因为这carry << 1会产生溢出）。

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

微信关注