位运算操作技巧

Posted on

链接：https://zhuanlan.zhihu.com/p/147250351
来源：知乎

位运算的百度百科如下: 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

位操作的优势位运算是一种底层的运算，往往比我们普通的运算要快上许多许多位运算是最高效而且占用内存最少的算法操作，执行效率非常高位运算操作的是二进制数，会拥有一些二进制的特性，在实际问题可以方便运用位运算只需较低的空间需求位运算使用能使程序变得更加简洁和优美位运算可以表示一些状态集合运算符号下面的a和b都是整数类型，则：

  • 按位与a & b
  • 按位或a | b
  • 按位异或a ^ b
  • 按位取反~a
  • 左移a << b
  • 带符号右移a >> b

C语言中位运算符之间，按优先级顺序排列为优先级符号：

  1. ~
  2. <<、>>
  3. &
  4. ^
  5. |
  6. &=、^=、|=、<<=、>>=

概念简介以及技巧

and运算 &

判断奇偶数：对于除0以外的任意数x，使用x&1==1作为逻辑判断即可

1
2
3
4
if (x&1==1)
{
    
}

判断某个二进制位是否为1，比如第7位, 0x40转到二进制是0100 0000，代表第7位是1。
1
2
3
4
if (n&0x40)
{
    //TODO:添加你要处理的代码
}

字节读取

1
2
3
4
(x >>  0) & 0x000000ff	/* 获取第0个字节 */
(x >>  8) & 0x000000ff	/* 获取第1个字节 */
(x >> 16) & 0x000000ff	/* 获取第2个字节 */
(x >> 24) & 0x000000ff	/* 获取第3个字节 */

判断一个数是不是 2 的指数
1
2
3
4
bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

取余
1
2
3
4
5
6
//得到余数
int Yu(int num,int n)
{
	int i = 1 << n;
	return num&(i-1);
}

指定二进制位数截取：比如说16位二进制数A：1000 1000 1000 1000，如果你想获得A的哪一位，就把数字B：0000 0000 0000 0000的那一位设置为1.比如说我想获得A的第三位就把B的第三位数字设置为1，则B为0000 0000 0000 0100，之后A、B求与，结果若为0，说明A的第三位为0，结果为1，说明A的第三位为1。同理：若要获得A的第五位，就把B设置为0000 0000 0001 0000，之后再求与。通常在程序中数字B被称为掩码，就是专门用来测试某一位是否为0的数值。

统计二进制中 1 的个数：利用x=x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1会将该位变为0。

1
2
3
4
5
6
7
8
9
int Count(int x)
{   
    int sum=0;
    while(x)
    {   sum++;
        x=x&(x-1);
    }
    return sum;
}

or操作

生成组合编码，进行状态压缩：当把二进制当作集合使用时，可以用or操作来增加元素。稍后详见“把二进制码当作集合使用”。

合并编码：在对字节码进行加密时，加密后的两段bit需要重新合并成一个字节，这时就需要使用or操作。

求一个数的二进制表达中0的个数

1
2
3
4
5
6
7
8
9
10
int Grial(int x)
{
    int count = 0;
    while (x + 1)
    {
        count++;
        x |= (x + 1);
    }
    return count;
}

xor操作

两个整数交换变量名

1
2
3
4
5
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

判断两个数是否异号
1
2
3
4
5
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true

int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false

数据加密：将需要加密的内容看做A，密钥看做B，A ^ B=加密后的内容C。而解密时只需要将C ^ 密钥B=原内容A。如果没有密钥，就不能解密！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define KEY 0x86
int main()
{
    char p_data[16] = {"Hello World!"};
    char Encrypt[16]={0},Decode[16]={0};
    int i;
       
    for(i = 0; i < strlen(p_data); i++)
    {
		Encrypt[i] = p_data[i] ^ KEY;
	}
	
    for(i = 0; i < strlen(Encrypt); i++)
    {
	    Decode[i] = Encrypt[i] ^ KEY;
    }
	
    printf("Initial date:  %s\n",p_data);
    printf("Encrypt date:  %s\n",Encrypt);
    printf("Decode date:  %s\n",Decode);
	
    return 0;
}

数字判重：利用了二进制数的性质：x^y^y = x。我们可见，当同一个数累计进行两次xor操作，相当于自行抵销了，剩下的就是不重复的数。
1
2
3
4
5
6
7
int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
	        tmp = tmp ^ arr[i];
	    }
    return tmp;
}

not操作

交换符号

1
2
3
int reversal(int a) {
    return ~a + 1;
}

取绝对值（效率高）：

  • n>>31 取得n的符号：若n为正数，n>>31等于0；若n为负数，n>>31等于-1；若n为正数 n^0=0，数不变；若n为负数，有n^-1 需要计算n和-1的补码，然后进行异或运算，结果n变号并且为n的绝对值减1，再减去-1就是绝对值
    1
    2
    3
    4
    int abs(int n)
    {
      return (n ^ (n >> 31)) - (n >> 31);
    }
    也可以这样使用
    1
    2
    3
    4
    5
    int abs(int n) 
    {
      int i = n >> 31;
      return i == 0 ? n : (~n + 1);
    }
    从低位到高位，将n的第m位置1。将1左移m-1位找到第m位，得到000…1…000，n在和这个数做或运算
    1
    2
    3
    4
    int setBitToOne(int n, int m)
    {  
        return n | (1 << (m-1));  
    }
    同理从低位到高位，将n的第m位置0，代码如下
    1
    2
    3
    4
    int setBitToZero(int n, int m)
    {  
        return n & ~(1 << (m-1));  
    }

    shl操作 & shr操作

    求2的N次方1<<n

高低位交换

1
2
unsigned short a = 34520;
a = (a >> 8) | (a << 8);

进行二进制逆序
1
2
3
4
5
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);

获得int型最大最小值
1
2
3
4
5
6
7
8
int getMaxInt()
{
    return (1 << 31) - 1;//2147483647， 由于优先级关系，括号不可省略
}
int getMinInt()
{
    return 1 << 31;//-2147483648
}

m的n次方
1
2
3
4
5
6
7
8
9
10
11
12
//自己重写的pow()方法
int pow(int m , int n){
    int sum = 1;
    while(n != 0){
        if(n & 1 == 1){
            sum *= m;
        }
        m *= m;
        n = n >> 1;
    }
    return sum;
}

找出不大于N的最大的2的幂指数
1
2
3
4
5
6
7
int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}

二分查找32位整数的前导0个数
1
2
3
4
5
6
7
8
9
10
11
12
13
int nlz(unsigned x)
{
   int n;

   if (x == 0) return(32);
   n = 1;
   if ((x >> 16) == 0) {n = n +16; x = x <<16;}
   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
   if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
   if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
   n = n - (x >> 31);
   return n;
}

位图的操作

将 x 的第 n 位置1，可以通过 x |= (x << n) 来实现set_bit(char x, int n);

将 x 的第 n 位清0，可以通过 x &= ~(1 << n) 来实现clr_bit(char x, int n);

取出 x 的第 n 位的值，可以通过 (x >> n) & 1 来实现get_bit(char x, int n);

如下:

1
2
3
#define clr_bit(x, n) ( (x) &= ~(1 << (n)) )
#define set_bit(x, n) ( (x) |= (1 << (n)) )
#define get_bit(x, n) ( ((x)>>(n)) & 1 )