用位运算实现加法也就是计算机用二进制进行运算，32位的CPU只能表示32位内的数，这里先用1位数的加法来进行，在不考虑进位的基础上，如下
- 1 + 1 = 0
- 1 + 0 = 1
- 0 + 1 = 1
- 0 + 0 = 0
很明显这几个表达式可以用位运算的“^”来代替，如下
- 1 ^ 1 = 0
- 1 ^ 0 = 1
- 0 ^ 1 = 1
- 0 ^ 0 = 0
这样我们就完成了简单的一位数加法，那么要进行二位的加法，这个方法可行不可行呢？肯定是不行的，矛盾就在于，如何去获取进位？要获取进位我们可以如下思考：
- 0 + 0 = 0
- 1 + 0 = 0
- 0 + 1 = 0
- 1 + 1 = 1
- //换个角度看就是这样
- 0 & 0 = 不进位
- 1 & 0 = 不进位
- 0 & 1 = 不进位
- 1 & 1 = 进位
正好，在位运算中，我们用“<<”表示向左移动一位，也就是“进位”。那么我们就可以得到如下的表达式
- //进位可以用如下表示：
- (x&y)<<1
到这里，我们基本上拥有了这样两个表达式
- x^y //执行加法
- (x&y)<<1 //进位操作
我们来做个2位数的加法，在不考虑进位的情况下
- 11+01 = 100 // 本来的算法
- // 用推算的表达式计算
- 11 ^ 01 = 10
- (11 & 01) << 1 = 10
- //到这里 我们用普通的加法去运算这两个数的时候就可以得到 10 + 10 = 100
- //但是我们不需要加法，所以要想别的方法，如果让两个数再按刚才的算法计算一次呢
- 10 ^ 10 = 00
- (10 & 10) << 1 = 100
到这里基本上就得出结论了，其实后面的那个 “00” 已经不用再去计算了，因为第一个表达式就已经算出了结果。
继续推理，直至进位补偿为0。
/**
* 两个正整数相加
*
* @param a
* @param b
* @return
*/
public static int aplusb(int a, int b) {
//用异或模拟不带进位的加法
int xor = a ^ b;
//用按位与模拟是否进位，左移1位代表进位补偿
int and = (a & b) << 1;
//进位补偿不断左移直至为0，则运算停止
while (and != 0) {
//不带进位加法
int sum = xor ^ and;
//获得进位补偿
and=(xor&and)<<1;
xor=sum;
}
return xor;
}
/**
* 两个正整数相加的递归算法
*/
public static int aplusbPro(int a,int b) {
if(b==0) {
return a;
}
return aplusbPro(a^b,(a&b)<<1);
}
/**
* 实现整数的相乘
*/
public static int amultibPro(int a,int b) {
int sum=0;
while(b!=0) {
if((b&1)!=0)//取最后一位 是否为0
sum=aplusb(a,sum);
a<<=1;
b>>=1;
}
return sum;
}
/**
* 递归实现整数相乘
*/
public static int amultib(int a,int b) {
return b==1?a:aplusb(amultib(a,b-1),a);//a*(b-1)+a
}测试发现：基本的算数运算在计算机底层其实就是通过位运算完成的，因此位运算实现的基本运算的效率和运算符等同
例如加法运算
乘法运算，在计算机底层会对被乘数，乘数做优化。当乘数大于被乘数时，会交替两者的位置，以减少运算次数，提升运算速度
优化前：
优化后
相关文章：1.用位运算实现四则运算之加减乘除
2.位运算 实现加法
3.用位运算实现四则运算之加减乘除（用位运算求一个数的1/3）