我想知道这个位操作意味着什么:
for (int m = 1; m < (1 << n); ++m) {
for (int s = m; s; s = (s - 1) & m) {
// ....
}
}
第一个 for 循环是枚举 n 个元素的所有子集,但是第二个 for 循环意味着什么?
最佳答案
如果s
格式为...10000
然后s-1
是 ...01111
。然后我们&
与 m
,只剩下那些 1
在下部,也出现在 m
中。 ( s
的高位保持不变,并与 m
中的相同)。
实际上,我们清除了 s
中设置最少的位。并将所有低位替换为 m
中的位。可以看出,这相当于“在m
的设定位内向下计数”。也就是说,如果m
有k
设置位,从 (1<<k)-1
开始倒数并且,对于这 2k 个数字中的每一个,分配其 k
位进入 k
职位 m
已设置位。
或者,如果我们解释 m
作为一个位集,它枚举 m
的所有子集(包括 m
但跳过空子集)。
关于c++ - 子集相关的位操作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58306315/