Skip to content

状态压缩

2021-02-23

用一个二进制数代替一个 bool 数组。

简介

由于 bool 变量只有 01 两种值,二进制位也具备此特征,故每个 bool 数组都可用一个二进制数表示。

bool 数组 a(长为 n)用 n 位二进制数表示,它的第 i 位表示 a[i]

状态压缩的相关操作方法:

操作运算
取出第 k 位数(n >> (k - 1)) & 1
将第 k 位取反n ^= (1 << (k - 1))
将第 k 位赋值为 1n |= (1 << (k - 1))
将第 k 位赋值为 0n &= ~ (1 << (k - 1))

lowbit 运算

lowbit(n)n 在二进制下「最低位的 1 和其后所有的 0」构成的数。

例:n=(101000)2lowbit(n)=(1000)2

定义 nin 在二进制下的第 i 位数字。n0 表示最低位的数字。

nk=1nk1n0=0,也就是 nkn 的二进制最低位的 1

  1. n 的每位取反,此时 nk=0nk1n0=1,其余位和原来相反;
  2. 再计算 n+1,此时 (n+1)k=1(n+1)k1(n+1)0=0,其余位仍和原来相反;
  3. 因此在 n & (n+1)[1],仅有第 k 位为 1。这就是 nlowbit
EXAMPLE
lowbit((10101000)2)=(10101000)2 & ((10101000)2+1)=(10101000)2 & ((01010111)2+1)=(10101000)2 & (01011000)2=(00001000)2

由于在 C++ 采用的补码表示下 n=∼n+1,故

lowbit(n)=n & (n+1)=n & n
cpp
int lowbit(int x) {
    return x & -x;
}

  1. n:将 n 的二进制每位取反。 ↩︎