整数 a 加 b (lintcode:a-b-problem)

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

def aplusb(a, b):
    num_list = []
    num_list.append(a)
    num_list.append(b)
    return sum(num_list)

写一个函数，求两个正整数之和，不得使用 + 等数学运算符，不得使用 sum() 函数。

def aplusb(a, b):
  sum1 = a ^ b
  carry = (a & b) << 1
  while carry:
#    other_sum = sum1 ^ carry
#    carry = (sum1 & carry) << 1
#    sum1 = other_sum
    sum1, carry = sum1 ^ carry, (sum1 & carry) << 1  #:直接赋值，不借助中间变量
  else :
    return sum1

print aplusb(11, 17)

思路和原理：

对数字做运算，除了四则运算之外，也就只剩下位运算了。位运算是针对二进制的，所以我们用二进制和位运算尝试下实现加法。

加法可分为同位相加和进位。

比如 7+18，
第一步，同位相加不进位。个位上7+8等于5（不考虑进位），十位上0+1等于1，最后结果是15。
第二步，进位。7+8有进位，进位结果是10。
第三部，把前面两步结果相加，15+10=25，正好等于7+18的结果。
那么接下来的问题就是尝试用二进制和位运算实现同位相加和进位。

二进制同位相加（不考虑进位）：
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0

很明显可以用位运算的按位异或“^”来代替：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

二进制进位：
0 + 0 无进位
0 + 1 无进位
1 + 0 无进位
1 + 1 有进位

可以用按位与“&”来代替：
0 & 0 无进位
0 & 1 无进位
1 & 0 无进位
1 & 1 有进位

而且在位运算中，我们有"<<"用来左移位，也就是进位。

基于以上，我们有了两个表达式：
x^y #同位相加
(x&y)<<1 #进位操作

把以上两步的结果再用以上的方法相加，如此迭代，当“进位操作”的结果为零的时候，“同位相加”的结果就是最终的结果。

lintcode 原题

资料：
位运算实现加法
位操作实现四则运算

20171231