位运算实现加减乘除求补比较正负判断.docx
《位运算实现加减乘除求补比较正负判断.docx》由会员分享，可在线阅读，更多相关《位运算实现加减乘除求补比较正负判断.docx（31页珍藏版）》请在冰点文库上搜索。
位运算实现加减乘除求补比较正负判断
维唯为为_博客园
∙博客园
∙首页
∙博问
∙闪存
∙新随笔
∙联系
∙订阅
∙管理
随笔-150文章-1评论-5
位运算实现加减乘除、求补、比较、正负判断
位运算的思想可以应用到很多地方，这里简单的总结一下用位运算来实现整数的四则运算。
1.整数的加法
viewplain
1.intMyAdd（inta,intb）
2.{
3.for（inti=1;i;i<<=1）
4.if（b&i）
5.for（intj=i;j;j<<=1）
6.if（a&j）a&=~j;
7.else{a|=j;break;}
8.returna;
9.}
我的思路主要是利用a+1的位运算就是最左端（从第0位开始向左）连续的1变为0，原先a中为0的位置最低那一位变为1。
在不同的位上加1，那就是从相应的位开始向左计算，右边不变。
下面还有一个网上的思路，我觉得这个更好：
viewplain
1.intAddWithoutArithmetic（intnum1,intnum2）
2.{
3.if（num2==0）returnnum1;//没有进位的时候完成运算
4.intsum,carry;
5.sum=num1^num2;//完成第一步没有进位的加法运算
6.carry=（num1&num2）<<1;//完成第二步进位并且左移运算
7.returnAddWithoutArithmetic（sum,carry）;//进行递归，相加
8.}
简化一下：
viewplain
1.intAdd（inta,intb）{b?
returnAdd（a^b,（a&b）<<1）:
returna;}
上面的思路就是先不计进位相加，然后再与进位相加，随着递归，进位会变为0，递归结束。
2.整数的减法
这个和加法一样了，首先取减数的补码，然后相加。
viewplain
1.intMyMinus（inta,intb）
2.{
3.for（inti=1;i&&（（b&i）==0）;i<<=1）;
4.for（i<<=1;i;i<<=1）b^=i;
5.returnMyAdd（a,b）;
6.}
3.整数的乘法
乘法就是将乘数写成（2^0）*k0+（2^1）*k1+（2^2）*k2+...+（2^31）*k31，其中ki为0或1，然后利用位运算和加法就可以了。
viewplain
1.intMyMul（inta,intb）
2.{
3.intans=0;
4.for（inti=1;i;i<<=1,a<<=1）
5.if（b&i）
6.ans+=a;
7.returnans;
8.}
4.整数除法（正整数）
除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^（2^31）,y^（2^30）,...y^8,y^4,y^2,y^1。
减掉相应数量的y就在结果加上相应的数量。
viewplain
1.intMyDiv（intx,inty）
2.{
3.intans=0;
4.for（inti=31;i>=0;i--）
5.{
6.//比较x是否大于y的（1<7.if（（x>>i）>=y）
8.{
9.ans+=（1<10.x-=（y<11.}
12.}
13.returnans;
14.}
====================================================================================
====================================================================================
加减乘除位运算
//程序中实现了比较大小、加减乘除运算。
所有运算都用位操作实现
//在实现除法运算时，用了从高位到低位的减法
//具体如下，算法也比较简单，所以没有作注释
#include
usingnamespacestd;
//加法
intadd（inta,intb）
{
intc;
while（c=（a&b））
{
a=（a^b）;
b=（c<<1）;
}
return（a^b）;
}
//求补码
intrev（inta）
{
returnadd（（~a）,1）;
}
//判断正负
intispos（inta）
{//正
return（a&0xFFFF）&&!
（a&0x8000）;
}
intisneg（inta）
{//负
returna&0x8000;
}
intiszero（inta）
{//0
return!
（a&0xFFFF）;
}
//比较两个正数的大小（非负也可）
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（rev（b）,rev（a））;
}
return0;
}
if（isneg（b））return1;
returnisbig_pos（a,b）;
}
//减法
intsub（inta,intb）
{
returnadd（a,rev（b））;
}
//正数乘法
intpos_mul（inta,intb）
{
intc=0x8000;
intre=a;
while（（c>>=1）&&（!
（b&c）））;
while（c>>=1）
{
re<<=1;
if（c&b）
re=add（re,a）;
}
returnre;
}
//乘法
intmul（inta,intb）
{
if（iszero（a）||iszero（b））return0;
if（ispos（a）&&ispos（b））
returnpos_mul（a,b）;
if（isneg（a））
{
if（isneg（b））
{
returnpos_mul（rev（a）,rev（b））;
}
returnrev（pos_mul（rev（a）,b））;
}
returnrev（pos_mul（a,rev（b）））;
}
//正数除法
intpos_div（inta,intb）
{
intre=0,temp=b;
if（isbig_pos（b,a））return0;
do{
temp<<=1;
}while（!
isbig_pos（temp,a））;
while（isbig_pos（temp,b））
{
re<<=1;
temp>>=1;
if（!
isbig_pos（temp,a））
{
a=sub（a,temp）;
re=add（re,1）;
}
}
returnre;
}
//除法
intidiv（inta,intb）
{
if（iszero（b））
{
cout<<"error"<exit
（1）;
}
if（iszero（a））return0;
if（ispos（a））
{
if（ispos（b））
returnpos_div（a,b）;
returnrev（pos_div（a,rev（b）））;
}
if（ispos（b））
returnrev（pos_div（rev（a）,b））;
returnpos_div（rev（a）,rev（b））;
}
intmain（）
{
inta,b;
while（cin>>a>>b）
{
if（isbig（a,b）&&（a<=b））cout<<"bigerror"<if（add（a,b）!
=（a+b））cout<<"adderror"<if（sub（a,b）!
=（a-b））cout<<"suberror"<if（mul（a,b）!
=（a*b））cout<<"mulerror"<if（idiv（a,b）!
=（a/b））cout<<"diverror"<}
return0;
}
-----------------------------------------------------------------------------------
加法是这样的
intadd（inta,intb）{intc;while（c=a&b）{a=a^b;b=c<<1;}returna^b;}
乘法是这样的
intcheng（inta,intb）{intc,i;c=0;
for（i=0;i<16;i++）{if（b&（1<returnc;}
zv的计算机组成原理学得好,给出了一个思路.
我记性不坏,还记得以前曾见过的算法,于是:
代码
（2005年）32．用原码加减交替一位除法进行7÷2运算。
要求写出每一步运算过程及运算结果。
循环步骤余数（R0R1）
0初始值00000111
左移，商000001110
1减001111011110
加0011，商000001110（0）
左移1位00011100
2减001111101100
加0011，商000011100（0）
左移1位00111000
3减001100001000
商100001000
（1）
左移1位00010001
4 减001111100001
加0011，商000010001（0）
左移1位00100010
R0右移1位00010010
所以，商是0010，即2；余数是0001，即1。
以及:
代码
这是一种实现，只能整除，并且肯定有问题：
#include
unsignedintdiv（unsignedinta,unsignedintb）
{
inti;
unsignedintm=0;
for（i=1;i<=32;i++）
{
m=（m<<1）|（a>>31）;
a=a<<1;
if（m>=b）
{
m=m-b;
a=a+1;
}
}
returna;
}
intmain（intargc,char**argv）
{
inta,b;
scanf（"%d,%d",&a,&b）;
printf（"a=%d\n",div（a,b））;
}
虽然我和zv的大致思路没问题,但是,注意了,实现除法的算法有很多种.
这里,悬赏2000盾盾,寻求其它的除法思路--即便最后没选上,认真参与并讨论的,也有额外的盾盾奖励!
--------------------
修改了之后的代码,这仅仅是众多算法中的一种而已:
代码
#include
intadd（inta,intb）
{
intc;
while（c=a&b）
{
a=a^b;
b=c<<1;
}
returna^b;
}
unsignedintidiv（unsignedinta,unsignedintb）
{
inti;
unsignedintm=0;
for（i=1;i<=32;i++）
{
m=（m<<1）|（a>>31）;
a=a<<1;
if（m>=b）
{
m=add（m,-b）;//m=m-b;
a=add（a,1）;//a=a+1;
}
}
returna;
}
intmain（intargc,char**argv）
{
inta,b;
scanf（"%d,%d",&a,&b）;
printf（"a=%d\n",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算法实现
*
*byNeil
*2006.10.20
*/
#include
#include
#define_USAGEprintf（"NOTE:
Settingdivisortozeroisnotallowed.\n"）;
//每次移位操作移动的位数,最大不超过sizeof（int）*8
//取值为2的n次方，n>=0
#define_MV_BITS8
intadd（int,int）;
intSpeedyDivision（int,int,int*,int*）;
intCheckErr（）;
intmain（intargc,char*argv[]）{
intn_dividend=0,n_divisor=0;
intn_remainder=0,n_quotient=0;
intn_magic=1,n_magic_r=1;
if（argc!
=1）{
_USAGE
return
（1）;
}
//fordebuging
//return（CheckErr（））;
printf（"Pleaseinputdividendanddivisor（separatingthembyoneormorespacekey）:
\n"）;
fflush（stdin）;
scanf（"%d%d",&n_dividend,&n_divisor）;
if（!
n_divisor）{
_USAGE
return
（1）;
}
printf（"%d/%d\n",n_dividend,n_divisor）;
if（n_dividend==n_divisor）{
n_quotient=1;
n_remainder=0;
}elseif（n_dividendn_quotient=0;
n_remainder=0;
}else{
if（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;
}else{
SpeedyDivision（n_dividend,n_divisor,&n_remainder,&n_quotient）;
}
}
}
n_quotient*=n_magic;
n_remainder*=n_magic_r;
printf（"quotient=%d,remainder=%d\n",n_quotient,n_remainder）;
return（0）;
}
intSpeedyDivision（intn_dividend,intn_divisor,
int*lp_remainder,int*lp_quotient）{
intn_bits=sizeof（int）*8;
intn_remainder=0,n_quotient=0;
intn_mv_times=0,n_loop=0;
unsignedintn_mask=0xff;
intn_try=0,n_try_value=0;
//快速移位算法的移位次数为[位数/_MV_BITS]
n_mv_times=n_bits/_MV_BITS;
//计算每次移位需要取得的被除数最高_MV_BITS位的掩码n_mask
n_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_loopn_remainder=n_remainder<<_MV_BITS;
n_remainder|=（（n_dividend&n_mask）>>（add（n_bits,-_MV_BITS）））;
n_dividend=n_dividend<<_MV_BITS;
n_quotient=n_quotient<<_MV_BITS;
if（n_remainder>=n_divisor）{
n_try=0;
n_try_value=n_divisor<//计算除数左移的有效次数
while（n_remainder>=n_try_value）{
n_try=add（n_try,1）;
n_try_value=n_divisor<}
//退出循环前的最后一次移位是无效的，减去
n_try=add（n_try,-1）;
//计算除数的2的n次方最大倍数使得除数与此倍数的积小于等于余数缓存区的值
n_quotient=add（n_quotient,（int）pow（2,n_try））;
//除数与上述最大倍数的积（最大积）
n_try_value=n_divisor<//用循环尝试找出大于等于上述最大积且小于余数缓存区的值的除数与中间商N的最大积，
//其中N=上述最大倍数+有效尝试次数
while（n_remainder>=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）;
}
intadd（inta,intb）{
intc=0;
while（c=a&b）{
a=a^b;
b=c<<1;
}
returna^b;
}
intCheckErr（void）{
intn_dividend=0,n_divisor=0;
intn_remainder
升级会员 