二进制枚举

二进制枚举

1.枚举所有集合

假设有三个元素的集合z：{0, 1, 2}，那么每种元素可以选或者不选，只有三个元素，有2^3个子集

{0，1，10，11，100，101，110，111}，刚好小于1 << |z|的数有2^3个，从小开始枚举，然后取二进制位即可表示某个元素的状态

for(int i = 0;i < (1 << n);i++) {
    // 枚举二进制位，即能得到某个元素的取舍状态
}

2.从大到小枚举某个集合s的非空子集

假设对于集合10101，若想要枚举全部非空集合，暴力做法是：不断减1，得到的所有子集中包含了s的子集，其中会有集合不是s的子集

那么，如何跳过这些非s的子集的集合。

集合s(10101)的子集从大到小演变过程：

• 10101 -> 10100 -> 10001 -> 10000 -> ...

普通二进制从大到小的演变过程：

• 111 -> 110 -> 101 -> 100 ->...

观察最低位的1，在普通二进制中，最低位的1变为0，最低位1的更低位的0全部变为1

考虑集合s，并不需要后续的0都变为1，只需要存在于集合s中的元素变为1即可，小于s的最大下一个子集的计算方法即为：

• s = s & (s - 1)

for(int sub = s;sub > 0;sub = sub & (sub - 1)) {
    // 枚举二进制位，即能得到s的子集
}

3.从大到小枚举某个集合s的子集(包括空集)

do{
    // 枚举二进制位，即能得到s的子集
    sub = sub & (sub - 1);
} while(sub != s)

解释：当sub = 0，sub & (sub - 1) = s，因为sub - 1为-1，-1的补码为32个1，所以最终sub == s的时候，即代表枚举完子集(包括空集)了。

4.枚举超集

暂未涉略，原文