Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法 » 

位运算应用技巧(2)

位运算可以直接操作计算机内存中整数的二进制位,运行效率很高,而且在代码中巧妙地使用位运算能使程序变得迷人,彰显编程的魅力。
这里介绍一些比较常用的位运算技巧,分为两个部分,本文主要介绍一些综合运用的方法。

  1. 位运算应用技巧(1):位运算基本概念及简单应用
  2. 位运算应用技巧(2):位运算综合运用

四 位运算综合运用

1. 一些等式

(1)关于补码,根据补码的定义可以有

~x = -x-1  -x = ~(x-1)

如对于x=5,取反后绝对值会加1,把5取反后得到-6,把4取反后得到-5,即把5取负相当于把5-1=4取反。

(2)关于运算,对于加减法,有

x+y = (x|y)+(x&y)  x-y = (x|~y)-(~x&y)

x|y中x和y只要有1的位就会为1,如果该位上x、y不同时为1,这就相当于x和y的和,如果同时为1,这时相对x和y的和还少一个1,但是后面x&y中就补上了这个1,而且其只有x和y同时为1的时候才会为1,所以(x|y)+(x&y)就是x+y。

对于位运算,有

x^y = (x|y)-(x&y)  x|y = (x&~y)+y  x&y = (~x|y)-~x

(3)关于关系,对于相等关系,有

x==y <=> !(x-y|y-x) x!=y <=> x-y|y-x

如果x==y,x-y = y-x = 0,0|0=0,显然可以有上式成立。

对于不等关系,有

x<y <=> (x-y)^((x^y)&((x-y)^x))  x<=y <=> (x|~y)&((x^y)|~(y-x))

2. 一些常见的16进制数

以下各数根据其1的位置可以分别取出一个32位整数的对应部分:

  • 0×55555555=0×01010101010101010101010101010101
  • 0xAAAAAAAA=0×10101010101010101010101010101010
  • 0×33333333=0×00110011001100110011001100110011
  • 0xCCCCCCCC=0×11001100110011001100110011001100
  • 0x0F0F0F0F=0×00001111000011110000111100001111
  • 0xF0F0F0F0=0×11110000111100001111000011110000
  • 0x00FF00FF=0×00000000111111110000000011111111
  • 0xFF00FF00=0×11111111000000001111111100000000
  • 0x0000FFFF=0000000000000000001111111111111111
  • 0xFFFF0000=1111111111111111110000000000000000

3. 一些常见的二进制操作

(1)增加删除末尾位

  • 删除末尾k位:x >> k
  • 末尾增加k位0:x << k
  • 末尾增加k位1:x << k | ((1 << k) – 1)

(2)修改右数第k位的值

  • 第k位取反:x ^ (1 << (k-1))
  • 第k位置1 :x | (1 << (k-1))
  • 第k位置0 :x & (~(1 << (k-1)))

(3)修改末尾k位

  • 末k位取反:x ^ ((1 << k) – 1)
  • 末k位置1: x | ((1 << k) – 1)
  • 末k位置0: x & (~((1 << k) – 1))

