状态压缩

简介

由于 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_{0}$ 表示最低位的数字。

设 $n_{k} = 1$ ， $n_{k - 1} \dots n_{0} = 0$ ，也就是 $n_{k}$ 为 $n$ 的二进制最低位的 $1$ 。

将 $n$ 的每位取反，此时 $n_{k} = 0$ ， $n_{k - 1} \dots n_{0} = 1$ ，其余位和原来相反；
再计算 $n + 1$ ，此时 $(n + 1)_{k} = 1$ ， $(n + 1)_{k - 1} \dots (n + 1)_{0} = 0$ ，其余位仍和原来相反；
因此在 $n & (\sim n + 1)$ 中^[1]，仅有第 $k$ 位为 $1$ 。这就是 $n$ 的 $lowbit$ 。

EXAMPLE

\begin{aligned} lowbit ((10101000)_{2}) & = (10101000)_{2} & (\sim (10101000)_{2} + 1) \\ = (10101000)_{2} & ((01010111)_{2} + 1) \\ = (10101000)_{2} & (01011000)_{2} \\ = (00001000)_{2} \end{aligned}

由于在 C++ 采用的补码表示下 $- n =\sim n + 1$ ，故

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

cpp

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