c++ - 子集相关的位操作

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设置位，从 (1<<k)-1 开始倒数并且，对于这 2^k 个数字中的每一个，分配其 k位进入 k职位 m已设置位。

或者，如果我们解释 m作为一个位集，它枚举 m 的所有子集(包括 m 但跳过空子集)。