首页 | Home
博客 | Blog
关于 | About

位操作

Posted on | Post modified | In C

Bitwise Operations

这一节我们研究如何使用位运算，完成加减乘的数学运算。在介绍每种运算之前，先来复习下基本的位运算：

x y AND& OR| XNOR(同或) XOR(异或)^
0 0 0 0 1 0
0 1 0 1 0 1
1 0 0 1 0 1
1 1 1 1 1 0
  • 异或

相同为0，不同为1，可以理解为不进位的加法，其性质如下：

x^0 = x;
x^1s = ~x //1s 为若干个1
x^(~x) = 1s
x^x = 0 //important!
a^b=c --> a^c=b --> b^c=a //可用于swap操作
  • 常用的位运算操作
x&1 == 1 or 0 //判断奇数偶数(x%2==1)
x = x&(x-1) //清零最低位的1，可用来计算二进制中1的个数
x &-x //得到最低位的1
x & (~0 << n) //x的最右边n位清零

四则运算

为了简化场景，和表述方便，令所有的操作数的类型为signed long long类型，对于int类型的边界问题，在本章最后讨论

加法

我们先使用真值表分析两个bit相加的几种情况，进而推算出多个bit的加法规则

x y sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

由上面的真值表可以推到看出:

  1. sum = x XOR y
  2. carry = x AND y

回想十进制的两位数加法规则，如果个位相加有进位，则十位要累加进位，同样的规则也适用于位运算，我们将上面真值表中加入上一次计算的进位项：

x y last carry sum carry
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 0 1

由上面真值表不难发现，多个bit的叠加是一个循环的过程，即第0为产生的carry带给第1位，第1位的x，y相加后再加上carry，将产生的carry再带给第2位…，以此类推。想想我们如何用程序实现这个过程，首先最容易想到的是将两个数x，y分别转成二进制数，然后按照真值表的规则，逐位相加。但是将一个数拆成二进制这种做法太麻烦，工作量很大，而且计算速度满。实际上要达到同样的效果，也可以这么做，首先将x,y先进行XOR操作，得到各个位上未累加carry项的结果A，然后再令x,y进行AND操作，得到每第一位的carry结果B，接着可以让A累加上每一位的carry，即AB进行XOR操作，但这个操作又会带来新的carry，于是循环这个而操作，直到carry为0

long long add(long long a, long long b){
    long long sum = 0,carry = 0;
    do{
        sum = a^b;
        carry = (a&b)<<1;
        sum = a;
        carry = b;
    }while(carry > 0)
    
    return sum;
}

对于上述代码，sum循环累加carry的过程有些不好理解，我们以3+1为例，看一下这个过程

    011         011         001  
XOR 001     AND 001     <<    1
-------     --------    ------- 
    010         001         010  
-------------------------------------（1）

    010         011         010  
XOR 010     AND 010     <<    1
-------     --------    ------- 
    000         010         100  
------------------------------------- (2)

    000         000      
XOR 100     AND 100     
-------     --------    
    100         000     
------------------------------------- (3)
  1. 第(1)步累加之后carry项为010表示在计算第一位时产生了一个carry，需要将其累加到sum的第二上
  2. 第(2)步将sum的第二项和carry累加得到000，此时又产生了新的carry010，因此需要将其加到sum的第三位上
  3. 第(3)步将sum的第三项和carry累加得到100，此时的carry为0，说明此次相加没有产生新的carry，运算结束

减法

有了加法之后，后面的减法和乘法就要简单很多，先看减法，要计算a+b可以转化为计算a+(-b)，那么如何表示-b呢？这个问题在C语言第二部分中曾提到过，在计算机中，有符号数是通过补码进行存储的，补码计算方式为“源码取反+1”, 因此-b可以表示为:~b+1，a+b可以表示为a+(~b+1)。理解了这个，减法就很容易实现了

long long subtract(long long a, long long b){
　　long long subtrahend = add(~b, 1);
　　long long sub = add(a, subtrahend);
　　return sub;
}

乘法

乘法计算也可以转化为加法计算，只需要将被乘数循环累加乘数次即可。考虑到乘数或者被乘数中可能有负数，因此还需要想办法解决符号的问题。

long long multiply(long long a, long long b){
    int sign = ((a <0) ^ (b< 0)) ? -1 : 1;
    long long multiplicand = labs(a);
    long long multiplier = labs(b);
    long long result=0;
    for(long long i=0;i<multiplier; ++i){
        result = add(result,multiplicand);
    }
    return sign == 1 ? result : -result;
}

这种方式相对简单，但是效率不高，而且有一个比较严重的问题是当乘数很大时，比如1x99999，那么上述运算要循环99999次，这显然是极为低效的，因此还有另一种手动模拟乘法的方式，假如我们要做2x3和2x5我们可以像做十进制乘法一样对二进制各位进行乘法运算后求和：

    010             010
