状态压缩

用二进制数存储 bool 数组.

简介 #

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

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

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

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

lowbit 运算 #

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

例:$n=(101000)_2$,$lowbit(n)=(1000)_2$.

$n_i$:$n$ 在二进制下的第 $i$ 位数字. 设 $n_k=1$,$n_0\cdots n_{k-1}=0$.

  1. 将 $n$ 的每一位取反,此时 $n_k=0$,$n_0\cdots n_{k-1}=1$,其余位和原来相反.
  2. 再令 $n=n+1$,此时 $n_k=1$,$n_0\cdots n_{k-1}=0$,其余位仍和原来相反.
  3. 因此 $n\&(\sim n+1)$ 仅有第 $k$ 位为 $1$.

由于在补码表示下 $-n=\sim n+1$,故

$$lowbit(n)=n\&(\sim n+1)=n\&-n$$

int lowbit(int x) {
    return x & -x;
}