简介

由于 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 运算

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

例：$n=\phantom{0}$$\phantom{0}(101000{)}_2$，$\mathrm{lowbit}(n)=\phantom{0}$$\phantom{0}(1000{)}_2$。

定义 $n_i$：$n$ 在二进制下的第 $i$ 位数字。$n_0$ 表示最低位的数字。

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

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

EXAMPLE

$$\begin{array}{rl}\mathrm{lowbit}((10101000{)}_2)& =(10101000{)}_2\mathrm{\&}(\sim (10101000{)}_2+1)\\ & =(10101000{)}_2\mathrm{\&}((01010111{)}_2+1)\\ & =(10101000{)}_2\mathrm{\&}(01011000{)}_2\\ & =(00001000{)}_2\end{array}$$

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

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

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

---

1. $\sim n$：将 $n$ 的二进制每位取反。 ↩︎