听同学百度二面中，不准用四则运算操作符来实现四则运算。一想就想到了计算机组成原理上学过的。位运算的思想可以应用到很多地方，这里简单的总结一下用位运算来实现整数的四则运算。
加法运算：
[cpp]view plaincopyintAddWithoutArithmetic(intnum1,intnum2) { if(num2==0)returnnum1;//没有进位的时候完成运算 intsum,carry; sum=num1^num2;//完成第一步没有进位的加法运算 carry=(num1&num2)<<1;//完成第二步进位并且左移运算 returnAddWithoutArithmetic(sum,carry);//进行递归，相加 }
简化一下：
[cpp]view plaincopyintAdd(inta,intb) { returnb?Add(a^b,(a&b)<<1):a; /*if(b) returnAdd(a^b,(a&b)<<1); else returna;*/ }
上面的思路就是先不计进位相加，然后再与进位相加，随着递归，进位会变为0，递归结束。
非递归的版本如下：
[cpp]view plaincopyintAdd(inta,intb) { intans; while(b) {//直到没有进位 ans=a^b;//不带进位加法 b=((a&b)<<1);//进位 a=ans; } returna; }
减法运算：
[cpp]view plaincopy//这个和加法一样了，首先取减数的补码，然后相加。 intnegtive(inta)//取补码 { returnAdd(~a,1); } intSub(inta,intb) { returnAdd(a,negtive(b)); }
正数乘法运算：
[cpp]view plaincopy//正数乘法运算 intPos_Multiply(inta,intb) { intans=0; while(b) { if(b&1) ans=Add(ans,a); a=(a<<1); b=(b>>1); } returnans; }
整数除法（正整数）
[cpp]view plaincopy//除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。 intPos_Div(intx,inty) { intans=0; for(inti=31;i>=0;i--) { //比较x是否大于y的(1<<i)次方，避免将x与(y<<i)比较，因为不确定y的(1<<i)次方是否溢出 if((x>>i)>=y) { ans+=(1<<i); x-=(y<<i); } } returnans; }
完整的实现：
[cpp]view plaincopy//加减乘除位运算 //程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现 //在实现除法运算时，用了从高位到低位的减法 //具体如下，算法也比较简单，所以没有作注释 #include<iostream> #include<cstdio> usingnamespacestd; intAdd(inta,intb) { intans; while(b) {//直到没有进位 ans=a^b;//不带进位加法 b=((a&b)<<1);//进位 a=ans; } returna; } //这个和加法一样了，首先取减数的补码，然后相加。 intnegtive(inta)//取补码 { returnAdd(~a,1); } intSub(inta,intb) { returnAdd(a,negtive(b)); } //判断正负 intispos(inta) {//正 return(a&0xFFFF)&&!(a&0x8000); } intisneg(inta) {//负 returna&0x8000; } intiszero(inta) {//0 return!(a&0xFFFF); } //正数乘法运算 intPos_Multiply(inta,intb) { intans=0; while(b) { if(b&1) ans=Add(ans,a); a=(a<<1); b=(b>>1); } returnans; } //乘法运算 intMultiply(inta,intb) { if(iszero(a)||iszero(b)) return0; if(ispos(a)&&ispos(b)) returnPos_Multiply(a,b); if(isneg(a)) { if(isneg(b)) { returnPos_Multiply(negtive(a),negtive(b)); } returnnegtive(Pos_Multiply(negtive(a),b)); } returnnegtive(Pos_Multiply(a,negtive(b))); } //除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。 intPos_Div(intx,inty) { intans=0; for(inti=31;i>=0;i--) { //比较x是否大于y的(1<<i)次方，避免将x与(y<<i)比较，因为不确定y的(1<<i)次方是否溢出 if((x>>i)>=y) { ans+=(1<<i); x-=(y<<i); } } returnans; } //除法运算 intMyDiv(inta,intb) { if(iszero(b)) { cout<<"Error"<<endl; exit(1); } if(iszero(a)) return0; if(ispos(a)) { if(ispos(b)) returnPos_Div(a,b); returnnegtive(Pos_Div(a,negtive(b))); } if(ispos(b)) returnnegtive(Pos_Div(negtive(a),b)); returnPos_Div(negtive(a),negtive(b)); } //比较两个正数的大小（非负也可） intisbig_pos(inta,intb) {//a>b>0 intc=1; b=(a^b); if(iszero(b)) return0; while(b>>=1) { c<<=1; } return(c&a); } //比较两个数的大小 intisbig(inta,intb) {//a>b if(isneg(a)) { if(isneg(b)) { returnisbig_pos(negtive(b),negtive(a)); } return0; } if(isneg(b)) return1; returnisbig_pos(a,b); } 扩展：在不使用*、/、+、-、%操作符的情况下，如何求一个数的1/3？（用C语言实现）
使用位操作符并实现“+”操作
[cpp]view plaincopy//替换加法运算符 intadd(intx,inty) { intres; while(y)//直到没有进位 { res=x^y;//不带进位的加法 y=((x&y)<<1);//进位 x=res; } returnx; } intdivideby3(intnum) { intsum=0; while(num>3) { sum=add(num>>2,sum); num=add(num>>2,num&3); } if(num==3) sum=add(sum,1); returnsum; }
原理：n = 4 * a + b; n / 3 = a + (a + b) / 3; 然后 sum += a, n = a + b 并迭代; 当 a == 0 (n < 4)时，sum += floor(n / 3); i.e. 1, if n == 3, else 0
