整数 a 加 b (lintcode:a-b-problem)
2017-12-31 本文已影响0人
v1coder
给出两个整数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 #进位操作
把以上两步的结果再用以上的方法相加，如此迭代，当“进位操作”的结果为零的时候，“同位相加”的结果就是最终的结果。
20171231
