原理: 位運算(&與证九、|或、~非瓷患、^異或)
對于二進制的加法運算如下(先不考慮進位):
1 + 0 = 1
1 + 1 = 0
0 + 1 = 1
0 + 0 = 0
有木有很熟悉酗宋,這是異或(^)運算呀,a ^ b东抹,如果只考慮進位呢:
1 + 0 = 0
1 + 1 = 1
0 + 0 = 0
0 + 1 = 1
之后蚂子,我們需要把計算結果左移(<<)一位,放到進位處缭黔,即上邊的計算可以看做 (a & b)<< 1
如果拿 1 + 1 來看:
a ^ b = 0
(a & b) << 1 = 10
這兩個結果是非進位與進位的結果食茎,需要將二者繼續(xù)相加,但是發(fā)現(xiàn)當其中某一個結果為0時馏谨,也就沒有繼續(xù)加的必要了别渔,那么 10 (2) 就是答案。
如果5 + 3 呢 ?按照上邊的步驟:
101 ^ 11 = 110
(101 & 11) << 1 = 10
說明沒進位部分是 110哎媚, 進位部分是 10喇伯,加起來是 1000(也就是 8)那不妨我們再按照這樣的方法來一遍,
110 + 10 = 拨与?
110 ^ 10 = 100
(110 & 10) << 1 = 100
好吧稻据,還沒完,繼續(xù)
100 ^ 100 = 0
(100 & 100) << 1 = 1000
誒~有一部分為0了买喧,就它了(1000)正好是8捻悯!從上邊的分析過程,就是一個遞歸淤毛,算法這東西今缚,自己琢磨琢磨吧,代碼提供在下方:
public int aplusb(int a, int b) {
if (a == 0 && b == 0) {
return 0;
} else if (a == 0) {
return b;
} else if (b == 0) {
return a;
}
return aplusb((a & b) << 1, a ^ b);
}