位运算

简介

位运算（bitwise operation）就是将数转换为二进制逐位运算。通常在处理器上，位运算的效率比乘除法高。

位运算

非（NOT）

非运算会对一个二进制数的每一位执行逻辑非运算，即取反，将\(0\)变成\(1\)，将\(1\)变成\(0\)。
在大多数编程语言中，其符号为~。 \[ \begin{align} \mathrm{NOT} \ & 0111 \ (= (7)_{10}) \\ = \ & 1000 \ (= (8)_{10}) \end{align} \]

非运算的结果是值的二进制补码减一，即\(\mathrm{NOT} \ x = -x - 1\)。

与（AND）

与运算对两个相同长度的二进制数每一组对应的bit进行比较并执行逻辑与运算，相当于将它们相乘。若两个bit都为\(1\)，则结果为\(1\)（\(1 \times 1 = 1\)）；否则结果为\(0\)（\(1 \times 0 = 0, 0 \times 0 = 0\)）。
在大多数编程语言中，其符号为&。 \[ \begin{align} & 0101 \ (= (5)_{10}) \\ \mathrm{AND} \ & 0011 \ (= (3)_{10}) \\ = \ & 0001 \ (= (1)_{10}) \end{align} \]

与运算可以用于确认某一位是\(1\)还是\(0\)。
例如，对于给定的数\(0011 \ (= (3)_{10})\)，我们要确认第\(2\)位是否是\(1\)，我们可以将其与\(0010\)（只有第\(2\)位是\(1\)）进行与运算： \[ \begin{align} & 0011 \ (= (3)_{10}) \\ \mathrm{AND} \ & 0010 \ (= (2)_{10}) \\ = \ & 0010 \ (= (2)_{10}) \end{align} \] 由于结果\(0010\)不为\(0\)，所以我们知道原数的第\(2\)位是\(1\)。这被称为位掩码（bit mask）。

与运算可以将某一位设置为\(0\)。例如，我们要把\(0110 \ (= (6)_{10})\)的第\(3\)位设置为\(0\)，可以将其与\(1011\)（只有第\(3\)位是\(0\)）进行与运算： \[ \begin{align} & 0110 \ (= (6)_{10}) \\ \mathrm{AND} \ & 1011 \ (= (11)_{10}) \\ = \ & 0010 \ (= (2)_{10}) \end{align} \]

由于这个属性，二进制数的奇偶校验就很方便了： \[ \begin{align} & 0110 \ (= (6)_{10}) \\ \mathrm{AND} \ & 0001 \ (= (1)_{10}) \\ = \ & 0000 \ (= (0)_{10}) \end{align} \] 因为\(6 \ \mathrm{AND} \ 1 = 0\)，所以\(6\)可以被\(2\)整除，因此\(6\)是偶数。

或（OR）

或运算对两个相同长度的二进制数每一组对应的bit进行比较并执行逻辑或运算。若两个bit都为\(0\)，则结果为\(0\)；否则结果为\(1\)。
在大多数编程语言中，其符号为|。 \[ \begin{align} & 0101 \ (= (5)_{10}) \\ \mathrm{OR} \ & 0011 \ (= (3)_{10}) \\ = \ & 0111 \ (= (7)_{10}) \end{align} \]

或运算可以将某一位设置为\(1\)。例如，我们要把\(0110 \ (= (6)_{10})\)的第\(4\)位设置为\(1\)，可以将其与\(1000\)（只有第\(4\)位是\(1\)）进行或运算： \[ \begin{align} & 0110 \ (= (6)_{10}) \\ \mathrm{OR} \ & 1000 \ (= (8)_{10}) \\ = \ & 1110 \ (= (14)_{10}) \end{align} \]

异或（XOR）

异或运算对两个相同长度的二进制数每一组对应的bit进行比较并执行逻辑异或运算。若只有其中一个bit为\(1\)，则结果为\(1\)；否则结果为\(0\)。即两者状态不同，结果为\(1\)；两者状态相同，结果为\(0\)。
在大多数编程语言中，其符号为^。数学中还可以用符号\(\oplus\)表示异或。 \[ \begin{align} & 0101 \ (= (5)_{10}) \\ \mathrm{XOR} \ & 0011 \ (= (3)_{10}) \\ = \ & 0110 \ (= (6)_{10}) \end{align} \]

