兩數(shù)之和
思路
在做 10 進制加法時允趟，例如15 + 6涣楷，我們先將低位相加得到結(jié)果的低位 1 和進位 1，將進位 1 和高位 1 相加就得到了結(jié)果的高位 2，最終的結(jié)果為 21沙峻。所以求加法的過程中怖辆，我們要得到當前位的結(jié)果和進位淑廊。
推廣到二進制猎荠，有
0 & 0 = 0, 0 ^ 0 = 0;
0 & 1 = 0, 0 ^ 1 = 1;
1 & 0 = 0, 1 ^ 0 = 1;
1 & 1 = 1, 1 ^ 1 = 0;
我們發(fā)現(xiàn)兩個二進制位做異或就是相加得到的當前位的結(jié)果碾阁，做與操作就是進位宪睹。
所以嘶居，我們將 a, b 進行異或操作得到當前位的結(jié)果整袁，進行與操作得到進位芋忿，如果進位為0痹仙，則退出循環(huán)，否則將當前步的結(jié)果賦值給 a，將進位左移一位的結(jié)果賦值為 b暴匠。代碼如下：
public int getSum(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
int ans = 0;
int carry = 0;
while (true) {
ans = a ^ b;
carry = a & b;
if (carry == 0) break;
a = ans;
b = carry << 1;
}
return ans;
}
簡化
public int getSum1(int a, int b) {
while(b != 0){
int temp = a ^ b;
b = (a & b) << 1;
a = temp;
}
return a;
}
