什么时候用状态压缩？

需要标记当前点的访问状态，且题目的数据长度比较短（最好小于32位）。满足以上条件，那么就可以使用二进制表示长度为 32 的 int 来代指点是否被访问过。

示例

$(000…0101)_2$ 代表编号为 0 和编号为 2 的节点已经被访问过，而编号为 11 的节点尚未被访问。

常用操作

检查编号为$x$的点是否被访问过

使用位运算

1
a = (state >> x) & 1

来获取$state$中第 $x$ 位的二进制表示，如果 $a$ 为 $1$ 代表编号为$x$的节点已被访问，如果为$0$则未被访问。

标记编号为$x$的点已经被访问过

使用位运算

1
state | (1 << x)