MENU

位运算总结

April 8, 2018 • 文章

位运算,相比普通的代码最大的优点就是其带来的高效性,也因此可以常在底层源码中看见它们的踪影。

本文就位运算常见的操作作一个总结,若您另有关于位运算巧妙的运用可以于底部留言区留言。

首先还是先来回顾下位操作的基础知识。

相关基础

1. 与运算

与运算符"&"是双目运算符。只有对应的两个二进位均为1时,结果位才为1,否则为0。例如:

9 & 5 = 00001001
      & 00000101
      = 00000001
      = 1

2. 或运算

或运算符"|"是双目运算符。只要对应的两个二进位有一个为1时,结果位就为1。例如:

9 | 5 = 00001001
      | 00000101
      = 00001101
      = 13

3. 非运算

非运算符" ~ "为单目运算符。其功能是对参与运算的各二进位求反。例如:

~ 9 = ~ 00001001
    =   11110110
    =   -10

4. 异或运算

异或运算符" ^ "是双目运算符。其功能是对参与运算的二进位相异或,即当两二进位相异时,结果为1,相同就为0。例如:

9 ^ 5 = 00001001
      ^ 00000101
      = 00001100
      = 12

5. 左移和右移

例1例2
x0110001110010101
x << 40011000001010000
x >> 4(逻辑右移)0000011000001001
x >> 4(算术右移)0000011011111001

左移动就是向左移动k位,丢弃最高的k位,并在右端补k个0,也就是常说的当前值乘以2的k次方。

右移动的原理也是相同的,右移k位就是当前数除以2的k次方。唯一不同的是分为逻辑右移和算术右移。

逻辑右移就是无符号移位,右移几位,就在左端补几个0。

算术右移动是有符号移位,和逻辑右移不同的是,算术右移是在左端补k个最高有效位的值,如此看着有些奇特,但对有符号整数数据的运算非常有用。我们知道有符号的数,首位字节,是用来表示数字的正负(1为负)。负数采用补码形式来存储,比如-26(11100110),算术右移1位之后-13(11110011)。如若不是补最高有效位的值1而是补作0的话,右移之后就变成正数了。

经典应用

1. i+(~i)=-1

i取反再与i相加,相当于把所有二进制位设为1,其十进制结果为-1。

2. 计算n+1与n-1

-~n == n + 1,~n为其取反,负号 ' - ' 再对其取反并加1。

~-n == n - 1,思路就是找到最低位的第一个1,对其取反并把该位后的所有位也取反,即01001000变为01000111

3. 取相反数

思路就是取反并加1,也即~n + 1或者(n ^ -1) + 1

4. if(x == a) x = b; if(x == b) x = a;

利用^运算符的性质,即得x = a ^ b ^ x

5. n倍数补全

当n为2的幂时,(x + n - 1) & ~(n - 1)会找到第一个大于x的数,且它正好是n的整数倍。

6. 求二进制中1的个数

/* Version 1 */
int count_bits(int n)
{
    return n ? (n & 1) + count_bits(n >> 1) : 0;
}

/* Version 2 */
int count_bits(int n)
{
     x = (x & 0x55555555) + ((x >> 1)  & 0x55555555);
     x = (x & 0x33333333) + ((x >> 2)  & 0x33333333);
     x = (x & 0x0f0f0f0f) + ((x >> 4)  & 0x0f0f0f0f);
     x = (x & 0x00ff00ff) + ((x >> 8)  & 0x00ff00ff);
     x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
  
     return x;
}

关于第二个版本,分析如下:(摘自Matrix67-位运算,并作稍微修改)

以十进制数211为例,其二进制为11010011,

| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |   <— 原数
+---+---+---+---+---+---+---+---+
|  1 0  |  0 1  |  0 0  |  1 0  |   <— 第一次运算后
+-------+-------+-------+-------+
|    0 0 1 1    |    0 0 1 0    |   <— 第二次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |   <— 第三次运算后,得数为 5
+-------------------------------+

整个程序是一个分治的思想。第一次我们把每相邻的两位加起来,得到每两位里1的个数,比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加,10+01=11,00+10=10,得到的结果是00110010,它表示原数前4位有3个1,末4位有2个1。最后一次我们把0011和0010加起来,得到的就是整个二进制中1的个数。

7. 判断二进制中1的奇偶性

x = x ^ (x >> 1);
x = x ^ (x >> 2);
x = x ^ (x >> 4);
x = x ^ (x >> 8);
x = x ^ (x >> 16);

cout << (x & 1) << endl; // 输出 1 为奇数

以下分析摘自Matrix67-位运算,并作稍微修改,

以十进制数1314520为例,其二进制为0001 0100 0000 1110 1101 1000。

第一次异或操作的结果如下:

  0001 0100 0000 1110 1101 1000
^ 0000 1010 0000 0111 0110 1100
= 0001 1110 0000 1001 1011 0100

得到的结果是一个新的二进制数,其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如,最右边那个0表示原数末两位有偶数个1,右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。

对这个数进行第二次异或的结果如下:

  0001 1110 0000 1001 1011 0100
^ 0000 0111 1000 0010 0110 1101
= 0001 1001 1000 1011 1101 1001

结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1,每个0就表示原数对应的四个位置上共偶数个1。

一直做到第五次异或结束后,得到的二进制数的最末位就表示整个32位数里1的奇偶性。

8. 判断奇偶性

/* 判断是否是奇数 */
bool is_odd(int n)
{
    return (n & 1 == 1);
}

9. 不用临时变量交换两个数

/* 此方法对 a 和 b 相等的情况不适用 */
a ^= b;  
b ^= a;  // 相当于 b = b ^ ( a ^ b );
a ^= b; 

10. 取绝对值

/* 注意:以下的数字 31 是针对 int 大小为 32 而言 */
int abs(int n)
{  
    return (n ^ (n >> 31)) - (n >> 31);  
} 

其中n >> 31取得n的正负号。

  • 若n为正数,n >> 31的所有位等于0,其值等于0。表达式转化为n ^ 0 - 0,等于n;
  • 若n为负数,n >> 31的所有位等于1,其值等于-1。表达式转化为(n ^ -1) + 1,这很好理解,负数的相反数就是对其补码取反再加1,(n ^ -1) + 1就是在做这样的事。

11. 取两数的较大值

/* 注意:以下的数字 31 是针对 int 大小为 32 而言 */
int max(int a, int b)
{
    return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}  

如果a >= b(a - b) >> 31为0,否则为-1。

12. 判断符号是否相同

/* 若 x,y 都为 0,输出真;若只有一个为 0,不会报错但运行结果是错的,因为 0 没有正负之分 */
bool is_same_sign(int x, int y)
{
    return (x ^ y) >= 0;
}  

13. 判断一个数是不是2的幂

bool is_power_of_two(int n)
{
    return (n > 0) ? (n & (n - 1)) == 0 : false;
}  

如果是2的幂,n - 1就是把n的二进制的最低的那个1取反为0,并把后面的0全部取反为1。

14. 取余2的幂次方

/* 其中 m 为 2 的幂次方,并对 m 取余 */
int mod(int n, int m)
{
    return n & (m - 1);  
}

参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. HT HT

    涨知识了