二进制位计算的总结

Posted on   |   In   |  

介绍二进制位操作的技巧

最近在刷题的时候遇到很多位操作的题，毕竟以前是学通信的，对于位操作还是有很多美好的记忆的，现归纳总结

位操作

包括位运算符和移位操作
位运算符包括&(与and), |(或or), ~(非not), ^(异或xor),
not运算的定义是把内存中的0和1全部取反，
对于无符号类型，取反后的效果就是把这个数在数轴上的位置“对称翻折到另一边去”，因为无符号类型的数是用$0000到$FFFF依次表示的。
而对于有符号的类型，取反后最高位的变化导致了正负颠倒，又因为负数储存使用补码，所以效果就是变为-a-1。这与上下界没有任何关系。
移位包括左移和右移。
左移(shl): 各二进位全部左移若干位，高位丢弃，低位补0.
右移(shr): 分为逻辑右移和算术右移,各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）,对于有符号数，一般是算术右移。
1)负数的右移：负数右移的话(符号位为1)，由于要保持它是负数，所以负数的二进制的右边补1。如果一直右移的话，最后就就变成0xFFFFFFFF 即-1
如： -4>>1 为-2 ；-4>>2为-1
2)负数的左移：跟正整数左移一样，右边补0，一直左移的话，最后就是0啦。-2<<2为-4 ； -2<<31为0
注意,下面的右移是逻辑右移

功能 示例 位运算
去掉最后一位 (101101->10110) x >> 1
在最后加一个0 (101101->1011010) x << 1
在最后加一个1 (101101->1011011) (x << 1) + 1
把最后一位变成1 (101100->101101) x or 1
把最后一位变成0 (101101->101100) x or 1 - 1
最后一位取反 (101101->101100) x ^ 1
把右数第k位变成1 (101001->101101,k=3) x or (1 << (k-1))
把右数第k位变成0 (101101->101001,k=3) x and not (1 << (k-1))
右数第k位取反 (101001->101101,k=3) x ^ (1 << (k-1))
取末三位 (1101101->101) x and 7
取末k位 (1101101->1101,k=5） x and( (1 << k) -1)即 x and $2^k-1)$
取右数第k位 (1101101->1,k=4) x >> (k-1) and 1
把末k位变成1 (101001->101111,k=4) x or ((1<< k)-1) 即 x or $2^k - 1$
末k位取反 (101001->100110,k=4) x xor ( (1 << k) -1)即 x ^ $2^k-1$
把右边连续的1变成0 (100101111->100100000) x and (x+1)
把右起第一个0变成1 (100101111->100111111) x or (x+1)
把右起第一个1变成0 11011000->11010000 x and (x-1)
把右边连续的0变成1 (11011000->11011111) x or (x-1)
取右边连续的1 (100101111->1111) (x ^ (x+1)) << 1
去掉右起第一个1的左边 (100101000->1000) x and (x xor (x-1))或者 x & (-x)

位操作技巧

巧妙利用位操作，可以提高程序的效率，例如乘以2，直接用左移，速度会快很多。

判断奇偶

只需要判断二进制表示的最后一位是不是为1

1
num & 1;

交换两数

利用a^b^a = b

1
2
3
4
5
6
7
8
9
10
11

int a= 2, b = 3;
/*
a = a^b;
b = b^a;
a = a^b;
*/

a ^= b;
b ^= a;
a ^= b;

变换符号

主要是补码和反码的知识，以后来补;
如对于-11和11，可以通过下面的变换方法将-11变成11

1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)

同样可以这样的将11变成-11

0000 1011(二进制) –取反-> 1111 0100(二进制) –加1-> 1111 0101(二进制)

求绝对值

类似于上面的符号变换

计算一个数的二进制1的个数

书面称作hammingWeight
number-of-1-bits
第一种方法

1
2
3
4
5
6
7
8
9
/*这种方法只对无符号数有效，有符号数使用将会陷入死循环*/
int hammingWeight(uint32_t n) {
        int count = 0;
        while(n){
            if(n&1)  count++;
            n = n>>1;
        }
        return count;
    }

1
2
3
4
5
6
7
8
9
int hammingWeight(int n){
    int count = 0;
    int flag = 1;
    while(n){
        if(n & flag) count++;
        flag<<1;
    }
    return count;
}

另一种方法：利用n&(n-1)消除最后一位的1.

1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
        int count = 0;
        
        while(n){
            count++;
            n = n &(n-1);
        }
        return count;
    }

Power Of Two

一个数是2的次方，那么这个数的二进制一定是最高位为1，其他位是0

1
2
3
bool isPowerOfTwo(int n) {
       return (n>0)&&(!(n&(n-1)));
   }

更多技巧详见

一些题目

Counting Bits

Reverse Bits

Number of 1 bits

Power Of Two

Bitmap

Bitmap又称位图，
这里有一篇利用bit位优化素数查找的文章
http://blog.csdn.net/morewindows/article/details/7354571
这篇文章很好的介绍了位操作
参见另一篇文章bitmap
参阅:
http://www.matrix67.com/blog/archives/263