前置知识

位运算，状态压缩基本原理。

二进制操作	符号	运算规则
按位与	&	对于每一位二进制数比较，如果都为 1 取 1，否则取 0
按位或	|	对于每一位二进制数比较，如果都为 0 取 0，否则取 1
按位非	~	对于每一位二进制，0 变成 1，1 变成 0
按位左移	<<	将这个数的二进制表示向左移动一位，越界丢弃，低位补 0
按位右移	>>	将这个数的二进制表示向右移动一位，越界丢弃，高位补 0
按位异或	^	对于每一位二进制数比较，如果两个不同取 1，否则取 0

这种运算较为简便，而且常数非常小，在非状态压缩的情况下也经常使用。

二进制数压缩 bool 数组操作

操作	运算
取出整数 \(n\) 在二进制表示下的第 \(k\) 位	(n >> k) & 1
取出整数 \(n\) 在二进制表示下的后 \(k\) 位	n & ((1 << k) - 1)
将整数 \(n\) 在二进制表示下的第 \(k\) 位取反	n ^ (1 << k)
将整数 \(n\) 在二进制表示下的第 \(k\) 位赋 \(1\)	n | (1 << k)
将整数 \(n\) 在二进制表示下的第 \(k\) 位赋 \(0\)	n & (~(1 << k))

正确性证明

操作 1

将 \(n\) 右移 \(k\) 位后，其末即为第 \(k\) 位。此时将其和 \(1\) 按位与即可舍弃前面所有的位上的数据（原因是 \(1\) 的二进制表示中其他位全部为 \(0\)，按位与后的结果也是 \(0\) ），比较最后一位是 \(0\) 还是 \(1\)。若为 \(0\) 则返回 \(0\)，反之亦然。

操作 2

将 \(1\) 向左移 \(k\) 位后减 \(1\) 会得到 \(2^k - 1\) 的形式。这样的形式的二进制表达类似于 111...11 ，总共有 \(k-1\) 个 \(1\)。将原数和该数按位或该数，会自动忽略高位，原因同上。同时其原理也是 \(0\) 或 \(1\) 与上 \(1\) 总是等于自身。

操作 3

1 << k 操作的含义同上。\(0\) 或 \(1\) 异或上 \(1\) 总是取反，当 \(0\) 异或 \(1\) 两者不同结果是 \(1\)，而 \(1\) 刚好相反。这样可以利用一个形如 100...00 的二进制数，对单个位进行取反，故正确。

操作 4

1 << k 操作的含义同上。\(0\) 或 \(1\) 或上 \(1\) 总是为 \(1\)。这是基础定义，不用 Sora 多解释了。

操作 5

1 << k 操作的含义同上。但是将这个数取反就会得到一个形如 111...11011..111 的数。同时，我们知道 \(0\) 或 \(1\) 与上 \(0\) 总是为 \(0\)，\(0\) 或 \(1\) 与上 \(1\) 总是等于自身，那么就相当于修改了第 \(k\) 位为 \(0\)。认为这个操作比较妙。