异或运算可以将某一位反转。例如，我们要把\(0110 \ (= (6)_{10})\)的第\(1\)位和第\(3\)位反转，可以将其和\(0101\)（第\(1\)位和第\(3\)位是\(1\)）进行异或运算： \[ \begin{align} & 0110 \ (= (6)_{10}) \\ \mathrm{XOR} \ & 0101 \ (= (5)_{10}) \\ = \ & 0011 \ (= (3)_{10}) \end{align} \]

通过定义可以得到，一个数异或自己总是得\(0\)。因此，将一个变量归零可以使用异或自己的方式，这种方式的效率通常比直接赋值为\(0\)要高。

数学等价

对于非负整数\(x\)和\(y\)，\(x \ge y\)，位运算可以写成如下形式： \[ \begin{align} \mathrm{NOT} \ x &= \sum\limits_{n=0}^{\lfloor \log_{2} x \rfloor} 2^{n} ((\lfloor \dfrac{x}{2^{n}} \rfloor \bmod 2 + 1) \bmod 2) = 2^{\lfloor \log_{2} x \rfloor + 1} - 1 - x \\ x \ \mathrm{AND} \ y &= \sum\limits_{n=0}^{\lfloor \log_{2} x \rfloor} 2^{n} (\lfloor \dfrac{x}{2^{n}} \rfloor \bmod 2) (\lfloor \dfrac{y}{2^{n}} \rfloor \bmod 2) \\ x \ \mathrm{OR} \ y &= \sum\limits_{n=0}^{\lfloor \log_{2} x \rfloor} 2^{n} ((\lfloor \dfrac{x}{2^{n}} \rfloor \bmod 2) + (\lfloor \dfrac{y}{2^{n}} \rfloor \bmod 2) - (\lfloor \dfrac{x}{2^{n}} \rfloor \bmod 2) (\lfloor \dfrac{y}{2^{n}} \rfloor \bmod 2)) \\ x \ \mathrm{XOR} \ y &= \sum\limits_{n=0}^{\lfloor \log_{2} x \rfloor} 2^{n} (((\lfloor \dfrac{x}{2^{n}} \rfloor \bmod 2) + (\lfloor \dfrac{y}{2^{n}} \rfloor \bmod 2)) \bmod 2) = \sum\limits_{n=0}^{\lfloor \log_{2} x \rfloor} 2^{n} ((\lfloor \dfrac{x}{2^{n}} \rfloor + \lfloor \dfrac{y}{2^{n}} \rfloor) \bmod 2) \end{align} \]

移位

移位会将二进制数字整体向左或向右移动，任意一端移出的位会被丢弃。在左移中，\(0\)会从右侧移入；而在右移中，符号位会从左侧移入。左移\(n\)位等同于乘以\(2^{n}\)，而右移\(n\)位等同于除以\(2^{n}\)并向负无穷取整。
在大多数编程语言中，左移为<<，右移为>>。 \[ \begin{align} \mathrm{LEFT \ SHIFT} \ & 00010111 \ (= (23)_{10}) \\ = \ & 00101110 \ (= (46)_{10}) \end{align} \] \[ \begin{align} \mathrm{RIGHT \ SHIFT} \ & 10010111 \ (= (-105)_{10}) \\ = \ & 11001011 \ (= (-53)_{10}) \end{align} \]

应用

• 乘以\(2^{m}\)

  int mulTwoPower(int n, int m=1) {
      return n << m;
  }

• 除以\(2^{m}\)

  int divTwoPower(int n, int m=1) {
      return n >> m;
  }

• 判断奇偶性

  bool isOdd(int n) {
      return n & 1;
  }

• 取两个数的最大值

  int max(int a, int b) {
      // 若n为非负数，n >> 31的值为0，否则为-1
      return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
  }

• 取两个数的最小值

  int min(int a, int b) {
      // 若n为非负数，n >> 31的值为0，否则为-1
      return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31));
  }

• 取绝对值

  int iabs(int n) {
      // 若n为非负数，n >> 31的值为0，否则为-1
      return (n ^ (n >> 31)) - (n >> 31);
  }

• 判断是否是\(2\)的幂

  bool isTwoPower(int n) {
      return n > 0 && (n & (n - 1)) == 0;
  }

• 对\(2^{n}\)取余

  int bmodTwoPower(int n, int m) {
      return m & (n - 1);
  }

• 判断符号是否相同

  bool isSameSign(int a, int b) {
      return (a ^ b) >= 0;
  }

• 加法

  int add(int a, int b) {
      int sum = 0, carry = 0;
      do {
          sum = a ^ b;
          carry = (a & b) << 1;
          a = sum;
          b = carry;
      }
      while (carry);
      return sum;
  }