感謝部落格:http://blog.csdn.net/itismelzp/article/details/49621741 提供的思路。
要用位運算來實作四則運算,不僅僅要知道&,|,~,^,<>怎麼做,還需要先掌握位運算的幾個運算規律:
1:~n=-(n+1),比如:~3=-4
2:擷取整數n的二進制串中最後一個1:-n&n=~(n-1)&n
3:去掉整數n的二進制串中最後一個1:n&(n-1)。
然後,我們就可以使用正常位運算并結合上面的運算規律來實作四則運算了。
加法:a+b
由a^b可得按位相加後沒有進位的和;
由a&b可得可以産生進位的地方;
由(a&b)<<1得到進位後的值。
那麼 按位相加後原位和+進位和 就是加法的和了,而 a^b + (a&b)<<1 相當于把 + 兩邊再代入上述三步進行加法計算。直到進位和為0說明沒有進位了則此時原位和即所求和。
public int add(int a,intb) {int res=a;int xor=a^b;//得到原位和int forward=(a&b)<<1;//得到進位和if(forward!=0){//若進位和不為0,則遞歸求原位和+進位和
res=add(xor, forward);
}else{
res=xor;//若進位和為0,則此時原位和為所求和
}returnres;
}
減法:a-b
由-b=+(-b),~(b-1)=-b可得a-b=a+(-b)=a+(~(b-1))。把減法轉化為加法即可。
public int minus(int a,intb) {int B=~(b-1);returnadd(a, B);
}
乘法:a*b
先來看一下二進制乘法是怎麼做的:
1011
* 1010
--------
10110 (1011<<1,相當于乘以0010)1011000 (1011<<3,相當于乘以1000)--------
1101110
可以看到,二進制乘法的原理是:從乘數的低位到高位,遇到1并且這個1在乘數的右起第i(i從0開始數)位,那麼就把被乘數左移i位得到 temp_i 。直到乘數中的1周遊完後,把根據各位1而得到的被乘數的左移值們 temp_i 相加起來即得乘法結果。那麼根據這個原理,可以得到實作代碼:這裡要點為:用i記錄目前周遊的乘數位,目前位為1則被乘數左移i位并加到和中,同時i++處理下一位;為0則乘數右移,i++,處理下一位......直到乘數==0說明乘數中的1周遊完了。此時把和傳回即可。
public int multi(int a,intb){int i=0;int res=0;while(b!=0){//乘數為0則結束//處理乘數目前位
if((b&1)==1){
res+=(a<
b=b>>1;++i;//i記錄目前位是第幾位
}else{
b=b>>1;++i;
}
}returnres;
}
除法:a/b
除法的意義就在于:求a可以由多少個b組成。那麼由此我們可得除法的實作:求a能減去多少個b,做減法的次數就是除法的商。
public int sub(int a,intb) {int res=-1;if(a
}else{
res=sub(minus(a, b), b)+1;
}returnres;
}