*   011         *   101  
-------         -------
    010             101
   0100            0000
 000000           10100
-------         -------
 000110           11001

观察上面运算可以发现：

  1. 令乘数的每一位与被乘数相乘，每乘一次乘数向右移动一位，直到乘数为0
  2. 如果乘数的第n位为1，只需要将被乘数左移n位即可，实际运算中可以让被乘数在每进行完一次乘法后向左移动一位，这样则可以不必单独记录n的值
  3. 如果乘数的第n位为0，这次计算可以跳过
long long multiply(long long a, long long b){
    int sign = ((a <0) ^ (b< 0)) ? -1 : 1;
    long long multiplicand = labs(a);
    long long multiplier = labs(b);
    long long result=0;
    while(multiplier > 0){
        if( (multiplier &0x01) != 0){
            result = add(result,multiplicand);
        }
        multiplicand = multiplicand<<1;
        multiplier = multiplier>>1;
    }
    return sign == 1 ? result : -result;
}

除法

简单的除法是不断用被除数减去除数，直到被除数小于除数，此时做减法的次数为商，余数为被除数。同样，除法也需要考虑符号问题

long long divide(long long a, long long b){
    int sign = ((a <0) ^ (b< 0)) ? -1 : 1;
    long long multiplicand = labs(a);
    long long multiplier = labs(b);
    long long remainder = dividend;
    long long result = 0;
    while(remainder >= divisor){
        remainder = substract(remainder,divisor);
        result = add(result,1);
    }
    return sign == 1 ? result : -result;
}

上述算法也会遇到和简单乘法相同的问题，就是当被除数特别大，除数特别小时，算法会很低效，比如99999/1要循环99999次。我们能否找到一种扩大步长的方式来减少循环次数呢？先看上面的运算，步长为除数，商为循环的次数。如果我们以除数的2的n次方倍作为步长，不断逼近被除数，则可以大大加快速度，我们以19/3为例来看下这种算法

  1. 找到小于19的最大除数，该除数为3的(2^i)倍，可知该除数为3x2x2 =12,此时i=2,相当于除数左移了两位3<<2
  2. 令19/12，得到商q=1，余数r=7，对于q的理解是它包含了2^i个3，因此，实际的商为qx2^i = 1x2^2 = 4
  3. 对于余数r=7，显然它并不是最后的余数，还可以继续被分解，于是将他作为新的被除数，重复第一步，找到小于7的最大除数为6，此时i=1，相当于3<<1
  4. 令7/6的到商q=1,r=1，此时的q同样是包含了2^i个3，因此，即实际的商为1x2=2，加上第2步得到的商，总的结果为6
  5. 此时r=1小于3说明除数已经全部分解完成，得到的余数为真正的余数
long long divide(long long a, long long b){
    int sign = ((a <0) ^ (b< 0)) ? -1 : 1;
    long long dividend  = labs(a);
    long long divisor = labs(b);
    long long tmp = 0;
    long long  result = 0;
    for(int i=31; i>=0; i--){
        tmp  = divisor << i; //divisor不变，tmp不断变小，int类型放置左移溢出
        if(dividend >= tmp){
            result = add(result,1LL<<i);
            dividend = (int)substract((int)dividend,(int)tmp);
        }
    }
    return sign == 1 ? result : -result;
}

关于除法还有另外一种计算方式，这种方式比上面要简单的多，并且不依赖加法与减法，该方式的伪码为：

quotient = 1
while divisor is less than dividend
    divisor = (left shift divisor)
    quotient = (left shift quotient)
Handle overflow recursively.

以除数被除数都为正数为例（忽略int边界问题），上述逻辑实现如下：

int  divide(int dividend, int divisor){
    if(dividend == 0 || dividend<divisor){
        return 0;
    }
    if(divisor == 1 ){
        return dividend;
    }
    if(dividend == divisor){
        return 1;
    }

    int q = 1; int tmp = divisor;
    while(tmp < dividend){
        tmp = tmp<<1;
        q = q<<1;
    }
    //余数比除数大的情况，比如11/3 , 商2余5，还需要继续这个过程
    if(tmp > divisor){
        tmp = tmp>>1;
        q = q>>1;
        return q+divide(dividend-tmp,divisor);
    }else{
        return q;
    }
}

边界问题

上面的算法均假设所有数据类型为long long类型，如果需要计算int类型的四则运算，需要考虑int的边界范围，即INT_MAX, INT_MIN。比如，计算除法divide(-2147483648, -1),被除数为INT_MIN，如果使用abs去符号，则得不到2147483648(INT_MAX为2147483647)，因此可以考虑使用labs函数，另外，再做商累加时，需要用到移位操作，1«i，如果i为INT_MAX同样会有问题，需要考虑将1表示为long long类型的1LL`。

更多为位运算相关问题

位运算除了用于做加减乘除外，还可以有其它的应用