位运算的思想可以应用到很多地方,这里简单的总结一下用位运算来实现整数的四则运算。
1.整数的加法
-
intMyAdd(inta,intb)
-
{
-
for(inti=1;i;i<<=1)
-
if(b&i)
-
for(intj=i;j;j<<=1)
-
if(a&j)a&=~j;
-
else{a|=j;break;}
-
returna;
-
}
我的思路主要是利用a+1的位运算就是最左端(从第0位开始向左)连续的1变为0,原先a中为0的位置最低那一位变为1。
在不同的位上加1,那就是从相应的位开始向左计算,右边不变。
下面还有一个网上的思路,我觉得这个更好:
-
intAddWithoutArithmetic(intnum1,intnum2)
-
{
-
if(num2==0)returnnum1;//没有进位的时候完成运算
-
intsum,carry;
-
sum=num1^num2;//完成第一步没有进位的加法运算
-
carry=(num1&num2)<<1;//完成第二步进位并且左移运算
-
returnAddWithoutArithmetic(sum,carry);//进行递归,相加
-
}
简化一下:
-
intAdd(inta,intb){b?returnAdd(a^b,(a&b)<<1):returna;}
上面的思路就是先不计进位相加,然后再与进位相加,随着递归,进位会变为0,递归结束。
2.整数的减法
这个和加法一样了,首先取减数的补码,然后相加。
-
intMyMinus(inta,intb)
-
{
-
for(inti=1;i&&((b&i)==0);i<<=1);
-
for(i<<=1;i;i<<=1)b^=i;
-
returnMyAdd(a,b);
-
}
3.整数的乘法
乘法就是将乘数写成(2^0)*k0 + (2^1)*k1 + (2 ^2)*k2 + ... + (2^31)*k31,其中ki为0或1,然后利用位运算和加法就可以了。
-
intMyMul(inta,intb)
-
{
-
intans=0;
-
for(inti=1;i;i<<=1,a<<=1)
-
if(b&i)
-
ans+=a;
-
returnans;
-
}
4.整数除法(正整数)
除法就是由乘法的过程逆推,依次减掉(如果x够减的)y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。
-
intMyDiv(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;
-
}
====================================================================================
====================================================================================
加减乘除位运算
//程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现
//在实现除法运算时,用了从高位到低位的减法
//具体如下,算法也比较简单,所以没有作注释
#include <iostream>
using namespace std;
//加法
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"<<endl;
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<<"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;
}
-----------------------------------------------------------------------------------
加法是这样的
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<<i)c=add(c,a<<i));}
returnc;}
zv的计算机组成原理学得好,给出了一个思路.
我记性不坏,还记得以前曾见过的算法,于是:
代码
(2005年)32.用原码加减交替一位除法进行7÷2运算。要求写出每一步运算过程及运算结果。
循环步骤余数(R0 R1)
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 <stdio.h>
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 <stdio.h>
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算法实现
*
* by Neil
* 2006.10.20
*/
#include <stdio.h>
#include <math.h>
#define _USAGE printf( "NOTE : Setting divisor to zero is not allowed.\n" );
//每次移位操作移动的位数,最大不超过sizeof( int ) * 8
//取值为2的n次方,n >= 0
#define _MV_BITS 8
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);
}
// 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){
_USAGE
return(1);
}
printf("%d / %d\n",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;
}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_loop<n_mv_times){
n_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<<n_try;
//计算除数左移的有效次数
while(n_remainder>=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;
//用循环尝试找出大于等于上述最大积且小于余数缓存区的值的除数与中间商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=0,n_quotient=0;
intloop=2,nmax=2147483647;
intloop2=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 = %d\n",
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函数,其他几乎一样的)
代码
intSpeedyDivision2(intn_dividend,intn_divisor,
int*lp_remainder,int*lp_quotient){
intn_remainder=0,n_quotient=0;
intn_try=0,n_try_value=0;
n_remainder=n_dividend;
n_try=0;
n_try_value=n_divisor<<n_try;
//计算除数左移的有效次数
while(n_remainder>=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;
//用循环尝试找出大于等于上述最大积且小于等于被除数的除数与实际商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);
//返回实际商与余数
*lp_remainder=n_remainder;
*lp_quotient=n_quotient;
return(0);
}
--------------------
锦瑟无端五十弦,一弦一柱思华年
庄生晓梦迷蝴蝶,望帝春心托杜鹃
沧海月明珠有泪,蓝田日暖玉生烟
此情可待成追忆,只是当时已惘然
举个例子,就以add函数的实现算法来说吧,前面两份代码都是这样的方法:
代码
intadd(inta,intb)
{
intc;
while(c=a&b)
{
a=a^b;
b=c<<1;
}
returna^b;
}
可是难道就没别的办法了吗?
以c99为例,支持动态数组的c99里,我们可以这样:
代码
intadd(intm,intn)
{
intinc(intnum)
{
struct{
chara[num];
charb;
}*s;
returnsizeof(*s);
}
while(m--)
{
n=inc(n);
}
}
注意到其中的inc函数了吗?它可以实现num+=1的功能(想想,为什么?).
然后循环加m次,是不是就可以实现m+n了呢?
这就是一种有效的方法.
注意了,这种方法虽然可行--但是:
1)速度超级慢,不信你们去算算10/2看看
2)m--用到了自减运算符号,好象不符合规定
于是,我们可以这样:
代码
intadd(intm,intn)
{
struct{
chara[m];
charb[n];
}*s;
returnsizeof(*s);
}
速度就快很多了,并且还没有使用任何的加减乘除运算符号与关键字.
最后,我们就可以得到改变了的代码:
代码
#inlcude <stdio.h>
intadd(intm,intn)
{
struct{
chara[m];
charb[n];
}*s;
returnsizeof(*s);
}
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;
}
也许,找到新的除法算法不是那么的简单,2000盾盾不是那么好拿的.
但是,要想在已有代码/算法的基础上改进和讨论,我想大家都改做得到,只要多动动脑子就可以了.
为什么不呢?
--------------------
有点没法理解charb[-1];的含义。。。
主要是因为我没在C里面用过动态数组,不知道是否可以用负数来定义数组大小
我以前碰到需要动态改变大小的数组的需求,都是用动态分配内存手动来实现之。。。汗一个先。
就如花总所说,我就先从怎么折腾add()方法琢磨吧,呵呵
--------------------
一个add()函数
代码
intadd(inta,intb){
intrst=0;
_asm{
XOR EAX,EAX
XOR EBX,EBX
XOR ECX,ECX
MOV EAX,a
MOV EBX,b
CMP EBX,0
JL less0// b < 0
JE last// b == 0
// b > 0
MOV ECX,b
again:
INC EAX
LOOP again
JMP last
less0:
// b < 0
MOV ECX,a
dummy:
CMP EBX,0
JE over
INC EBX
LOOP dummy
over:
CMP ECX,0
JE bLarge
MOV EAX,ECX
JMP last
bLarge:
MOV EAX,EBX
last:
MOV rst,EAX
}
return(rst);
}
INC和ADD还是有点区别di,一个是一个操作数,一个是2个操作数
当然,我用INC及ECX绕过使用ADD是有点投机取巧,我再想想吧。。。头疼啊,当年没学过算法。。。5555
也抽点时间顺便写个加法和乘法吧,减法就是加法了,除法就是花哥那个了.就不花时间了.
代码
intadd(inta,intb)
{
intc;
do{
c=a^b;
b=a&b;
a=c;
}while(b<<=1);
returnc;
}
其实这个加法和飞哥给的那个原理是一样的,步骤相反,是先异或求出每一位相加后的值,然后把进位左移再和这些相加后的值做异或,如此重复到进位为0了为止.
代码
intmul(inta,intb){
inti=1,c=0;
do{
c=add(c,a&0x1?b:0);
a=((unsignedint)a>>1)|(c<<(BIT-1));
c>>=1;
}while(i<<=1);
returnc*(~(i-1))+a;
}
这个乘法是乘积是64位的(可能吧,我没做详细测试,而且返回是int值,要改成int64),飞哥给出的那个是32位的,最后一步用(~(i-1))来算最大整数不知道正确不正确.错了就改成7f吧,不过立即数位数就不能改了,比较不通用.其他应该没问题.
#define BIT 32
相关推荐
c++位运算c++位运算c++位运算c++位运算c++位运算c++位运算c++位运算c++位运算c++位运算
c语言位运算c语言位运算c语言位运算c语言位运算c语言位运算
正在学习位运算的人群
【转载】常用位操作 位运算应用口诀 常用位操作 几个常用的位操作 计算树状数组lowbit的三种方法 统计一个整数的二进制中1的个数(位运算技巧) 收藏 统计一个整数的二进制中1的个数的三种方法 位运算讲稿_by_...
ACM位运算技巧 一些常用到的基本位运算技巧
C语言位运算 有6种: &, | , ^(亦或), <<(左移), >>(右移)。 注意:参与位运算的元素必须是int型或者char型,以补码形式出现。 按位与& &运算常应用于: 迅速清零 保留指定位 判断奇偶性 a & 1 = 1...
c++位运算
位运算即是直接进行二进制位的处理.利用c语言的位操作功能,可以方便地将程序中的许多开关变量存储在一个字节的特定位中以节省内存,此类的思想和技巧常常被用于操作系统、计算机网络协议和软件的设计中⋯ .目前...
位运算是指按二进制位进行的运算。因为在系统软件中,常要处理二进制位的问题。文章介绍位运算符和位运算,位运算举例,位段等
0、逻辑运算符 1、位逻辑非运算 2、位逻辑与运算 4、位逻辑异或运算 5、位左移运算 6、位右移运算
CMU上机题,与深入理解计算机系统一书配套,能更好的理解位运算
这是一个16位运算器的设计,有完整的实验过程,适合初学者
Java的位运算
(11)取模运算转化成位运算 (在不产生溢出的情况下) a % (2^n) 等价于 a & (2^n - 1) (12)乘法运算转化成位运算 (在不产生溢出的情况下) a * (2^n) 等价于 a (13)除法运算转化成位运算 (在不产生溢出的情况下) ...
摘自2014国家集训队论文《回归本源——位运算及其应用》,详细描述了位运算的众多巧妙用法,对于位运算的深入运用可以参考。
位运算符 C提供了六种位运算运算符;这些运算符可能只允许整型操作数,即char、short、int和long,无论signed或者unsigned。
Java位运算操作 左位移 右位移 与或非的操作
JAVA位运算.pdf ,深入了解java位运算
实用位运算规则,让你了解位操作的知识,此属于C语言的基础知识内容。
一个c语言 位运算 的程序一个c语言 位运算 的程序一个c语言 位运算 的程序