LintCode A+B Problem Python
2019-06-30 本文已影响0人
流浪山人
Description：
Write a function that add two numbers A and B.
Clarification
Are a and b both 32-bit integers?
Yes.
Can I use bit operation?
Sure you can.
解析
这个题目主要考察了基本功，包括二进制，位运算，迭代
解题思路
这道题考察的应该就是底层二进制是如何实现数字的加减的。
首先考虑把十进制数转化成二进制树。举例说明，譬如3+6；
3-> 0000 0011
6-> 0000 0110
按位操作运算中，没有涉及进位的直接运算符。因此考虑结合
a^b(不进位加法)
(a&b)<<1(用于表示进位的位置)
我们考虑我们在做加法的时候，是不是先把两个数按照不进位的加法进行运算（a^b），然后再在进位的位置加1((a&b)<<1).
所以我理解，a&b)<<1这一步就像扫描一样， 从最低位向最高位进行扫描，直到没有进位为止（（a&b）<<1的结果为0）
具体我们看这个实例：
- (a)3-> 0000 0011
(b)6-> 0000 0110 - a^b= 0000 0101
(a&b<<1)0000 0100 (恰好是第二位由于1^1造成的进位，导致第三位要加1，那么由于这个+1会不会造成第四位的进位呢？所以还需要递归下去) - a^b= 0000 0001
(a&b<<1)0000 1000 - a^b= 0000 1001
(a&b<<1)0000 0000
至此，递归结束了，因为第二项为0了，所以最终结果就是 0000 1001 转化为十进制为9
为小白科普下位运算：
| 操作 | 运算符符号 | 中文名称 | 描述 |
|---|---|---|---|
| ~x 或 not x | ~ 或 not | 按位求反 | 对x的各二进制取反，即把1变成0，把0变成1。等效于 -(x+1) |
| x << y | << | 左移 | 将x的各二进位全部向左移动y位，相当于在x的二进制位后面加y个0 。 等效于 x * 2**y |
| x >> y | >> | 右移 将x的各二进位全部向右移动y位，相当于将x的二进制位前y位切除 。等效于x / 2**y (取整) | |
| x & y 或 x and y | & 或 and | 按位与 | 只有x和y对应二进制位都为1，该位结果为1否者为0。对于二进制位长度不一样， 在前面添0补齐。 |
| x ^ y | ^ | 按位异或 | x和y对应二进制位相异，该位置结果为1 否者为0， 对于二进制位长度不一样 ，在前面添0补齐。 |
| x | y 或 x or y | 或 or | 按位或 | 只要x和y对应二进制位有一个为1，该位结果为1否者为0 ，对于二进制位长度不一样， 在前面添0补齐。 |
最终Python3 代码如下：实测负数会有问题，后续改进
def aplusb(a,b):
if a==0:
return b
elif b==0:
return a
else:
s=a^b
t=(a&b)<<1
return aplusb(s,t)
a=int(input("first number:"))
b=int(input("second number:"))
print(aplusb(a,b))
