版權(quán)聲明：本文參考網(wǎng)絡(luò)文章湃望。
難度：普通
要求：
給出兩個(gè)整數(shù)a和b, 求他們的和, 但不能使用 +等數(shù)學(xué)運(yùn)算符挺身。
** 注意事項(xiàng)
你不需要從輸入流讀入數(shù)據(jù)态罪，只需要根據(jù)aplusb的兩個(gè)參數(shù)a和b微宝，計(jì)算他們的和并返回就行添怔。
說(shuō)明
a和b都是 32位
整數(shù)么废赞？
是的
我可以使用位運(yùn)算符么徽龟？
當(dāng)然可以
樣例如果 a=1并且 b=2，返回3
思路：
用位運(yùn)算實(shí)現(xiàn)加法也就是計(jì)算機(jī)用二進(jìn)制進(jìn)行運(yùn)算唉地，32位的CPU只能表示32位內(nèi)的數(shù)据悔，這里先用1位數(shù)的加法來(lái)進(jìn)行，在不考慮進(jìn)位的基礎(chǔ)上耘沼，如下
1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0
很明顯這幾個(gè)表達(dá)式可以用位運(yùn)算的“^”來(lái)代替极颓，如下
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
這樣我們就完成了簡(jiǎn)單的一位數(shù)加法，那么要進(jìn)行二位的加法群嗤，這個(gè)方法可行不可行呢菠隆？肯定是不行的，矛盾就在于狂秘，如何去獲取進(jìn)位骇径？要獲取進(jìn)位我們可以如下思考：
0 + 0 = 0
1 + 0 = 0
0 + 1 = 0
1 + 1 = 1
//換個(gè)角度看就是這樣
0 & 0 = 不進(jìn)位
1 & 0 = 不進(jìn)位
0 & 1 = 不進(jìn)位
1 & 1 = 進(jìn)位
正好，在位運(yùn)算中赃绊，我們用“<<”表示向左移動(dòng)一位既峡，也就是“進(jìn)位”。那么我們就可以得到如下的表達(dá)式
//進(jìn)位可以用如下表示：
(x&y)<<1
到這里碧查，我們基本上擁有了這樣兩個(gè)表達(dá)式
x^y //執(zhí)行加法
(x&y)<<1 //進(jìn)位操作
現(xiàn)總結(jié)如下：
定理1：
設(shè)a运敢，b為兩個(gè)二進(jìn)制數(shù)，則a+b = a^b + (a&b)<<1忠售。證明：a^b是不考慮進(jìn)位時(shí)加法結(jié)果传惠。當(dāng)二進(jìn)制位同時(shí)為1時(shí)，才有進(jìn)位稻扬，因此 (a&b)<<1是進(jìn)位產(chǎn)生的值卦方，稱為進(jìn)位補(bǔ)償。將兩者相加便是完整加法結(jié)果泰佳。
定理2：
使用定理1可以實(shí)現(xiàn)只用位運(yùn)算進(jìn)行加法運(yùn)算盼砍。證明：利用定理1中的等式不停對(duì)自身進(jìn)行迭代尘吗。每迭代一次，進(jìn)位補(bǔ)償右邊就多一位0浇坐，因此最多需要加數(shù)二進(jìn)制位長(zhǎng)度次迭代睬捶，進(jìn)位補(bǔ)償就變?yōu)?，這時(shí)運(yùn)算結(jié)束近刘。
class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
if(a==0)return b;
if(b==0)return a;
int x = a^b; //記錄不進(jìn)位數(shù)
int y = (a&b)<<1; //記錄進(jìn)位數(shù)
return aplusb(x,y); //然后遞歸 上述不進(jìn)位結(jié)果 + 進(jìn)位結(jié)果擒贸，最終進(jìn)位為0，則返回最終結(jié)果
}
};
