目录位运算与、或、异或取反左移和右移复合赋值位运算符关于优先级位运算的应用有关 2 的幂的应用取绝对值取两个数的最大/最小值判断两非零数符号是否相同交换两个数操作一个数的二进制位汉明权重位移实现LSB 置零操作x & -x 实现n & (n - 1) 实现构造汉明权重递增的排列集合集合集合与元素常见的集合操作Lowbit集合遍历
位运算
位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。
基本的位运算共 6 种，分别为：按位与、按位或、按位异或、按位取反、左移和右移。
与、或、异或
这三者都是两数间的运算，因此在这里一起讲解。
它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。
运算
运算符
数学符号表示
解释
与
\(\&\)
\(\&\)、\(\operatorname{and}\)
只有两个对应位都为 1 时才为 1
或
|
\(\mid\)、\(\operatorname{or}\)
只要两个对应位中有一个 1 时就为 1
异或
^
\(\oplus\)、\(\operatorname{xor}\)
只有两个对应位不同时才为 1
注意，逻辑与（对应的数学符号为 \(\wedge\)）和按位与、逻辑或（\(\vee\)）和按位或的区别。
异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 \(a \oplus b \oplus b = a\) 。
举例：
\[\begin{aligned}
5 &=(101)_2\\
6 &=(110)_2\\
5\operatorname\&6 &=(100)_2 =\ 4\\
5\operatorname|6 &=(111)_2 =\ 7\\
5\oplus6 &=(011)_2 =\ 3\\
\end{aligned}
\]
取反
取反是对一个数 \(num\) 进行的位运算，即单目运算。
取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把 \(num\) 的二进制补码中的 \(0\) 和 \(1\) 全部取反（\(0\) 变为 \(1\)，\(1\) 变为 \(0\)）。有符号整数的符号位在 ~ 运算中同样会取反。
补码：在二进制表示下，正数和 \(0\) 的补码为其本身，负数的补码是将其对应正数按位取反后加一。
举例（有符号整数）：
\[\begin{aligned}
5&=(00000101)_2\\
\text{~}5&=(11111010)_2=-6\\
-5\text{的补码}&=(11111011)_2\\
\text{~}(-5)&=(00000100)_2=4
\end{aligned}
\]
左移和右移
num << i 表示将 \(num\) 的二进制表示向左移动 \(i\) 位所得的值。
num >> i 表示将 \(num\) 的二进制表示向右移动 \(i\) 位所得的值。
举例：
\[\begin{aligned}
11&=(00001011)_2\\
11<<3&=(01011000)_2=88\\
11>>2&=(00000010)_2=2
\end{aligned}
\]
移位运算中如果出现如下情况，则其行为未定义：
右操作数（即移位数）为负值；
右操作数大于等于左操作数的位数。
例如，对于 \(int\) 类型的变量 \(a\)、\(a<<-1\) 和 \(a<<32\) 都是未定义的。
对于左移操作，需要确保移位后的结果能被原数的类型容纳，否则行为也是未定义的。对一个负数执行左移操作也未定义。
对于右移操作，右侧多余的位将会被舍弃，而左侧较为复杂：
对于无符号数，会在左侧补 \(0\)；
对于有符号数，则会用最高位的数（其实就是符号位，非负数为 \(0\)，负数为 \(1\)）补齐。
复合赋值位运算符
与 +=、-= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , <<= , >>= 。
取反是单目运算，所以没有复合赋值运算符。
关于优先级
位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。
位运算的应用
位运算一般有三种作用：
高效地进行某些运算，代替其它低效的方式；
表示集合（常用于 状态压缩 DP）；
题目本来就要求进行位运算。
需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。
但像「乘 2 的非负整数次幂」和「除以 2 的非负整数次幂」就最好使用位运算，因为此时使用位运算可以优化复杂度。
有关 2 的幂的应用
由于位运算针对的是变量的二进制位，因此可以推广出许多与 2 的整数次幂有关的应用。
例如，将一个数乘（除） 2 的非负整数次幂：
计算 \(n * 2^m\) 的代码实现：
int mulPowerOfTwo(int n, int m) { // 计算 n*(2^m)
return n << m;
}
计算 \(n / 2^m\) 的代码实现：
int divPowerOfTwo(int n, int m) { // 计算 n/(2^m)
return n >> m;
}
注意，我们平常写的除法是向 0 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为 0 ，而 -1 >> 1 的值为 -1 。
取绝对值
对整数 n 取绝对值的代码实现：
int abs(int n) {
return (n ^ (n >> 31)) - (n >> 31);
}
首先，n >> 31 可以取得 n 的符号：
若 n 为正数，n >> 31 等于 0，此时，上述表达式等价于 n ^ 0 - 0 = n；
即正数的绝对值还是它本身；
若 n 为负数，n >> 31 等于 -1，此时，上述表达式等价于 n ^ (-1) - (-1) = n。
其中，n ^ (-1) 需要计算 n 和 -1 的补码，然后进行异或运算，结果就是 n 变号并且为 n 的绝对值减 1，再减去 -1，就是其绝对值。
这种算法，在某些机器上，效率比 n > 0 ? n : -n 高。
取两个数的最大/最小值
在某些机器上，效率比 a > b ? a : b 高。
// 如果 a >= b, (a - b) >> 31 为 0，否则为 -1
int max(int a, int b) {
return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}
int min(int a, int b) {
return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31));
}
判断两非零数符号是否相同
bool isSameSign(int x, int y) { // 有 0 的情况例外
return (x ^ y) >= 0;
}
交换两个数
该方法具有局限性：这种方式只能用来交换两个整数，使用范围有限。
对于一般情况下的交换操作，推荐直接调用 algorithm 库中的 std::swap 函数。
void swap(int &a, int &b) {
a ^= b ^= a ^= b;
}
操作一个数的二进制位
获取一个数二进制的某一位：
// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) {
return (a >> b) & 1;
}
将一个数二进制的某一位设置为 0：
// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) {
return a & ~(1 << b);
}
将一个数二进制的某一位设置为 1：
// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) {
return a | (1 << b);
}
将一个数二进制的某一位取反：
// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) {
return a ^ (1 << b);
}
这些操作相当于将一个 32 位整型变量当作一个长度为 32 的布尔数组。
汉明权重
汉明权重 是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是 1 的个数。
对于一个二进制数，它的汉明权重就等于它 1 的个数（即 popcount）。
位移实现
求一个数的汉明权重可以循环求解：我们不断地去掉这个数在二进制下的最后一位（即右移 1 位），维护一个答案变量，在除的过程中根据最低位是否为 1 更新答案。
代码如下：
// 求 x 的汉明权重
int popcount(int x) {
int cnt = 0;
while (x) {
cnt += x & 1;
x >>= 1;
}
return cnt;
}
LSB 置零操作
x & -x 实现
求一个数的汉明权重还可以使用 lowbit 操作：我们将这个数不断地减去它的 lowbit，直到这个数变为 0。
代码如下：
// 求 x 的汉明权重
int popcount(int x) {
int cnt = 0;
while (x) {
cnt++;
x -= x & -x;
}
return cnt;
}
n & (n - 1) 实现
减 1 操作将 n 最右边的符号从 0 变到 1，从 1 变到 0，与操作将会移除最右端的 1。如果最初 n 有 X 个 1，那么经过 X 次这样的迭代运算，n 将变为 0。
int popcount(int n) {
int cnt = 0;
for(; n != 0; n = n & (n - 1)) {
cnt++;
}
return cnt;
}
n & (n-1) 实现在大多数比特为 0 的情况下是效率最高的。
注意，上面的 x -= x & -x 操作与 n = n & (n - 1) 操作是等价的，都是将最低有效位（Least Significant Bit，LSB）置为零。
构造汉明权重递增的排列
在状态压缩 DP 中，按照 popcount 递增的顺序枚举有时可以避免重复枚举状态。这是构造汉明权重递增的排列的一大作用。下面我们来具体探究如何在 \(O(n)\) 时间内构造汉明权重递增的排列。
我们知道，一个汉明权重为 n 的最小的整数为 \(2^n-1\)。只要可以在常数时间构造出一个整数汉明权重相等的后继，我们就可以通过枚举汉明权重，从 \(2^n-1\) 开始不断寻找下一个数的方式，在 \(O(n)\) 时间内构造出 \(0\sim n\) 的符合要求的排列。
而找出一个数 \(x\) 汉明权重相等的后继有这样的思路，以 \((10110)_2\) 为例：
把 \((10110)_2\) 最右边的 1 向左移动一位，如果不能移动，将它左边的 1 向左移动，以此类推，得到 \((11010)_2\)。
把得到的 \((11010)_2\) 最后移动的 1 原先的位置一直到最低位的所有 1 都移到最右边。这里最后移动的 1 原来在第三位，所以最后三位 010 要变成 001，得到 \((11001)_2\)。
这个过程可以用位运算优化：
int t = x + (x & -x);
x = t | ((((t &-t)/(x & -x)) >> 1) - 1);
第一个步骤，我们把数 x 加上它的 lowbit，在二进制表示下，就相当于把 x 最右边的连续一段 1 换成它左边的一个 1。
例如，当 \(x =(10110)_2\) 时，\(-x = (01010)_2\)， 因此，\((x\ \& -x) = (10)_2\)，所以 \(t = x + (x\ \& -x) = (11000)_2\)。
第二个步骤，我们把答案后面的 1 补齐，\(t\) 的 lowbit 是 x 最右边连续一段 1 最左边的 1 移动后的位置，而 \(x\) 的 lowbit 则是 \(x\) 最右边连续一段 1 最左边的位置。
此时，\(t = (11000)_2\)，\(\operatorname{lowbit}(t) = (01000)_2\)，\(\operatorname{lowbit}(x)=(00010)_2\)。
接下来的除法操作是这种位运算中最难理解的部分，但也是最关键的部分。我们设原数最右边连续一段 1 最高位的 1 在第 \(r\) 位上（位数从 0 开始），最低位的 1 在第 l 位，\(t\) 的 lowbit 等于 \(1 << (r+1)\) ，x 的 lowbit 等于 \(1 << l\)， \((((t\&-t)/(x\&-x))>>1)\) 得到的，就是 \((1<<(r+1))/(1< 以前面的例子为例， \[\frac{\operatorname{lowbit(t)/2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2 \] 把这个数减去 1 得到的就是我们要补全的低位，或上原来的数就可以得到答案。所以枚举 \(0\sim n\) 按汉明权重递增的排列的完整代码为： for (int i = 0; (1< for (int x = (1< // 写下需要完成的操作 } } 其中要注意 0 的特判，因为 0 没有相同汉明权重的后继。 集合 集合 常见的集合术语如下： 集合术语 数学符号 运算符 举例 结果 交集 \(A \cap B\) \(a\ \&\ b\) \(\{0,2,3\} \cap \{0,1,2\} = \{0,2\}\) \((1101)_2\ \&\ (0111)_2 = (0101)_2\) 并集 \(A \cup B\) \(a\ \text{|}\ b\) \(\{0,2,3\} \cup \{0,1,2\} = \{0,1,2,3\}\) \((1101)_2\ \text{|}\ (0111)_2 = (1111)_2\) 对称差 \(A \underline{\vee} B\) \(a \oplus b\) \(\{0,2,3\} \underline{\vee} \{0,1,2\} = \{1,3\}\) \((1101)_2\ \oplus\ (0111)_2 = (1010)_2\) 差 \(A \setminus B\) \(a\ \&\ (\text{~}b)\) \(\{0,2,3\} \setminus \{1,2\} = \{0,3\}\) \((1101)_2\ \&\ (1001)_2 = (1001)_2\) 差（子集） \(A \setminus B (B \subseteq A)\) \(a \oplus b\) \(\{0,2,3\} \underline{\vee} \{0,2\} = \{3\}\) \((1101)_2\ \oplus\ (0101)_2 = (1000)_2\) 包含于 \(A \subseteq B\) \(a\ \&\ b = a\) \(a\ |\ b = b\) \(\{0,2\} \subseteq \{0,2,3\}\) \((0101)_2\ \&\ (1101)_2 = (0101)_2\) \((0101)_2\ |\ (1101)_2 = (1101)_2\) 集合与元素 常见的集合与元素的操作如下： 集合术语 数学符号 运算符 举例 结果 空集 \(\emptyset\) \(0\) 单元素集合 \({i}\) \(1 << i\) \(\{2\}\) \(1 << 2\) 全集 \(U = {0,1,2, \cdots, n - 1}\) \((1< \(\{1,2,3\}\) \((1<<4) - 1\) 补集 \(\complement_US = U \setminus S\) \(\text{~}s\) \(((1< 属于 \(i \in S\) \((s>>i)\ \&\ 1 = 1\) \(2 \in \{0,2,3\}\) \(((1101)_2 >> 2)\ \&\ 1 = 1\) 不属于 \(i \notin S\) \((s>>i)\ \&\ 1 = 0\) \(1 \in \{0,2,3\}\) \(((1101)_2 >> 1)\ \&\ 1 = 0\) 添加元素 \(S \cup {i}\) \(s\ |\ (1 << i)\) \(\{0,3\} \cup \{2\} = \{0,2,3\}\) \((1001)_2\ |\ (1<<2) = (1101)_2\) 删除元素 \(S \setminus {i}\) \(s\ \&\ (~(1<< i))\) \(\{0,2,3\} \setminus \{2\} = \{0,3\}\) \((1101)_2\ \&\ \text{~}(1<<2) = (1001)_2\) 删除元素 \(S \cup {i} (i \in S)\) \(s \oplus (1 << i)\) \(\{0,2,3\} \setminus \{2\} = \{0,3\}\) \((1101)_2\ \oplus\ \text{~}(1<<2) = (1001)_2\) 删除最小元素 \(s\ \&\ (s - 1)\) \((101100)_2\ \&\ (101011)_2 = (101000)_2\) 常见的集合操作 Lowbit s & (-s) 例如，s = 101100，那么 ~s = 010011 -s = (~s)+1 = 010100 因此，s & -s = 000100 集合遍历 for i in range(n): if (s >> i) & 1: # i 在 s 中 # 处理 i 的逻辑 从大到小枚举 s 的所有非空子集 sub sub = s while sub: # 处理 sub 的逻辑 sub = (sub - 1) & s 如果要从大到小枚举 s 的所有子集 sub（从 s 枚举到空集 ∅），可以这样写： sub = s while True: # 处理 sub 的逻辑 sub = (sub - 1) & s if sub == s: break 参考： 位运算 分享｜从集合论到位运算，常见位运算技巧分类总结！