問題：
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
大意：
計算a和b兩個整數(shù)的和盟蚣，但是不能用+或-運算符鼓拧。
比如：
給出 a = 1 和 b = 2，返回 3.
思路：
這道題乍看之下很簡單损同，計算兩個數(shù)之和嘛，但問題在于不能直接使用加號和減號驾锰，這就尷尬了扮碧，不過如果不這樣，也稱不上一道題了堤瘤。其實對于運算玫芦，我們知道計算機本身就是沒有什么加減乘除的，一切都是二進(jìn)制在進(jìn)行一些位運算本辐，所以這里很顯然的一個思路也就是轉(zhuǎn)換成位運算姨俩，當(dāng)然如果你本來就知道加法的實現(xiàn)原理，那也可以直接拿來做了师郑。
我們先看個位數(shù)的二進(jìn)制運算：
1 + 1 = 10环葵；
1 + 0 = 1；
0 + 1 = 1宝冕；
0 + 0 = 0张遭。
如果我們用^，也就是位異或運算來做：
1 ^ 1 = 0地梨；
1 ^ 0 = 1菊卷；
0 ^ 1 = 1；
0 ^ 0 = 0宝剖。
其實觀察可以看到洁闰，異或和直接的加唯一結(jié)果有區(qū)別的就是1+1這一條，但是換個想法万细，1+1是要進(jìn)位的扑眉，進(jìn)位后個位上還是變成0了，這樣就一樣了赖钞，只不過還需要有一個進(jìn)位操作腰素，而對于二進(jìn)制，只有都是1的時候才會進(jìn)位雪营，這立馬就可以聯(lián)想到“與”操作了對不對：
1 & 1 = 1弓千；
1 & 0 = 0；
0 & 1 = 0献起；
0 & 0 = 0洋访。
既然是進(jìn)位，我們當(dāng)然要將得出來的結(jié)果進(jìn)一位谴餐，這里使用左移運算符就可以了姻政，所以對于1+1這種的做法就是異或加上與的進(jìn)位：
1+1 = 1^1 + (1&1)<<1
當(dāng)然我們還是不能有加號，所以對上那個加法我們還是要使用同樣的方法总寒，這就是遞歸了扶歪，那要到什么時候為止呢，從邏輯上來說，到不再有進(jìn)位就可以了善镰。
現(xiàn)在我們看一個二位數(shù)的加法：11+ 10 = 101
首先11^10 = 01妹萨，
然后11&10 = 10，左移一位得100炫欺，
現(xiàn)在有進(jìn)位乎完，那么繼續(xù) 01+100，
01^100 = 101品洛，
01&100 = 000树姨，
這時候與操作后的結(jié)果為0了，可以停止運算了桥状，最后的的結(jié)果應(yīng)該是101帽揪，答案正確。說明思路是對的辅斟。
代碼（Java）
public class Solution {
public int getSum(int a, int b) {
if (b == 0) return a;
int sum,up;
sum = a^b;
up = (a&b)<<1;
return getSum(sum, up);
}
}
代碼很簡單转晰，遞歸調(diào)用，在每次調(diào)用中都先檢查進(jìn)位的計算是不是為0了士飒，也就是是不是沒有進(jìn)位了查邢，如果沒有了說明異或運算就是最終結(jié)果了亩冬，如果還有進(jìn)位就繼續(xù)算下去拂檩，算異或和與之后的左移然后繼續(xù)調(diào)用。
看來這些看似理所當(dāng)然的最簡單的運算符校摩，內(nèi)里的門道也是需要了解清楚的芳撒。
合集：https://github.com/Cloudox/LeetCode-Record
