`

位运算

    博客分类:
  • C++
 
阅读更多

位运算的思想可以应用到很多地方,这里简单的总结一下用位运算来实现整数的四则运算。

1.整数的加法

view plain

  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,那就是从相应的位开始向左计算,右边不变。

下面还有一个网上的思路,我觉得这个更好:

view plain

  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. }

 

简化一下:

view plain

  1. intAdd(inta,intb){b?returnAdd(a^b,(a&b)<<1):returna;}

 

上面的思路就是先不计进位相加,然后再与进位相加,随着递归,进位会变为0,递归结束。

2.整数的减法

这个和加法一样了,首先取减数的补码,然后相加。

view plain

  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,其中ki01,然后利用位运算和加法就可以了。

view plain

  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就在结果加上相应的数量。

view plain

  1. intMyDiv(intx,inty)
  2. {
  3. intans=0;
  4. for(inti=31;i>=0;i--)
  5. {
  6. //比较x是否大于y(1<<i)次方,避免将x(y<<i)比较,因为不确定y(1<<i)次方是否溢出
  7. if((x>>i)>=y)
  8. {
  9. ans+=(1<<i);
  10. x-=(y<<i);
  11. }
  12. }
  13. returnans;
  14. }

 

====================================================================================

====================================================================================

加减乘除位运算

//程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现

//在实现除法运算时,用了从高位到低位的减法

//具体如下,算法也比较简单,所以没有作注释

 

#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

  1001111011110

  0011,商0000011100

  左移100011100

  2001111101100

  0011,商0000111000

  左移100111000

  3001100001000

  1000010001

  左移100010001

  4 001111100001

  0011,商0000100010

  左移100100010

  R0右移100010010

  所以,商是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 --

*

*计算除数的2n次方最大倍数使除数与此倍数的积小于等于被除数

*用循环尝试找出大于等于上述最大积且小于被除数的除数与实际商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

//取值为2n次方,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);

 

//计算除数的2n次方最大倍数使得除数与此倍数的积小于等于余数缓存区的值

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);

 

//计算除数的2n次方最大倍数使得除数与此倍数的积小于等于被除数

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);

}

 

 

INCADD还是有点区别di,一个是一个操作数,一个是2个操作数

 

当然,我用INCECX绕过使用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

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics