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

位运算应用技巧(1)

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

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

一 整数的计算机表示

位运算需要操作内存中整数的二进制位,首先肯定要知道整数在计算机中是怎么表示的。整数分为原码、反码和补码三种表示。

  • 原码就是符号位加上真值的绝对值,最高位为符号位(正数的符号位为0,负数的为1),比如8位的二进制数:
            [+1] = [0000 0001]
            [-1] = [1000 0001]
  • 正数的反码是其本身。负数的反码是在原码的基础上,符号位不变,其余位取反。如
            [+1] = [00000001] = [00000001]
            [-1] = [10000001] = [11111110]
  • 整数的补码是其本身。负数的补码在原码的基础上,符号为不变,其余位取反,最后加1,也就是在反码的基础上加1。如
            [+1] = [00000001] = [00000001] = [00000001]
            [-1] = [10000001] = [11111110] = [11111111]

整数在计算机内的表示即为补码表示法,目的是为了在运算时让符号位也参与运算,方便执行,这里不详细讨论。

二 位运算基础

位运算包括按位取反、按位与、按位或、按位异或、按位左移、按位右移共六种运算,运算直接在数据的二进制补码形式上进行。

取反运算(~a)表示把一个数的每个二进制位取反,0变1,1变0。这里需要特别注意原来数据的数据类型,如果是有符号数据,取反会把最高位的符号为也同时取反。

与运算(a&b)、或运算(a|b)、异或运算(a^b)把两个数的二进制位对齐后逐个进行相应的位运算。

这里讲一下异或的运算规则,两个位相异时结果为1,相同时结果为0。或者另一种理解,有时会更有用,异或1不变,异或0取反。

左移运算(a<<n)把a的二进制向左移动n位,右端补0。右移运算(a>>n)把a的二进制位向右移动n为,左端补符号位。这里对正数的移位操作没什么问题,关键是负数的,例子如下

  • [-9] = [10... 0000 1001] = [11... 1111 0110] = [11... 1111 0111]
  • 左移2位,右边补0,得[-9]<<2 = [11...1101 1100] = 0xf…fd = [-36]
  • 右移2位,左边补1,得[-1]>>2 = [11...1111 1101] = 0xf…fd = [-3]

代码验证如下:

void test(){
	int i = -9, j = (i << 2), k = (i >> 2);
	printf("%3d: 0x%x\n", i, i); // -9: 0xfffffff7
	printf("%3d: 0x%x\n", j, j); //-36: 0xffffffdc
	printf("%3d: 0x%x\n", k, k); // -3: 0xfffffffd
}

Note:有些系统右移时左边始终补0。

三 位运算简单应用

1. 求Int整数的最大值和最小值。

利用C++中Int是32位的特点进行移位,其他可以类型可以类似得到。

int getMinInt(){ return 1 << 31; }
int getMaxInt1(){ return (1 << 31) - 1; }
int getMaxInt2(){ return ~(1 << 31); }
int getMaxInt3(){ return ((unsigned int) - 1) >> 1; }

2. 对2的幂的乘法、除法或取模

当幂为1的特殊情况可能会更加常用。利用2^n=(1<<n)求2的幂也非常常用。

int mul2(int x){ return x << 1; } //x * 2 
int div2(int x){ return x >> 1; } // x / 2
int mod2(int x){ return x & 1; } // x % 2
int mul2exp(int x, int n){ return x << n; } // x * 2^n
int div2exp(int x, int n){ return x >> n; } // x / 2^n
int mod2exp(int x, int n){ return x & ((1 << n) - 1); } // x % 2^n

3. 判断奇偶

对直接上面模2的结果的简单应用。

void oddOrEven(int n){
	if (n & 1)		printf("%d is奇数\n", n);
	if (!(n & 1))	printf("%d is偶数\n", n);
}

4. 不用辅助变量交换两个数

void swap(int &a, int &b){
	//方法1
	a = a + b;	b = a - b;	a = a - b;
	//方法2
	a ^= b;  b ^= a;  a ^= b;
	//方法3
	a ^= b ^= a ^= b;
}

使用加法交换可能会溢出。

5. 求绝对值

对于方法一(方法二类似):

  • 如果n为正数,符号位为0,n>>31=0,原式=n^0-0=n-0=n。
  • 如果n为负数,符号位为1,n>>31=-1,原始=(n^(-1))-(-1)=|n|。这里涉及到负数的补码形式。以n=-5为例,(-5) ^ (-1) = 1…100 ^ 1…000 = 0…100 = 4, 4 -(-1)=5
int getABS1(int n){
	return (n ^ (n >> 31)) - (n >> 31);
}
int getABS2(int n){
	return n ^ (~(n >> 31) + 1) + (n >> 31);
}

6. 求平均值

对于方法二,由与的特点,a&b是a和b均为1的位的平均值。a和b均为0的位的平均值也为0,可以忽略。由异或的特点,(a^b)>>1是a和b不同的为的平均值,相加即为a和b整体的平均值。

int getAverage1(int a, int b){
	return (a + b) >> 1;	//加法可能溢出
}
int getAverage2(int a, int b){
	return (a & b) + ((a ^ b) >> 1);
}

7. 求两个数较大、较小值

利用一点,对于任何数a,因为0的二进制全为0,有a&0 = 0,因为-1的二进制全为1,有a&(-1) = a

  • 如果a>b,a<b的值为0,-(a<b)也为0,(a ^ b) & 0 = 0, a ^ 0 = a。
  • 如果a<b,a<b的值为1,-(a<b)为-1,(a ^ b) & (-1) = a ^ b, a ^ (a ^ b) = b。

于是能求得较大值。较小值类似。

int getMax(int a, int b){
	return a ^ ((a ^ b) & -(a < b));
}
int getMin(int a, int b){
	return b ^ ((a ^ b) & -(a < b)); 
}

8. 位修改

获取x的二进制表示中从右到左第N位,或置为1,或置为0:

int getBitN(int x, int n){
	return (x >> (n - 1)) & 1;
}
int setBitN1(int x, int n){
	return x | (1 << (n - 1));
}
int setBitN0(int x, int n){
	return x & ~(1 << (n - 1));
}
上一篇: 下一篇:

我的博客

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

站内搜索

最新评论