状压DP

二进制 与 位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 \(6\) 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。为了方便叙述，下文中省略“按位”。

关于优先级

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符（详见 运算页面 ），所以使用时需多加注意，在必要时添加括号。

位运算的应用

位运算一般有三种作用：

1. 高效地进行某些运算，代替其它低效的方式。
2. 表示集合。（常用于 状压DP）
3. 题目本来就要求进行位运算。

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”就最好使用位运算，因为此时使用位运算可以优化复杂度。）

2 的幂的应用

由于位运算针对的是变量的二进制位，因此可以推广出许多与 2 的整数次幂有关的应用。

将一个数乘（除） 2 的非负整数次幂：

int mulPowerOfTwo(int n, int m) { return n << m; } // 计算 n*(2^m)
int divPowerOfTwo(int n, int m) { return n >> m; } // 计算 n/(2^m)

注意

我们平常写的除法是向 \(0\) 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 \(0\) 时两种方法等价，当数小于\(0\) 时会有区别，如： -1 / 2 的值为 \(0\) ，而 -1 >> 1 的值为 \(-1\) 。

判断一个数是不是 \(2\) 的非负整数次幂：

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

对 \(2\) 的非负整数次幂取模：

int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }

交换两数

这种方式只能用来交换两个整数，使用范围有限。

对于一般情况下的交换操作，推荐直接调用 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\) 的布尔数组。

在此基础上，可以手写实现 bitset。

模拟集合操作

一个数的二进制表示可以看作是一个集合（ \(0\) 表示不在集合中，\(1\) 表示在集合中）。比如集合 \(\{1,3,4,8\}\) ，可以表示成 \((100011010)_2\) 。而对应的位运算也就可以看作是对集合进行的操作。

操作	集合表示	位运算语句
交集	\(a \cap b\)	a & b
并集	\(a \cup b\)	a | b
补集	\(\bar{a}\)	~ a（全集为二进制都是 1）
差集	\(a \setminus b\)	a & (~ b)
对称集	\(a\triangle b\)	a ^ b

子集遍历：

// 遍历 u 的非空子集
for (int s = u; s; s = (s - 1) & u) {
  // s 是 u 的一个非空子集
}

用这种方法可以在 \(\mathcal{O}(2^{\operatorname{popcount}(u)})\) （ \(\operatorname{popcount}(u)\) 表示 \(u\) 二进制中 \(1\) 的个数）的时间复杂度内遍历 \(u\) 的子集，进而可以在 \(\mathcal{O}(3^n)\) 的时间复杂度内遍历大小为 \(n\) 的集合的每个子集的子集。（复杂度为 \(\mathcal{O}(3^n)\) 是因为每个元素都有 不在大子集中/只在大子集中/同时在大小子集中 三种状态。）

内建函数

GCC 中还有一些用于位运算的内建函数：

1. int __builtin_ffs(int x) ：返回 \(x\) 的二进制末尾最后一个 \(1\) 的位置，位置的编号从 \(1\) 开始（最低位编号为 \(1\) ）。当 \(x\) 为 \(0\) 时返回 \(0\) 。
2. int __builtin_clz(unsigned int x) ：返回 \(x\) 的二进制的前导 \(0\) 的个数。当 \(x\) 为 \(0\) 时，结果未定义。
3. int __builtin_ctz(unsigned int x) ：返回 \(x\) 的二进制末尾连续 \(0\) 的个数。当 \(x\) 为 \(0\) 时，结果未定义。
4. int __builtin_clrsb(int x) ：当 \(x\) 的符号位为 \(0\) 时返回 \(x\) 的二进制的前导 \(0\) 的个数减一，否则返回 \(x\) 的二进制的前导 \(1\) 的个数减一。
5. int __builtin_popcount(unsigned int x) ：返回 \(x\) 的二进制中 \(1\) 的个数。
6. int __builtin_parity(unsigned int x) ：判断 \(x\) 的二进制中 \(1\) 的个数的奇偶性。

这些函数都可以在函数名末尾添加 l 或 ll （如 __builtin_popcountll ）来使参数类型变为 ( unsigned ) long 或 ( unsigned ) long long （返回值仍然是 int 类型）。 例如，我们有时候希望求出一个数以二为底的对数，如果不考虑 0 的特殊情况，就相当于这个数二进制的位数 -1 ，而一个数 n 的二进制表示的位数可以使用 32-__builtin_clz(n) 表示，因此 31-__builtin_clz(n) 就可以求出 n 以二为底的对数。

由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。

状压DP

状态压缩动态规划，简称状压DP。

状态压缩

当状态维数 \(n\) 很多但每一维状态数 \(k\) 都很少（一般是 \(2\) ）的时候，我们可以用一个 \(n\) 位 \(k\) 进制整数来表示这 \(n\) 维状态。

从 \(\mathcal{O}(n!)\) 到 \(\mathcal O(2^n)\)

状压DP是最接近暴力的一种DP，因为它可以完整地记录每一种状态。

但它又比 \(\mathcal O(n!)\) 的纯暴力搜索要优一些，因为它舍弃了状态的更新顺序的记录。

所以很多情况下，状压DP就是将 \(\mathcal O(n!)\) 的暴力优化到 \(\mathcal O(2^n)\) 的另一个暴力的过程。

子集枚举

上面算法的瓶颈在于枚举 \(S\) 的子集 \(T\) 仍然需要 \(\mathcal O(2^n)\) 的复杂度，但其实多数情况下 \(S\) 的子集数是远远小于 \(2^n\) 的。

我们只需把

for(int T = 1; T <= S; ++T) if((S & T) == T)

改为

for(int T = S; T; T = (T - 1) & S)

即可使得 \(T\) 仅枚举到 \(S\) 的所有非空子集。

因为 \(S\) 取遍所有子集，所以枚举的 \(T\) 共有 \(\sum_{i=0}^n\dbinom{n}{i}2^i=3^n\) 个。

合理运用小范围数据

状压DP中 \(2^n\) 的复杂度使得题目中的某些数据范围也会很小（一般在 \(25\) 以下）。当遇到 \(25\) 以下的数据范围时一定要敏感。