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.
解法一
思路：這里用到了一個半加法的思想, 即兩位單獨(dú)的位相加其結(jié)果可以用異或得到, 進(jìn)位可以用與得到. 然后對于兩個數(shù)字來說同樣可以延伸這個思想.
舉個例子: 11+5, 其二進(jìn)制形式為11: 1011, 5: 0101
那么兩個位置都為1的地方就需要進(jìn)位, 所以進(jìn)位值就為0001. 原位置兩個數(shù)相加的結(jié)果為那個位置值的異或即1110, 即兩個位置值如果不一樣就為1, 一樣的話要么兩個位置原來值都為0結(jié)果也為0, 要么進(jìn)位, 那么結(jié)果依然是0.
接下來就要把進(jìn)位位和下一位相加, 所以進(jìn)位值左移一位,即0001變?yōu)?010, 重復(fù)上面操作可得新的進(jìn)位值為0010, 原位置異或(即相加)結(jié)果為1100奉芦，而1110和0010相與之后饱苟，變?yōu)?010，左移一位藻茂，是0100呀邢，依次繼續(xù)壁晒。
繼續(xù)重復(fù)上面操作直到進(jìn)位為0, 可得到最終結(jié)果10000, 即16
class Solution {
public:
int getSum(int a, int b) {
int r = b;
for(;a;b=r){
r^=a;//把每次a和b的異或賦值給r琢融，然后再賦值給 b，類似于1110雁竞，1100
a=(a&b)<<1;//每次 a與 b的相與左移一位钦椭，賦值給 a，類似于0010碑诉，0100
}
return r;
}
};
這種思想也可以有另一種寫法彪腔。
int getSum(int a, int b){
while(a!=0){
int temp=(a&b)<<1;
b^=a;
a=temp;
}
return b;
}
