状态压缩

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

将 bool 数组 $a$（长为 $n$）用 $n$ 位二进制数表示，它的第 $i$ 位表示 $a[i]$.

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

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