原理: 位运算(&与、|或、~非、^异或)
对于二进制的加法运算如下(先不考虑进位):
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
这两个结果是非进位与进位的结果,需要将二者继续相加,但是发现当其中某一个结果为0时,也就没有继续加的必要了,那么 10 (2) 就是答案。
如果5 + 3 呢 ?按照上边的步骤:
101 ^ 11 = 110
(101 & 11) << 1 = 10
说明没进位部分是 110, 进位部分是 10,加起来是 1000(也就是 8)那不妨我们再按照这样的方法来一遍,
110 + 10 = ?
110 ^ 10 = 100
(110 & 10) << 1 = 100
好吧,还没完,继续
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);
}