位运算实现加减乘除、求补、比较、正负判断.docx

维唯为为_博客园 博客园 首页 博问 闪存 新随笔 联系 订阅 管理随笔-150 文章-1 评论-5 位运算实现加减乘除、求补、比较、正负判断位运算的思想可以应用到很多地方，这里简单的总结一下用位运算来实现整数的四则运算。1.整数的加法view plain1. int MyAdd(int a,int b) 2. 3. for(int i=1;i;i=1) 4. if(b&i) 5. for(int j=i;j;j= 1) 6. if(a&j) a&=j; 7. else a|=j;break; 8. return a ; 9. 我的思路主要是利用a+1的位运算就是最左端（从第0位开始向左）连续的1变为0，原先a中为0的位置最低那一位变为1。在不同的位上加1，那就是从相应的位开始向左计算，右边不变。下面还有一个网上的思路，我觉得这个更好：view plain1. int AddWithoutArithmetic(int num1,int num2) 2. 3. if(num2=0) return num1;/没有进位的时候完成运算 4. int sum,carry; 5. sum=num1num2;/完成第一步没有进位的加法运算 6. carry=(num1&num2)1;/完成第二步进位并且左移运算 7. return AddWithoutArithmetic(sum,carry);/进行递归，相加 8. 简化一下：view plain1. int Add(int a,int b) b?return Add(ab,(a&b)1):return a; 上面的思路就是先不计进位相加，然后再与进位相加，随着递归，进位会变为0，递归结束。2.整数的减法这个和加法一样了，首先取减数的补码，然后相加。view plain1. int MyMinus(int a,int b) 2. 3. for(int i=1;i&(b&i)=0);i=1); 4. for(i=1;i;i=1) b=i; 5. return MyAdd(a,b); 6. 3.整数的乘法乘法就是将乘数写成(20)*k0 + (21)*k1 + (2 2)*k2 + . + (231)*k31，其中ki为0或1，然后利用位运算和加法就可以了。view plain1. int MyMul(int a,int b) 2. 3. int ans=0; 4. for(int i=1;i;i=1,a=0;i-) 5. 6. /比较x是否大于y的(1i)次方，避免将x与(yi)比较，因为不确定y的(1i)=y) 8. 9. ans+=(1i); 10. x-=(yi); 11. 12. 13. return ans; 14. =加减乘除位运算/ 程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现/ 在实现除法运算时，用了从高位到低位的减法/ 具体如下，算法也比较简单，所以没有作注释#include using namespace std;/ 加法int add(int a,int b )int c;while( c =(a&b)a =(ab);b =(cb0int c =1;b =(ab);if( iszero(b)return0;while( b =1)c bif( isneg(a)if( isneg(b)return isbig_pos( rev(b), rev(a);return0;if( isneg(b)return1;return isbig_pos(a, b);/ 减法int sub(int a,int b )return add(a, rev(b);/ 正数乘法int pos_mul(int a,int b )int c =0x8000;int re = a;while(c=1)&(!(b&c);while( c =1)re =1;if( c&b )re = add(re, a);return re;/ 乘法int mul(int a,int b )if( iszero(a)| iszero(b)return0;if( ispos(a)& ispos(b)return pos_mul(a, b);if( isneg(a)if( isneg(b)return pos_mul( rev(a), rev(b);return rev( pos_mul( rev(a), b );return rev( pos_mul(a, rev(b);/ 正数除法int pos_div(int a,int b)int re =0, temp = b;if( isbig_pos(b, a)return0;dotemp =1;while(!isbig_pos(temp, a);while( isbig_pos(temp, b)re =1;if(!isbig_pos(temp, a)a = sub(a, temp);re = add(re,1);return re;/ 除法int idiv(int a,int b )if( iszero(b)cout error a b)if(isbig(a,b)&(a=b) cout big error endl;if(add(a,b)!=(a+b) cout add error endl;if(sub(a,b)!=(a-b) cout sub error endl;if(mul(a,b)!=(a*b) cout mul error endl;if(idiv(a,b)!=(a/b) cout div error endl;return0;-加法是这样的int add(int a,int b)int c;while(c=a&b) a=ab;b=c1;return ab;乘法是这样的int cheng(int a,int b)int c,i;c=0;for(i=0;i16;i+)if(b&(1i)c=add(c,ai);return c;zv的计算机组成原理学得好,给出了一个思路.我记性不坏,还记得以前曾见过的算法,于是:代码（2005年）32用原码加减交替一位除法进行72运算。要求写出每一步运算过程及运算结果。循环步骤余数（R0 R1）0 初始值00000111左移，商0 000011101 减0011 11011110加0011，商0 00001110（0）左移1位000111002 减0011 11101100加0011，商0 00011100（0）左移1位001110003 减0011 00001000商1 00001000（1）左移1位000100014减0011 11100001加0011，商0 00010001（0）左移1位00100010 R0右移1位00010010所以，商是0010，即2；余数是0001，即1。以及:代码这是一种实现，只能整除，并且肯定有问题：#include unsignedint div (unsignedint a,unsignedint b)int i;unsignedint m =0;for(i =1; i =32; i+)m =(m 31);a = a = b)m = m - b;a = a +1;return a;int main(int argc,char*argv)int a , b;scanf(%d, %d,&a,&b);printf(a = %dn, div(a, b);虽然我和zv的大致思路没问题,但是,注意了,实现除法的算法有很多种.这里,悬赏2000盾盾,寻求其它的除法思路-即便最后没选上,认真参与并讨论的,也有额外的盾盾奖励!-修改了之后的代码,这仅仅是众多算法中的一种而已:代码#include int add (int a,int b)int c;while(c = a & b)a = a b;b = c 1;return a b;unsignedint idiv (unsignedint a,unsignedint b)int i;unsignedint m =0;for(i =1; i =32; i+)m =(m 31);a = a = b)m = add (m,-b);/m = m - b;a = add (a,1);/a = a + 1;return a;int main (int argc,char*argv)int a , b;scanf (%d, %d,&a,&b);printf (a = %dn, idiv(a, b);return0;-琢磨了一个，写得有点匆忙，没做什么优化，先贴上来了，大家给提提意见代码/* SpeedyDivision 算法描述* * 1、接收被除数与除数* 2、如果除数为零，退出* 3、如果被除数等于除数，商置1，余数置0，退出* 4、如果被除数小于除数，商置0，余数置0，退出* 5、如果被除数小于0，作标记，被除数置为其绝对值* 6、如果除数小于0，作标记，除数置为其绝对值* 7、如果除数等于1，商置为被除数的值，余数置0，商取标记的符号，退出* 8、下面进行快速移位计算* * A、快速移位算法的循环次数为 被除数数据类型的位数 / _MV_BITS* B、计算每次移位需要取得的被除数最高_MV_BITS位的掩码* 如：* 当 _MV_BITS = 8 时，假设 sizeof( int ) * 8 = 32 位* 则掩码为 0xFF000000* C、进入主循环* D、余数缓存左移_MV_BITS位* 余数缓存低_MV_BITS位填入被除数最高_MV_BITS位* 被除数左移_MV_BITS位* 商左移_MV_BITS位* E、如果余数缓存的值小于除数，则回到D* F、如果余数缓存的值大于除数，则在余数缓存中减去除数一次，商增加1，再判断余数缓存与除数的大小，直到余数缓存小于除数* 相当于如下循环：（注1）* while( n_remainder = n_divisor ) * n_remainder = add( n_remainder, -n_divisor );* n_quotient = add( n_quotient, 1 );* * G、判断主循环结束条件属否到达（是否已到达了算法要求的循环次数被除数数据类型的位数 / _MV_BITS）* 如果没到达，回到D* H、结束循环* * 9、商及余数取标记的符号，输出之* 10、结束* * * 注1：* F步骤的移位实现如下* * 如果 n_remainder = n_divisor，则* 设置除数左移次数缓冲 n_try，置初始值为0* 设置除数左移后的值的n_try_value缓冲，置初始值为除数的值* 循环判断n_remainder = n_try_value，* 每循环一次，除数左移次数n_try增加1，同时除数左移n_try次，并将值填入缓冲n_try_value中* 退出循环后，最后一次左移是多出来的，减去，即 n_try -；* * 计算除数的2的n次方最大倍数使除数与此倍数的积小于等于被除数* 用循环尝试找出大于等于上述最大积且小于被除数的除数与实际商N的最大积，其中N = 上述最大倍数 + 有效尝试次数* 计算中间余数* */* SpeedyDivision 算法实现* * by Neil* 2006.10.20*/#include #include #define _USAGE printf( NOTE : Setting divisor to zero is not allowed.n );/ 每次移位操作移动的位数, 最大不超过 sizeof( int ) * 8/ 取值为 2 的 n 次方， n = 0#define _MV_BITS 8int add(int,int);int SpeedyDivision(int,int,int*,int*);int CheckErr();int main(int argc,char* argv)int n_dividend =0, n_divisor =0;int n_remainder =0, n_quotient =0;int n_magic =1, n_magic_r =1;if( argc !=1)_USAGEreturn(1);/ for debuging/ return( CheckErr() );printf(Please input dividend and divisor(separating them by one or more space key):n);fflush( stdin );scanf(%d %d,&n_dividend,&n_divisor );if(! n_divisor )_USAGEreturn(1);printf(%d / %dn, n_dividend, n_divisor );if( n_dividend = n_divisor )n_quotient =1;n_remainder =0;elseif( n_dividend n_divisor )n_quotient =0;n_remainder =0;elseif( n_dividend )if( n_dividend 0)n_dividend *=-1;n_magic *=-1;n_magic_r =-1;if( n_divisor 0)n_divisor *=-1;n_magic *=-1;n_magic_r =-1;if( n_divisor =1)n_quotient = n_dividend;elseSpeedyDivision( n_dividend, n_divisor,&n_remainder,&n_quotient );n_quotient *= n_magic;n_remainder *= n_magic_r;printf(quotient = %d, remainder = %dn, n_quotient, n_remainder );return(0);int SpeedyDivision(int n_dividend,int n_divisor,int* lp_remainder,int* lp_quotient )int n_bits =sizeof(int)*8;int n_remainder =0, n_quotient =0;int n_mv_times =0, n_loop =0;unsignedint n_mask =0xff;int n_try =0, n_try_value =0;/ 快速移位算法的移位次数为 位数 / _MV_BITSn_mv_times = n_bits / _MV_BITS;/ 计算每次移位需要取得的被除数最高_MV_BITS位的掩码 n_maskn_loop =0;while( n_loop ( n_bits /8)n_mask |=( n_mask 8);n_loop +;n_mask = n_mask ( add( n_bits,-_MV_BITS );n_loop =0;while( n_loop n_mv_times )n_remainder = n_remainder ( add( n_bits,-_MV_BITS );n_dividend = n_dividend _MV_BITS;n_quotient = n_quotient = n_divisor )n_try =0;n_try_value = n_divisor = n_try_value )n_try = add( n_try,1);n_try_value = n_divisor n_try;/ 退出循环前的最后一次移位是无效的，减去n_try = add( n_try,-1);/ 计算除数的2的n次方最大倍数使得除数与此倍数的积小于等于余数缓存区的值n_quotient = add( n_quotient,(int)pow(2, n_try );/ 除数与上述最大倍数的积(最大积)n_try_value = n_divisor = n_try_value )/ 每次增加一次除数n_try_value = add( n_try_value, n_divisor );if( n_remainder = n_try_value )/ 计算中间商n_quotient = add( n_quotient,1);/ 退出循环前加的那次是多余的,减去,得到小于等于余数缓存区的值的除数与中间商N的积n_try_value = add( n_try_value,-n_divisor );/ 计算中间余数n_remainder = add( n_remainder,-n_try_value );n_loop +;/ 返回实际商与余数* lp_remainder = n_remainder;* lp_quotient = n_quotient;return(0);int add(int a,int b )int c =0;while( c = a & b)a = a b;b = c 1;return a b;int CheckErr(void)int n_dividend =0, n_divisor =0;int n_remainder =0, n_quotient =0;int loop =2, nmax =2147483647;int loop2 =2;while( loop = nmax )n_dividend = loop;loop2 =2;while( loop2 = loop )n_divisor = loop2;SpeedyDivision( n_dividend, n_divisor,&n_remainder,&n_quotient );if( n_quotient * n_divisor + n_remainder )!= n_dividend )printf(Error : %d / %d = %d, remainder = %dn,n_dividend, n_divisor, n_quotient, n_remainder );return(-1);loop2 +;loop +;if( loop %100000)=0)printf(%d - %d is ok.n, loop -100000+1, loop );printf(2 - 2147483647 is ok.n);return(0);其中 add 方法我就偷懒照搬花总写的了（让我想我也想不出更好的啦，嘎嘎），这个算法我个人觉得唯一可取之处就是左移不是一次一位的移了，这样对于左移的时间和次数都减少了，不过貌似对内存空间的要求增加了，我还没有仔细比对，先发着大家砸吧，呵呵我真是木瓜脑袋，被移位给框死了，只想到能比一位一位地快就好，所以给出了上面那个代码，刚才又仔细看了几遍，突然发现如果 _MV_BITS 设置为sizeof(int)*8，移位一次就相当如把被除数整个移进了余数缓冲区，其效果就是外层循环次数为1，也就是说，真正起作用的是内层if里的内容。我被自己郁闷到了55555555555555修改后的代码如下：（只给出了 SpeedyDivision2 函数，其他几乎一样的）代码int SpeedyDivision2(int n_dividend,int n_divisor,int* lp_remainder,int* lp_quotient )int n_remainder =0, n_quotient =0;int n_try =0, n_try_value =0;n_remainder = n_dividend;n_try =0;n_try_value = n_divisor = n_try_value )n_try = add( n_try,1);n_try_value = n_divisor n_try;/ 退出循环前的最后一次移位是无效的，减去n_try = add( n_try,-1);/ 计算除数的2的n次方最大倍数使得除数与此倍数的积小于等于被除数n_quotient = add( n_quotient,(int)pow(2, n_try );/ 除数与上述最大倍数的积(最大积)n_try_value = n_divisor = n_try_value )/ 每次增加一次除数n_try_value = add( n_try_value, n_divisor );if( n_remainder = n_try_value )/ 计算实际商n_quotient = add( n_quotient,1);/ 退出循环前加的那次是多余的,减去,得到小于等于被除数的除数与实际商N的积n_try_value = add( n_try_value,-n_divisor );/ 计算实际余数n_remainder = add( n_remainder,-n_try_value );/ 返回实际商与余数* lp_remainder = n_remainder;* lp_quotient = n_quotient;return(0);-锦瑟无端五十弦，一弦一柱思华年庄生晓梦迷蝴蝶，望帝春心托杜鹃沧海月明珠有泪，蓝田日暖玉生烟此情可待成追忆，只是当时已惘然举个例子,就以add函数的实现算法来说吧,前面两份代码都是这样的方法:代码int add (int a,int b)int c;while(c = a & b)a = a b;b = c 1;return a b;可是难道就没别的办法了吗?以c99为例,支持动态数组的c99里,我们可以这样:代码int add(int m,int n)int inc (int num)structchar anum;char b;*s;returnsizeof(*s);while(m-)n = inc (n);注意到其中的inc函数了吗?它可以实现num+=1的功能(想想,为什么?).然后循环加m次,是不是就可以实现m+n了呢?这就是一种有效的方法.注意了,这种方法虽然可行-但是:1)速度超级慢,不信你们去算算10/2看看2) m-用到了自减运算符号,好象不符合规定于是,我们可以这样:代码int add(int m,int n)structchar am;char bn;*s;returnsizeof(*s);速度就快很多了,并且还没有使用任何的加减乘除运算符号与关键字.最后,我们就可以得到改变了的代码:代码#inlcude int add(int m,int n)structchar am;char bn;*s;returnsizeof(*s);unsignedint idiv (unsignedint a,unsignedint b)int i;unsignedint m =0;for(i =1; i =32; i+)m =(m 31);a = a = b)m = add (m,-b);/m = m - b;a = add (a,1);/a = a + 1;return a;int main (int argc,char*argv