简介

目标：对于一个 \(n\) 位二进制表示的子集 x，我们希望枚举其子集。

朴素枚举其子集的代码，复杂度 \(O(2^{n})\)：

for (int s = 0; s <= x; s++)
    if (s | x == x)
        // s 表示的二进制是 x 的子集

快速枚举其子集的代码，复杂度 \(O(2^{|X|})\)，其中 \(X\) 是 x 表示的集合：

for (int s = x; s > 0; s = (s - 1) & x)
    // s 表示的二进制是 x 的子集
// 以上算法不！会！处！理！空！集！，额外处理！

正确性证明：

代码中的 & x 保证 s 一定是 s 的子集，而 (s - 1) 保证枚举出来的 s 递减至 0，详细证明不在此赘述脑补即可.

拓展

在很多的状压 DP 当中，我们不仅要枚举一个集合的子集，而是要枚举 \([0, 2^n)\) 的所有二进制数表示的集合的子集，如果使用朴素地暴力做法，那么复杂度显然是 \(O(4^n)\)，可以过 \(n \le 10\) 的数据。

那么如果我们使用刚刚介绍的优化方法，复杂度会变成多少呢？

分析：总体复杂度为： \[ \sum_{i = 0}^n \binom{n}{i}2^i = \sum_{i = 0}^n \binom{n}{i}2^i1^{n - i} \] 逆用二项式定理： \[ \sum_{i = 0}^n \binom{n}{i}2^n = (2 + 1)^n = 3^n \] 因此，算法的复杂度为 \(O(3^n)\)（而且是最优的），可以通过 \(n \le 15\) 的数据。