简介

位运算（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}$

1
2
3

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

除以$2^{m}$

1
2
3

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

判断奇偶性

1
2
3

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$的幂

1
2
3

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

对$2^{n}$取余

1
2
3

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

判断符号是否相同

1
2
3

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;
}