原題
Description
Write a function that add two numbers A and B. You should not use +
or any arithmetic operators.
Clarification
Are a and b both 32-bit
integers?
- Yes.
Can I use bit operation?
- Sure you can.
Example
Given a=1
and b=2
return 3
解題
要求不用算術(shù)運(yùn)算符實(shí)現(xiàn)加法aplusb
食磕,可以使用位運(yùn)算尽棕。
主要是用的異或運(yùn)算實(shí)現(xiàn)。
異或 -> 不進(jìn)位加法
Example
- 不需要進(jìn)位的情況
2 ^ 5
2: 010
5: 101
^ -----
7: 111
- 需要進(jìn)位
2 ^ 6
2: 010
6: 110
^ -----
5: 101
這里第二位計(jì)算的結(jié)果為0
是正確的彬伦,但是并沒有向上一位進(jìn)滔悉。
不進(jìn)位加法結(jié)果:a ^ b
與 -> 進(jìn)位
接下來的問題就是獲取進(jìn)位
首先知道哪些位置需要進(jìn)位,需要進(jìn)位的位置有個(gè)特點(diǎn)就是兩個(gè)數(shù)在該位都為1
单绑,因此可以通過與運(yùn)算得出回官。
Example
2 & 6
2: 010
6: 110
& -----
010
然后只需要把需要進(jìn)位的位置左移一位就可以得到進(jìn)位。
進(jìn)位:a & b << 1
遞歸相加
- 通過異或運(yùn)算得到了不進(jìn)位加法結(jié)果為
a ^ b
- 通過與運(yùn)算得到了進(jìn)位為
a & b << 1
接下來只需要把這兩個(gè)數(shù)加在一起即可搂橙,這時(shí)候可以選擇遞歸調(diào)用aplusb
歉提,問題就變?yōu)檫f歸何時(shí)結(jié)束。
在進(jìn)位的加法過程中,可能產(chǎn)生新的進(jìn)位唯袄,這時(shí)繼續(xù)遞歸需要調(diào)用aplusb
弯屈。繼續(xù)這個(gè)過程,最終進(jìn)位會(huì)變?yōu)?code>0恋拷,此時(shí)結(jié)束遞歸。
最終代碼
class Solution {
public:
/*
* @param a: An integer
* @param b: An integer
* @return: The sum of a and b
*/
int aplusb(int a, int b) {
// write your code here
if (b == 0) return a;
return aplusb(a ^ b, (a & b) << 1);
}
};