子集相关的位操作

Question

我想知道这个位操作意味着什么：

for (int m = 1; m < (1 << n); ++m) {
    for (int s = m; s; s = (s - 1) & m) {
        // ....
    }
}

第一个for循环是枚举n个元素的所有子集，但是第二个for循环意味着什么？

Answer 1

如果s是 的形式...10000，则s-1是...01111。然后我们&，m只留下那些1也出现在下部的部分m。（ 的高位s保持不变，并与 中的相同m）。

实际上，我们清除了 中设置最少的位s，并将所有较低位替换为 中的那些m。可以看出，这相当于“在设定的位内向下计数m”。也就是说，如果m已k设置位，则从 开始倒数，对于这 2 ^{k 个}数字中(1<<k)-1的每一个，将其位分配到已设置位的位置。^kkm

或者，如果我们解释m为位集，它会枚举 的所有子集m（包括m但跳过空子集）。