数据结构-位运算实现加减乘除、取反求补

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

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

整数的加法

int MyAdd(int a,int b)    
{    
    for(int i=1;i;i<<=1)         
        if(b&i)            
            for(int j=i;j;j<<= 1)        
                if(a&j) a&=~j;    
                else {a|=j;break;}                          
    return a ;    
}

主要是利用a+1的位运算就是最左端（从第0位开始向左）连续的1变为0，原先a中为0的位置最低那一位变为1。
在不同的位上加1，那就是从相应的位开始向左计算，右边不变。

还有一个思路,如下：

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);//进行递归，相加    
}

简化一下：

int Add(int a,int b) { b?return Add(a^b,(a&b)<<1):return a; }

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

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

int MyMinus(int a,int b)    
{    
    for(int i=1;i&&((b&i)==0);i<<=1);    
    for(i<<=1;i;i<<=1) b^=i;    
    return MyAdd(a,b);    
}

整数的乘法

乘法就是将乘数写成(2^0)k0 + (2^1)k1 + (2 ^2)k2 + … + (2^31)k31，其中ki为0或1，然后利用位运算和加法就可以了。

int MyMul(int a,int b)    
{    
    int ans=0;    
    for(int i=1;i;i<<=1,a<<=1)    
        if(b&i)    
            ans+=a;    
        return ans;    
}

整数除法（正整数）

除法就是由乘法的过程逆推，依次减掉（如果x够减的）y^(2^31),y^(2^30),…y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。

int MyDiv(int x,int y)    
{    
    int ans=0;    
    for(int i=31;i>=0;i--)  
    {    
    //比较x是否大于y的(1<<i)次方，避免将x与(y<<i)比较，因为不确定y的(1<<i)次方是否溢出  
        if((x>>i)>=y)           
        {       
            ans+=(1<<i);      
            x-=(y<<i);        
        }       
    }    
    return ans;    
}

加减乘除位运算示例

// 程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现
// 在实现除法运算时，用了从高位到低位的减法
// 具体如下，算法也比较简单，所以没有作注释

#include <iostream>
using namespace
std;

// 加法
int add(int a, int b) {
    int c;
    while (c = (a & b)) {
        a = (a ^ b);
        b = (c << 1);
    }
    return (a ^ b);
}

// 求补码
int rev(int a) {
    return add((~a), 1);
}

// 判断正负
int ispos(int a) { // 正
    return (a & 0xFFFF) && !(a & 0x8000);
}
int isneg(int a) { // 负
    return a & 0x8000;
}
int iszero(int a) { // 0
    return !(a & 0xFFFF);
}

// 比较两个正数的大小（非负也可）
int isbig_pos(int a, int b) { // a>b>0
    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) { // a>b
    if (isneg(a)) {
        if (isneg(b)) {
            return isbig_pos(rev(b), rev(a));
        }
        return 0;
    }
    if (isneg(b)) return 1;
    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)) return 0;
    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)) return 0;
    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);
        }
    }
    return re;
}

// 除法
int idiv(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 rev(pos_div(a, rev(b)));
    }
    if (ispos(b))
        return rev(pos_div(rev(a), b));
    return pos_div(rev(a), rev(b));
}

int main() {
    int a, 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;
    }
    return 0;
}

加法是这样的

int add(int a,int b){int c;while(c=a&b){ a=a^b;b=c<<1;}return a^b;}

乘法是这样的

int cheng(int a,int b){ 
    int c,i;c=0;
    for(i=0;i<16;i++){if(b&(1<<i)c=add(c,a<<i));}
    return c;
}

计算机乘法除法原理

1.乘法
由于计算机中，所有数值都是用2的N次方来表示的:2^n0+2^n1+2^n2+2^n3+2^n4…..
因此xy,(x)(2^n0+2^n1+2^n2+2^n3+2^n4)=(x2^n0)+(x2^n1)+(x2^n2)+(x2^n3)+(x*2^n4)+……即(x左移n0)+(x左移n1)+(x左移n2)+(x左移n3)+(x左移n4)+……

用15(x)13(y)来举例，1513 为1111*1101

a.首先y的最低位为1(2^0)，x左移0位得到1111  
b.然后y的最低第二位为0，没有2^1存在，因此本次无运算(结果可以看作为0)  
c.然后y的最低第三位为1(2^2)，x左移2位得到111100  
d.然后y的最低第四位为1(2^3)，x左移3位得到1111000  
e.把a、b、c、d的结果相加1111+0+111100+1111000=11000011(195),该结果就是乘法的结果

特别的，x*y中，如果y是2的N次方，因此相当于x右移N位。

2.除法(加减交替法)
x/y其实就是，x不断减y的过程。小学时候学的长长除法就是这个原理。
用二进制的除法x/y，比十进制容易写，商不是0即是1，而且如果除数大于除数的1倍，商就是标记在另一个位上面了。

二进制除法x/y=0.1001/0.1011手工计算如下：

            0.11  
       _______
0.1001/0.1001
         10010(后面补0)
         -1011
        ------
           111(余数)
           1110(后面补0)
          -1011
        --------
              1(余数)
              
设ri表示第i次运算后所得的余数,则：
若ri>0，则商1，余数和商左移1位，再减去除数，即ri+1=2ri-y
若ri<0，则商0，余数和商左移1位，再加上除数，即ri+1=2ri+y

用85/6来举例,85/6=1010101/110

a.101(0101)左移1位到第3位都小于110，因此商=000  
b.1010(101)左移四位是1010,比110大，商=0001,余数=1010-110=100(101)  
c.余数100(101)左移一位是1001,比110大，商=00011,余数=1001-110=11(01)  
d.余数11(01)左移一位是110,等于110，商=000111,余数=0(1)  
e.余数0(1)左移一位是01,小于110,商=0001110,余数=01

因此85/6=1010101/110=0001110，即14，余数为最后的余数1

版权所有，转载请注明出处 luowei.github.io.