二进制状态压缩

缘起

状态压缩是算法中常用的手段. 经常会联合dp、搜索中使用. 就拿搜索来讲，使用dfs毫无疑问，无论从空间复杂度还是性能上都不如直接枚举二进制数来得快（代价是不易读）.

所以有必要单独写篇文章来论述.

分析

基本认识

集合中的子集枚举经常和状态压缩联系在一起——对于集合元素较少时，使用一个二进制数来表示选择了这个集合中的哪些元素是极为方便的.

例如

1
2
3
4
5
6
7
8
9
下面讨论的集合是 S={0,...,n-1}
1. 空集用0表示
2. 单点集合{i} 用 1<<i 表示
3. 全集用 (1<<n)-1 表示
4. 判断i是否属于T（S的某个子集） if(T>>i&1)  想想i=0就知道了
5. 向集合T加入i（即T并上{i}） T|1<<i
6. 从集合T中去除掉i,  T&~（1<<i）
7. 集合T和集合T' 的并集 T|T'
8. 集合T和集合T' 的交集 T&T'

全集的子集枚举

有了上述基本认识，要想将S={0,…,n-1} 的全部子集枚举出来的话，可以像下面这样写代码

1
2
3
4
for(int i = 0; i<(1<<n); i++)
{
	// 这里插入对子集进行处理(每个i都代表一个S的子集)代码...
}

这种枚举将从空集开始，按照{0},{1},{0,1},…{0,1,…,n-1}这样的升序枚举出S的全部子集.

某个集合的子集的枚举

上面介绍的是S={0,..,n-1}这个集合的子集枚举. 下面介绍S的子集T的所有子集的枚举. 这个时候, i是T的子集，i+1就未必是T的子集了. 废话不多说，直接上代码

1
2
3
4
5
6
int s = T;
do
{
    // 这里插入对s（T的子集）的处理代码...
    s = (s-1)&T;
}while(s!=T)

首先，只需要减一就行了. 因为T的子集不可能大于T

之所以要s!=T, 是因为0（空集）肯定是T的子集，而-1&T=T. 为什么上面的代码就能遍历T的所有子集呢? 你想想T的最末位的那个1（lowbit）就知道了. s-1其实就在破坏这一lowbit（类似于 xxxx1000000-1=xxxx0111111） 则与T做&运算之后，得到的就是 s=xxxx0000000这样. 即lowbit就干掉了. s再减一的话, 则就变成 xxxx1111111这种… 与T做&运算的话，…自己想想就知道了

枚举k个元素的子集

枚举S={0,…,n-1}的所有大小为k的子集的方法. 

1
2
3
4
5
6
7
int comb = (1<<k)-1;
while(comb<1<<n)
{
    // 这里插入k子集的处理代码...
    int lowbit = comb & (-comb), y = x+comb;
    comb = ( (comb & ~y)/x >> 1) | y
}

以 comb = 0101110 为例. 其实它的下一个k子集的求法就是两部分的 | 运算结果. 第一部分是comb的lowbit+1的结果，即

0101110+0000010（这是comb的lowbit）=0110000

第二部分就是从lowbit开始往高位进动的连续的1片段，即 0001110， 这个连续的1的片段不断的向右移动直至少掉了一个1. 即0000011.

然后这两部分做&运算，得到了0110011. 这就是comb=0101110 的下一个k子集.

而对应到代码. 学过树状数组的都知道lowbit的求法，就不多说什么了. y=x+comb就是第一部分. 而comb&~y得到的就是从lowbit往高位进动的连续的1片段. 它除以x得到的（注意, 除法的优先级高于>>运算）就是将这个连续的1片段移动到最低位，然后结果再>>1就是少掉一个1, 然后最后与y（即第一部分）做|运算. 即

( (comb & ~y)/x >> 1) 求出的就是第二部分. 而 y是第一部分.

为什么结束条件是 comb<1<<n呢? 因为你想啊，如果处理到了最高位k个1的话，则再按照上面两部分做|运算的话，则结果一定>1<<n.