远航休息栈
首页 > 笔记 > 位运算技巧

位运算技巧

写一些常用的位运算的小技巧

其实就是一些简单的常数优化，但可以让程序简单易读，更有逼格

C/C++语言提供的位运算符有：

images

结果

images

初步了解以后，就开始学习一些小技巧吧

1、奇偶性判断

没学位运算前，我们这么写

bool check(int value)
{
	if(value % 2 == 0)
		return false;
	else
		return true;
}
//加以优化
bool check(int value)
{
	return (value % 2 != 0);
}

要知道，上面的代码我们使用的是对2取余，如果操作数value是小数的话，还勉强行得通，但是value是一个上百万的大数，那么这就白白浪费了CPU的大量时间，程序的效率和性能就很差。我们知道任何数在计算机储存中都是以二进制储存的，细心的你就会发现在二进制的最小一位有个特点，为0就是偶数，为1就是奇数，按照这个原理我们根本没必要让CPU白白做那么多的工作，只要一步判断就可以了。接下来就让我们看看位运算的精妙之处！

那么我们的目的就是判断最小位是0还是1，可是我们怎么判断呢？我们要用位运算阿里判断，就是与或非。在上面的复习之中我们只说了位运算的计算方法，并没有说其用处。那么在这里我们用到的就是“与”！与运算特有的一个功能就是判断指定位上的值（0或1）。我们来看下面的表格（与运算）。

images

我们要注意一下这里的 操作数2 ，它只有最低位是1，其余位都是0，这就是关键所在，操作数1是随机值。我们看看结果只会有两种结果：0或1。这个结果就取决于操作数1的最低位，它为1时就为1，为0时就为0.

“那么我要判断的是第二位呢？”

好！那我们就把操作数2改为 00000010 那么结果就只会有 00000000 或 00000010 其结果取决于第二位。

有了这个基础那么我们来看看怎么用位运算判断奇偶性吧：

bool check(int value)
{
	if(value & 0x0001 == 0)
		return false;
	else
		return true;
}
//加以优化
bool check(int value)
{
	return (value & 1 != 0);
}
//在简化
#define	PARITY(value) (value&1)

总结

使用a%2来判断奇偶性和a & 1是一样的作用，但是a & 1要快好多。

2、  判断n是否是2的正整数冪

所谓2的正整数冪就是指 2，4，8，16，32，64，128，256，512，1024，2018………….等数字，若何判断一个数是否是这样的数呢？我们看看不用位运算的计算方法：

#include <math.h>
bool IsPowerOfTwo(int value)
{
	for(int i = 0,l = 8*sizeof(value); i < l ;i++)
	    if(pow(2,i) == value)
		return true;
	return false;
}

在这个算法中，我们使用了一个循环。其原理非常简单就是一一的对比，但是其中还调用了数学函数库，效率大大降低。接下来我们讲讲怎样用位运算来判断。我们首先要研究一下这些数的特性，请看下表（与运算）：

images

我们发现 n&（n-1） =  0  我们可以 用逻辑非 ！（n&（n-1）） =  1 。那是不是这样就可以了呢，你会发现 ！（0&（0-1）） =  1 但是 0并不是 2的正整数冪。我们可以用 逻辑与 ！（n&（n-1）） &&  n  = 1;请看下面的代码：

bool IsPowerOfTwo(INT value)
{
	if((!(n&(n-1)) ) && n == 1)
		return true;
	else
		return false;
}
//简化
#define	ISPOWEROFTWO(n) ((!(n&(n-1)) ) && n)

3、获得int最大值（不码字了，累死了）

int getMaxInt(){  
        return (1 << 31) - 1;//2147483647， 由于优先级关系，括号不可省略  
}

4、获得int最小值

int getMinInt(){  
    return 1 << 31;//-2147483648  
 }

5、获得long的最大值

long getMaxLong(){  
    return ((unsigned long) - 1) >> 1;//2147483647  
}

6、乘2运算

int mulTwo(int n){//计算n*2   
    return n << 1;  
}

7、除以2运算

int divTwo(int n){//负奇数的运算不可用  
    return n >> 1;//除以2  
}

8、乘2的m次方

int mulTwoPower(int n,int m){//计算n*(2^m)  
    return n << m;  
}

9、除以2的m次方

int divTwoPower(int n,int m){//计算n/(2^m)  
    return n >> m;  
}

10、直接交换两个数

void swap(int *a,int *b){     
    (*a) ^= (*b) ^= (*a) ^= (*b);     
}

11、取绝对值

int abs(int n){  
return (n ^ (n >> 31)) - (n >> 31);  
/* n>>31 取得n的符号，若n为正数，n>>31等于0，若n为负数，n>>31等于-1 
若n为正数 n^0=0,数不变，若n为负数有n^-1 需要计算n和-1的补码，然后进行异或运算， 
结果n变号并且为n的绝对值减1，再减去-1就是绝对值 */  
}

12、求两个数的最小值

int min(int x,int y){  
    return y ^ ((x ^ y) & -(x < y));  
         /*如果x<y x<y返回1，否则返回0， 
            与0做与运算结果为0，与-1做与运算结果不变*/  
}

13、判断符号是否相同

boolean isSameSign(int x, int y){ //有0的情况例外  
    return (x ^ y) >= 0; // true 表示 x和y有相同的符号， false表示x，y有相反的符号。  
}

14、对2的n次方取余

int quyu(int m,int n){//n为2的次方  
    return m & (n - 1);  
    /*如果是2的幂，n一定是100... n-1就是1111.... 
     所以做与运算结果保留m在n范围的非0的位*/  
}

15、平均数

int getAverage(int x, int y){  
        return (x + y) >> 1;   
｝