(4)修改末尾连续的01

  • 把末尾连续的1变0:x & (x + 1),如10011: 10011&10100=10000
  • 把末尾连续的0变1:x | (x – 1),如0100:10100|10011=10111
  • (5)取末尾连续的01

    • 取末尾连续的1:(x ^ (x + 1)) >> 1,如10111:(10111^11000)>>111
    • 取末尾连续的0(保留第一次出现的1):(x & (x ^ (x-1))),如10100:10100&(10100^10011)=100

    以上各种操作当k=1时有时更常用。另外,x&(x-1)可以把最后一个1消去,如10100:10100&10011=10000。

    4. 把一个数变为大于等于其的最小的2的幂

    算法的基本思想是把这个数的最高位的1左边全部变成1,即11…1的形式,然后整体再加1,即变成100…0的形式,即为所求的2的幂。

    C++代码如下。首先判断是否为2的幂,如果是的话不需要任何改变直接输出。否则采用一种类似于迭代的方法进行更改,执行完第1步后,每个位上的值为本身及左边1个数的或(共2个数),执行完第2步后,每个位上的值为本身及左边3个数的或(共4个数),……,执行完第5步后,每个位上的值为本身及左边31个数的或(共32个数)。于是显然最高位1的右边全部会变成1,左边则不受影响。最后再加一即可。

    int change2Pow(unsigned int n){
        if(!(n & (n-1))) return n;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return n + 1;
    }

    5. 计算二进制中1的个数

    经典问题,最简单的方法是逐位判断是否为1,同时计数,复杂度为数字的长度。

    int countBit1_1(int x){
    	int cnt = 0;
    	while (x) cnt += x & 0x01, x >>= 1;
    	return cnt;
    }

    方法二是每次消去最后出现的一个1,同时计数,复杂度为1的个数。

    int countBit1_2(int x){
    	int cnt = 0;
    	while (x) x &= (x-1), cnt++;
    	return cnt;
    }

    方法三如下。采用分治思想,第1步把相邻2位的1的个数相加,保存这4位中。第2步把相邻的4位的1的个数相加,保存到这4位中。……第5步把相邻的32位的1的个数相加,保存到这32位中,即保存到x中。

    int countBit1_3(int x){
    	x = (x & 0x55555555) + ((x >> 1) & 0x55555555); //相邻 2位相加
    	x = (x & 0x33333333) + ((x >> 1) & 0x33333333); //相邻 4位相加
    	x = (x & 0x0F0F0F0F) + ((x >> 1) & 0x0F0F0F0F); //相邻 8位相加
    	x = (x & 0x00FF00FF) + ((x >> 1) & 0x00FF00FF); //相邻16位相加
    	x = (x & 0x0000FFFF) + ((x >> 1) & 0x0000FFFF); //相邻32位相加
    	return x;
    }

    6. 计算二进制中1的个数的奇偶性

    可以采用5的方法先计算个数,然后再判断奇偶。也可以仿照方法三,采用分治思想,第1步统计相邻2位的1的个数奇偶性,保存到这2位的低位中。第2步统计相邻4位的1的个数奇偶性,保存到这4位的低位中。……第5步统计相邻2位的1的个数奇偶性,保存到这32位的低位中,即x的最低位。

    int bit1OddEven(int x){ //奇数个为1,偶数个为0
    	x ^= x >> 1;		//相邻 2位中1的奇偶性
    	x ^= x >> 2;		//相邻 4位中1的奇偶性
    	x ^= x >> 4;		//相邻 8位中1的奇偶性
    	x ^= x >> 8;		//相邻16位中1的奇偶性
    	x ^= x >> 16;		//相邻32位中1的奇偶性
    	return x & 1; 	
    }

    7. 翻转二进制数

    类似地,采用分治思想,逐步翻转整个二进制数。

    int reverseBit(int x){
    	x = (x & 0x55555555) >> 1 | (x & 0xAAAAAAAA) << 1;  //翻转相邻 2位
    	x = (x & 0x33333333) >> 2 | (x & 0xCCCCCCCC) << 2;  //翻转相邻 4位
    	x = (x & 0x0F0F0F0F) >> 4 | (x & 0xF0F0F0F0) << 4;  //翻转相邻 8位
    	x = (x & 0x00FF00FF) >> 8 | (x & 0xFF00FF00) << 8;  //翻转相邻16位
    	x = (x & 0x0000FFFF) >> 16 | (x & 0xFFFF0000) << 16;//翻转相邻32位
    	return x;
    }

    8. 统计二进制前导0、末尾0的个数

    采用递归思想进行。先排除为0的特殊情况。然后先看前16位是否全0,如果全0,增加计数,并把这个数左移16位删除已经计数的16个0。然后看前8位是否全0。一直到只剩一位时可以直接计算。

    统计末尾0的个数时思想类似,只是变成了统计后面16位、8位等是否全0。

    int countLeading0(unsigned int x){
    	if (!x) return 32;
    	int n = 1;
    	if ((x >> 16) == 0) n += 16, x <<= 16;
    	if ((x >> 24) == 0) n += 8, x <<= 8;
    	if ((x >> 28) == 0) n += 4, x <<= 4;
    	if ((x >> 30) == 0) n += 2, x <<= 2;
    	return n - (x >> 31);
    }
    int countTrailing0(unsigned int x)
    {
    	if (!x) return 32;
        int n = 1;
        if ((x << 16) == 0) n += 16, x >>= 16;
    	if ((x << 24) == 0) n += 8, x >>= 8;
    	if ((x << 28) == 0) n += 4, x >>= 4;
    	if ((x << 30) == 0) n += 2, x >>= 2;
    	return n - (x & 0x01);
    }

    9. 位运算加法

    根据加法的规则不难理解。

    int plus (int a,int b)
    {
    	int x = a ^ b, y = a & b;
    	while (y)
    	{
    		int tx = x, ty = y << 1;
    		x = tx ^ ty, y = tx & ty;
    	}
    	return x;
    }

    10. 格雷码(Gray码)

    格雷码是一组数的编码,相邻两个数的只有一位二进制位不同。另外,其最大数和最小数也只差一位二进制位。

    • 0到7二进制:000, 001, 010, 011, 100, 101, 110, 111
    • 0到7格雷码:000, 001, 011, 010, 110, 111, 101, 100

    二进制码->格雷码(编码):最左边一位不变,将每一位与左边一位异或,作为对应格雷码该位的值。 如求5=(101)2对应的格雷码,格雷码第一位(最左边)的1不变,第2位为原数的第2位与第1位的异或,为0^1=1,第3位为原数第3位与第2位的异或,为1^0=1,所得格雷码为(111)2=7。

    整体上可以看成把原数向右移动一位,则与原数异或的时候,所得结果的第i位即为原数的第i位与i-1位的异或,而结果的最高位是原数的最左边数与0的异或,保持不变。

    int dec2Gray(unsigned int x){ 
    	return x ^ (x >> 1); 
    }

    格雷码->二进制码(解码):最左边一位不变,从第二位起,将每位与左边一位解码后的值异或,作为该位解码后的值.

    如求7=(111)2对应的原二进制数,第1位(最左边)的1不变,第2位为原数的第2位的和结果的第1位异或,为1^1=0,第3位为原数的第3位和结果的第2位的异或,为1^0=1,所得二进制数为(101)2=5。整体上可以看成原二进制数每一位上的数为格雷码该位置及其左边所有数的异或,可以用方法1实现。

    方法2采用了二分的思想,每次把右边一半的值异或上左边一半的值。

    int gray2Dec1(unsigned int x){
    	unsigned int y = x;	
    	while (x >>= 1) y ^= x;
    	return y;
    }
    int gray2Dec2(unsigned int x){  
    	x ^= x >> 16;				
    	x ^= x >> 8;				
    	x ^= x >> 4;				
    	x ^= x >> 2;
    	x ^= x >> 1;
    	return x;
    }
    
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论