跳转至

位运算

位运算就是把整数转换为二进制后,每位进行相应的运算得到结果。

常用的运算符共 6 种,分别为与(&)、或(|)、异或(^)、取反(~)、左移(<<) 和右移(>>)。

与、或、异或

与(&)或(|)和异或(^)这三者都是两者间的运算,因此在这里一起讲解。

表示把两个整数分别转换为二进制后各位逐一比较。

运算符 解释
& 只有在两个(对应位数中)都为 1 时才为 1
| 只要在两个(对应位数中)有一个 1 时就为 1
^ 只有两个(对应位数)不同时才为 1

^ 运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即 (a ^ b) ^ b = a

举例:

\begin{aligned} &5&=&&(101)_2\\ &6&=&&(110)_2\\ &5\tt\,\&\,6\rm&=&&(100)_2&=\ 4\\ &5\tt\,|\,\rm6&=&&(111)_2&=\ 7\\ &5\tt\,\text{^}\,\rm6&=&&(011)_2&=\ 3\\ \end{aligned}

取反

取反是对 1 个数 num 进行的计算。

~ num 的补码中的 0 和 1 全部取反 (0 变为 1,1 变为 0)。

补码——正数的补码为其(二进制)本身,负数的补码是其(二进制)取反后 +1

举例:

\begin{aligned} 5=(0000\ 0101)_2\\ 5\ \text{的补码} =(1111\ 1010)_2\\ \tt\ \text{~}\rm5=(1111\ 1010)_2 \end{aligned}

左移和右移

与前面的 4 种运算相似,这两种运算仍是把整数转换为二进制后进行操作。

左移(<<) 将转化为二进制后的数字整体向左移动。

num << i // 表示将 num 转换为二进制后向左移动 i 位(所得的值)

右移(>>) 将转化为二进制后的数字整体向右移动。

num >> i // 表示将 num 转换为二进制后向左移动 i 位(所得的值)

举例:

\begin{aligned} &5&&=&&(00000101)_2\\ &5\tt\,<<\,\rm1&&=&&(00001010)_2\!\!\!&=&&\!\!\!20\\ &5\tt>>\rm1&&=&&(00000010)_2&=&&2 \end{aligned}

在 C++ 中,右移操作中右侧多余的位将会被舍弃。而左侧较为复杂:对于无符号数,会在左侧补 0;而对于有符号数,则会用最高位的数补齐(Replicate most significant bit on left)。

注意:

  1. 左移和右移是有返回值的,并非对 num 本身进行操作。
  2. 左移和右移的优先级低于四则运算符,例如 x<<1+1 会被解释为 x<<(1+1) ,所以必要的时候,要使用括号。

位运算的应用

如果 num 是正数,num << i 相当于 num 乘以 2 的 i 次方,而 num >> i 相当于 num 除以 2 的 i 次方。 (位运算比 %/ 操作快得多) (据 2018JSOI 夏令营,效率可以提高 60%)

Warning

为什么要强调是正数呢?考虑一下 -1 >> 3

num * 10 = (num<<1) + (num<<3)

num & 1 相当于取 num 二进制的最末位,可用于判断 num 的奇偶性,二进制的最末位为 0 表示该数为偶数,最末位为 1 表示该数为奇数。

1
2
3
4
5
6
// 利用位运算的快捷的 swap 代码
void swap(int &a, int &b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
}

一个数的二进制表示可以看作是一个集合(0 表示不在集合中,1 表示在集合中)。比如集合 {1, 3, 4, 8},可以表示成 0b00000000000000000000000100011010,十进制就是 2^8+2^4+2^3+2^1=282

而对应的位运算也就可以看作是对集合进行的操作。

操作 集合表示 位运算语句
交集 a \cap b a & b
并集 a \cup b a | b
补集 \bar{a} ~a
差集 a \setminus b ~a
对称差 a\triangle b a ^ b

位运算的常用方法

  • 乘以 2 运算。

    1
    2
    3
    int mulTwo(int n) {  // 计算 n*2
      return n << 1;
    }
    
  • 除以 2 运算。

    1
    2
    3
    int divTwo(int n) {  // 负奇数的运算不可用
      return n >> 1;     // 除以 2
    }
    
  • 乘以 2 的 m 次方。

    1
    2
    3
    int mulTwoPower(int n, int m) {  // 计算 n*(2^m)
      return n << m;
    }
    
  • 除以 2 的 m 次方。

    1
    2
    3
    int divTwoPower(int n, int m) {  // 计算 n/(2^m)
      return n >> m;
    }
    
  • 判断一个数的奇偶性。

    1
    boolean isOddNumber(int n) { return n & 1; }
    
  • 取绝对值(某些机器上,效率比 n > 0 ? n : -n 高)。

    1
    2
    3
    4
    5
    6
    7
    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 就是绝对值 */
    }
    
  • 取两个数的最大值(某些机器上,效率比 a > b ? a : b 高)。

    1
    2
    3
    4
    int max(int a, int b) {
      return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
      /* 如果 a>=b,(a-b)>>31 为 0,否则为 - 1 */
    }
    
  • 取两个数的最小值(某些机器上,效率比 a > b ? b : a 高)。

    1
    2
    3
    4
    int min(int a, int b) {
      return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
      /* 如果 a>=b,(a-b)>>31 为 0,否则为 - 1 */
    }
    
  • 判断符号是否相同。

    1
    2
    3
    4
    boolean isSameSign(int x, int y) {  // 有 0 的情况例外
      return (x ^ y) >=
             0;  // true 表示 x 和 y 有相同的符号,false 表示 x,y 有相反的符号。
    }
    
  • 计算 2 的 n 次方。

    1
    2
    3
    int getFactorialofTwo(int n) {  // n > 0
      return 1 << n;                // 2 的 n 次方
    }
    
  • 判断一个数是不是 2 的幂。

    1
    2
    3
    4
    5
    boolean isFactorialofTwo(int n) {
      return n > 0 ? (n & (n - 1)) == 0 : false;
      /* 如果是 2 的幂,n 一定是 100... n-1 就是 1111....
         所以做与运算结果为 0 */
    }
    
  • 对 2 的 n 次方取余。

    1
    2
    3
    4
    5
    int quyu(int m, int n) {  // n 为 2 的次方
      return m & (n - 1);
      /* 如果是 2 的幂,n 一定是 100... n-1 就是 1111....
         所以做与运算结果保留 m 在 n 范围的非 0 的位 */
    }
    
  • 求两个整数的平均值。

    1
    2
    3
    int getAverage(int x, int y) {
      return (x + y) >> 1;
      
    
  • 遍历一个集合的子集

    1
    2
    3
    4
    int b = 0;
    do {
      // process subset b
    } while (b = (b - x) & x);
    

题目推荐

CODEVS 2743 黑白棋游戏

参考

位运算技巧:https://graphics.stanford.edu/~seander/bithacks.html


评论