一种子集枚举方式的正确性说明

标签：cdots 正确性 枚举 1b 子集 2b mathrm

一种常见的枚举子集的方法是

for(int S = SET; S; S = (S-1) & SET)

其中，变量 \(\rm {S}\) 是所枚举的子集

考虑 \(\rm {S}\) 的二进制展开

\[\mathrm {S}=(b_1b_2b_3\cdots b_k)_2 \]

假设其二进制展开下的最低位的 \(1\) 在第 \(p\) 位

\[\mathrm {S}=(b_1b_2b_3\cdots b_p\cdots b_k)_2 \]

归纳一下，假设该枚举方式可以枚举到 \(b_1b_2b_3\cdots b_p\) 不变时的所有子集，也就是，枚举了只有 \(b_{p+1} b_{p+2}\cdots b_k\) 不同的所有子集

那么令 \(\mathrm {S}\leftarrow \mathrm{S} - 1\)

也就是把 \(\mathrm {S}\) 的第 \(b_p\) 位变为 \(0\)，\(b_{p+1}b_{p+2}\cdots b_k\) 中所有数变为 \(1\)

这个时候再令 \(\mathrm {S}\leftarrow \mathrm{S}\operatorname {and} \mathrm{SET}\)

就把 \(b_{p+1} b_{p+2}\cdots b_k\) 变成初始集合中的状态

继续该过程，可以枚举 \(b_1b_2b_3\cdots b_{p-1}\) 不变且 \(b_p=0\) 时 \(b_{p+1}b_{p+2}\cdots b_k\) 的所有情况

合起来就是枚举了只有 \(b_pb_{p+1}b_{p+1}\cdots b_k\) 中存在变化的所有子集

初始状态时，考虑最低位的 \(1\) 可以发现该做法显然正确，这可以说明该做法是正确的

标签：cdots,正确性,枚举,1b,子集,2b,mathrm
From： https://www.cnblogs.com/lostintianyi/p/17217839.html