-
Notifications
You must be signed in to change notification settings - Fork 0
/
aplusb.txt
62 lines (49 loc) · 1.89 KB
/
aplusb.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。
分析:
当然,该问题应该是通过位运算来解的。
1)二进制数:2+1 ==> 10
+ 01
------
11
得出:3。显然通过&运算得出的答案是正确的。
2)如果会出现进位的情况,结果可能就会有问题了。
如:2+2 ==> 10
+ 10
------
10
结果就不正确了。
3) 通过上面的分析,是不是就会想到,应该分两步:
先不考虑进位
2+2 ==> 10
+ 10
---------
00
然后加上进位值:100
就相当于
00
+ 100
----------
100
结果不就对了吗!
4)总结:可以通过^运算来模拟不考虑进位的相加,& 然后 左移一位(<<)来模拟进位运算。
int aplusb (int a, int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
return aplusb(a^b, (a&b) << 1);//由于 << 比 & 运算更优先,所以得括号。
}
分析看看对不对:
5 + 6:
==> 101 101
^ 110 & 110
------- ---------
011 100
相当于: 011 + 1000 ==> 3 + 8
==> 011 011
^ 1000 & 1000
------- ---------
1011 0000
由于b=0,return a ==> 11。 对头!!!