A+B问题

源代码：https://github.com/ianxin/Algorithm/tree/master/src

问题描述：

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。

思路：

a+b可以分为三步来，比如a=3,b=2

a的二进制是0011， b的二进制是0010，如果不考虑进位a+b的结果为0001。
只考虑进位，结果是0011+0010=0010
将该进位左移一位，变为00100
将00100再与0001进行异或，得到00101，即十进制下等于5
结束

常规 Python 解法如下：

#！/usr/bin/env python3
# -*- coding utf-8 -*-
"""
    @param a: The first integer
    @param b: The second integer
    @return:  The sum of a and b
    异或=不考虑进位的加法
    与=只考虑进位
    """
    def aplusb(a, b):
        # write your code here, try to do it without arithmetic operators.
        if b == 0:
            return a
        if a == 0:
            return b
        while b:
            carry = (a&b)<<1 
            a = a ^ b
            b = carry
        return a

但是，此解法在数据较大时运行时间过长，无法通过测试。

更改后的解法如下：

#！/usr/bin/env python3
# -*- coding utf-8 -*-
def aplusb(a, b):
    # write your code here, try to do it without arithmetic operators.
    limit = 0xfffffffff
    while b:
        a, b = (a ^ b) & limit, (a & b) << 1
    return a if a & 1 << 32 == 0 else a | (~limit)

参考资料