2019-08-05: 修改笔误，完善内容。

基操勿六皆坐

集合${0,1,\cdots,n-1}$的子集$S$可用如下方法编码成整数：

$$f(S)=\sum_{i\in S}2^i$$

一些集合的运算可以对应地写成如下方式。

• 空集$\varnothing$：0

• 只含有第$i$个元素的集合${i}$：1<<i

• ${0,1,\cdots,n-1}$：(1<<n)-1

• 判断第$i$个元素是否属于集合$S$：if(S>>i&1)

• 向集合中加入第$i$个元素$S\cup{i}$：S|1<<i

• 从集合中去除第$i$个元素$S\setminus {i}$：S&~(1<<i)

• 并集$S\cup T$：S|T

• 交集$S\cup T$：S&T

¹

lowbit

该技巧用于取一个二进制数的从右往左第一个非0位所表示的10进制数。

对于int类型来说，~x = -x-1

原理：对于一个正数的整型数据，计算机在存储对应的负数时，会将该正数按位取反后（反码）再加1（补码），例如：

x = 0100 -x = 1100 x&-x = 0100

显然对于任意一个正数x，除从右往左第一个非0位及其右面的位与-x对应位相同以外，其他位都相反，利用这个性质，可以快速取出一个二进制数的从右往左第一个非0位所表示的10进制数。

代码如下：

1

lowbit(x) = x & -x;

枚举$S$中的所有子集

1
2
3
4

for (int S_ = S; ~S; --S) {
    S_ &= S;
    subset(S_);
}

每次对当前生成的子集减1，也就是将S_最低位的1变成0，更低位的所有0变成1，如1100-1 = 1011，即每次将S_中元素序号最小的去掉，再将集合S中比前述去掉的元素的序号更小的所有元素加入S_，直到S_=0再减1，退出循环。

还有这种操作？

枚举${0,1,\cdots,n-1}$中所有大小为$k$的子集

1
2
3
4
5

int comb = (1 << k) - 1;
while (comb < 1 << n) {
    int x = comb & -comb,y = comb + x;
    comb = ((comb &~ y) / x >> 1) | y;
}

按照字典序的话，最小的子集是(1<<k)-1，所以用它作为初始值。现在我们求出comb其后的二进制码。例如0101110之后的是0110011，0111110之后的是1001111。下面是求出comb下一个二进制码的方法。

1. 求出最低位的1开始的连续的1的区间(0101110->0001110)

2. 将这一区间全部变为0, 并将区间左侧的那个0变为1(0101110-0110000)

3. 将第1步里取出的区间右移，直到剩下的1的个数减少了1个(0001110->0000011)

4. 将第2步和第3步的结果按位取或(0110000|0000011=0110011)

用lowbit将最低位的1取出后，设它为x。那么通过计算y=comb+x,就将comb从最低位的1开始的连续的1都置0了。我们来比较一下~y和comb。在comb中加上x后没有变化的位，在~y中全都取相反的值。而最低位1开始的连续区间在~y中依然是1，区间左侧的那个0在~y中也依然是0。于是通过计算z=comb&~y就得到了最低位1开始的连续区间。比如如果comb=0101110则x=0000010，y=0110000，z=0001110。

同时，y也恰好是第2步要求的值。那么首先将z不断右移，直到最低位为1，这通过计算z/x即可完成。这样再将z/x右移一位就得到了第3步要求的值。这样我们就求出了comb之后的下一个二进制列。因为是从n个元素中进行选择，所以comb的值不能大于1<<n。如此一来，就完成了大小为k的所有子集的枚举。

¹

枚举${0,1,\cdots,n-1}$中所有不包含相邻元素的集合

不包含相邻元素的集合，简单理解即为表示集合的二进制数中不包含相邻的1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int i = 0;
while (i < 1 << k) {
    int comb = i &~ (i + (Lowbit(i)));
    if ((comb & Lowbit(comb)) == comb) {
        printf("%d\n", i);
        ++cnt;
        ++i;
    }
    else {
        i += Lowbit(i);
    }
}
printf("\n%d\n", cnt);

注：该结果的计数为$f(n)=F_{n+2}$，其中${F_{n}}(F_1=1,F_2=1)$为斐波那契数列。²

证明如下：

当$n=0$时，显然$f(0)=1$，

当$n=1$时，即枚举${0}$中所有不包含相邻元素的集合，即$f(1)=2$，

对于$n>1$，当最低位为0时，只需次低位及其左边的二进制位不包含相邻元素，方案数为$f(n-1)$；当最低位为1时，次低位必须为0,其左边的二进制位不包含相邻元素，方案数为$f(n-2)$。故总方案数为$f(n)=f(n-1)+f(n-2)$。

参考该结论，可以在线性时间内算出任意集合$S$的不包含相邻元素的子集的计数问题。

妙啊！妙啊！妙啊！

计算$S$中有多少元素

1
2
3
4

card[0] = 0;
for (int S = 1; S < bound; ++i){
    card[S] = card[S & (S - 1)] + 1;
}

集合$S$中的最小元素编号

1
2
3
4
5
6

for (int i = 0; i < n; ++S){
    ttt[1 << i] = i;
}
for (int S = 1; S < bound; ++S){
    ttt[S] = ttt[S & -S];
}