位运算(偏向状态压缩)的骚操作

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

基操勿六皆坐

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

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

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

  • 空集\varnothing0

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

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

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

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

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

  • 并集STS\cup TS|T

  • 交集STS\cup TS&T

[1]

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;

枚举SS中的所有子集

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,,n1}\{0,1,\cdots,n-1\}中所有大小为kk的子集

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了。我们来比较一下~ycomb。在comb中加上x后没有变化的位,在~y中全都取相反的值。而最低位1开始的连续区间在~y中依然是1,区间左侧的那个0在~y中也依然是0。于是通过计算z=comb&~y就得到了最低位1开始的连续区间。比如如果comb=0101110x=0000010y=0110000z=0001110

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

[1:1]

枚举{0,1,,n1}\{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)=Fn+2f(n)=F_{n+2},其中{Fn}(F1=1,F2=1)\{F_{n}\}(F_1=1,F_2=1)为斐波那契数列。[2]

证明如下:

n=0n=0时,显然f(0)=1f(0)=1

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

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

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

妙啊!妙啊!妙啊!

计算SS中有多少元素

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

集合SS中的最小元素编号

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];
}

  1. 挑战程序设计竞赛(第2版). 秋叶拓哉等. ↩︎ ↩︎

  2. Fibonacci number. Wikipedia. https://en.wikipedia.org/wiki/Fibonacci_number ↩︎