二进制与位运算

AisDaeun 42 2023-11-15

枚举子集

给定一个集合x,x中有n个元素,要求枚举x的所有子集。

考虑把每个元素是否在子集中出现视为一个bit,则整个集合可以用n个bit表示,这n个bit称作状态集合。

for (int i = 0; i < (1 << n); i++) {
    //do something
}

给定一个状态集合,要求枚举该集合的所有子集。

for (int i = S; i; i = (i - 1) & S) {
    //do something
}

枚举n个数中选k个数的集合

当然可以像刚刚一样枚举所有的子集,不过未免效率太低。

下面介绍一种方法,可以高效地求出所有集合。

int p = (1 << k) - 1;
while (p < (1 << n) {
    int x = p & -p;
    int y = p + x;
    int z = p & ~y;
    p = (z / x >> 1) | y;
}

如何理解这种方法?下面以k = 3,n = 8的情况举例。

下面这段代码以暴力方法生成了所有结果。

for (int i = 0; i < (1 << 8); i++)
    if (__builtin_popcount(i) == 3)
        cout << bitset<8>(i) << '\n';

下面这段代码生成了所有结果和中间变量。

int k = 3, n = 8;
int p = (1 << k) - 1;
while (p < (1 << n) - 1) {
    cout << bitset<8>(p) << '\n';
    int x = p & -p;
    int y = p + x;
    int z = p & ~y;
    cout << bitset<8>(x) << ' ' << bitset<8>(y) << ' ' << bitset<8>(z) << '\n';
    p = (z / x >> 1) | y;
}

截取一些输出,仔细观察:

00010011
00000001 00010100 00000011
00010101
00000001 00010110 00000001
00010110
00000010 00011000 00000110
00011001
00000001 00011010 00000001
00011010
00000010 00011100 00000010
00011100
00000100 00100000 00011100
00100011
00000001 00100100 00000011
00100101
00000001 00100110 00000001
0010011
00000010 00101000 00000110
00101001
00000001 00101010 00000001

我们发现,z是p截取末尾连续1段的结果,y是将p末尾连续1段置0,再将连续1段左侧第一个0置1的结果;而p的下一个子集是由左侧进位和右侧原有部分共同构成的。

时间复杂度上有极大的改进:O(2^n) -> O(C_{n}^{k})