生活随笔
收集整理的這篇文章主要介紹了
用位运算实现加减乘除
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
聽同學百度二面中，不準用四則運算操作符來實現四則運算。一想就想到了計算機組成原理上學過的。位運算的思想可以應用到很多地方，這里簡單的總結一下用位運算來實現整數的四則運算。
加法運算：
[cpp]?view plaincopy
int?AddWithoutArithmetic(int?num1,int?num2)?? {?? ????if(num2==0)?return?num1;?? ????int?sum,carry;?? ????sum=num1^num2;?? ????carry=(num1&num2)<<1;?? ????return?AddWithoutArithmetic(sum,carry);?? }??
簡化一下：
[cpp]?view plaincopy
int?Add(int?a,int?b)?? {?? ????return?b???Add(a^b,(a&b)<<1)?:?a;?? ????? ? ? ?? }??
上面的思路就是先不計進位相加，然后再與進位相加，隨著遞歸，進位會變為0，遞歸結束。?
非遞歸的版本如下：
[cpp]?view plaincopy
int?Add(int?a,?int?b)?? {?? ????int?ans;?? ????while(b)?? ????{????? ????????ans?=?a^b;?????????? ????????b?=?((a&b)<<1);????? ????????a?=?ans;?? ????}?? ????return?a;?? }???
減法運算：
[cpp]?view plaincopy
?? int?negtive(int?a)????? {?? ????return?Add(~a,?1);?? }?? int?Sub(int?a,?int?b)?? {?? ????return?Add(a,?negtive(b));?? }???
正數乘法運算：
[cpp]?view plaincopy
?? int?Pos_Multiply(int?a,int?b)?? {?? ????int?ans?=?0;?? ????while(b)?? ????{?? ????????if(b&1)?? ????????????ans?=?Add(ans,?a);?? ????????a?=?(a<<1);?? ????????b?=?(b>>1);?? ????}?? ????return?ans;?? }??
整數除法（正整數）
[cpp]?view plaincopy
?? int?Pos_Div(int?x,int?y)?? {?? ????int?ans=0;?? ????for(int?i=31;i>=0;i--)?? ????{?? ?????????? ????????if((x>>i)>=y)?? ????????{?? ????????????ans+=(1<<i);?? ????????????x-=(y<<i);?? ????????}?? ????}?? ????return?ans;?? }??
完整的實現：
[cpp]?view plaincopy
?? ?? ?? ?? #include<iostream>?? #include<cstdio>?? using?namespace?std;?? ?? int?Add(int?a,?int?b)?? {?? ????int?ans;?? ????while(b)?? ????{???? ????????ans?=?a^b;?????????? ????????b?=?((a&b)<<1);????? ????????a?=?ans;?? ????}?? ????return?a;?? }?? ?? ?? int?negtive(int?a)????? {?? ????return?Add(~a,?1);?? }?? int?Sub(int?a,?int?b)?? {?? ????return?Add(a,?negtive(b));?? }?? ?? ?? int?ispos(?int?a?)??? {??? ????return?(a&0xFFFF)?&&?!(a&0x8000);?? }?? int?isneg(?int?a?)??? {??? ????return?a&0x8000;?? }?? int?iszero(?int?a?)?? {??? ????return?!(a&0xFFFF);?? }?? ?? ?? int?Pos_Multiply(int?a,int?b)?? {?? ????int?ans?=?0;?? ????while(b)?? ????{?? ????????if(b&1)?? ????????????ans?=?Add(ans,?a);?? ????????a?=?(a<<1);?? ????????b?=?(b>>1);?? ????}?? ????return?ans;?? }?? ?? ?? int?Multiply(int?a,int?b)?? {?? ????if(?iszero(a)?||?iszero(b)?)?? ????????return?0;?? ????if(?ispos(a)?&&?ispos(b)?)?? ????????return?Pos_Multiply(a,?b);?? ????if(?isneg(a)?)?? ????{?? ????????if(?isneg(b)?)?? ????????{?? ????????????return?Pos_Multiply(?negtive(a),?negtive(b)?);?? ????????}?? ????????return?negtive(?Pos_Multiply(?negtive(a),?b?)?);?? ????}?? ????return?negtive(?Pos_Multiply(a,?negtive(b))?);?? }?? ?? ?? int?Pos_Div(int?x,int?y)?? {?? ????int?ans=0;?? ????for(int?i=31;i>=0;i--)?? ????{?? ?????????? ????????if((x>>i)>=y)?? ????????{?? ????????????ans+=(1<<i);?? ????????????x-=(y<<i);?? ????????}?? ????}?? ????return?ans;?? }?? ?? ?? int?MyDiv(?int?a,?int?b?)?? {?? ????if(?iszero(b)?)?? ????{?? ????????cout?<<?"Error"?<<?endl;?? ????????exit(1);?? ????}?? ????if(?iszero(a)?)?? ????????return?0;?? ????if(?ispos(a)?)?? ????{?? ????????if(?ispos(b)?)?? ????????????return?Pos_Div(a,?b);?? ????????return?negtive(?Pos_Div(?a,?negtive(b))?);?? ????}?? ????if(?ispos(b)?)?? ????????return?negtive(?Pos_Div(?negtive(a),?b?)?);?? ????return?Pos_Div(?negtive(a),?negtive(b)?);?? }??? ?? ?? ?? int?isbig_pos(?int?a,?int?b?)??? {???? ????int?c?=?1;?? ????b?=?(a^b);?? ????if(?iszero(b)?)?? ????????return?0;?? ????while(?b?>>=?1?)?? ????{?? ????????c?<<=?1;?? ????}?? ????return?(c&a);?? }??? ?? ?? int?isbig(?int?a,?int?b?)??? {??? ????if(?isneg(a)?)?? ????{?? ????????if(?isneg(b)?)?? ????????{?? ????????????return?isbig_pos(?negtive(b),?negtive(a)?);?? ????????}?? ????????return?0;?? ????}?? ????if(?isneg(b)?)?? ????????return?1;?? ????return?isbig_pos(a,?b);?? }??
擴展：在不使用*、/、+、-、%操作符的情況下，如何求一個數的1/3？（用C語言實現）
使用位操作符并實現“+”操作
[cpp]?view plaincopy
?? int?add(int?x?,?int?y)?? {?? ????int?res;?? ????while(y)????????? ????{?? ????????res?=?x^y;????????? ????????y?=?((x&y)<<1);???? ????????x?=?res;?? ????}?? ????return?x;?? }?? ?? int?divideby3(int?num)?? {?? ????int?sum?=?0;?? ????while(num?>?3)?? ????{?? ????????sum?=?add(num>>2?,?sum);?? ????????num?=?add(num>>2?,?num&3);?? ????}?? ????if(num?==?3)?? ????????sum?=?add(sum?,?1);?? ????return?sum;?? }??
原理：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
總結
以上是生活随笔為你收集整理的用位运算实现加减乘除的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
