二进制状态压缩是指将一个长度为 m 的 bool 数组用一个 m 位二进制整数表示并存储的方法。
利用下列位运算操作可以实现原 bool 数组中对应下标元素的存取。
| 操作 | 运算 |
| 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 |
| 取出整数 n 在二进制表示下的第 0 ~ k − 1 位 | n & ((1 << k) – 1) |
| 把整数 n 在二进制表示下的第 k 位取反 | n ^ (1 << k) |
| 对整数 n 在二进制表示下的第 k 位赋值 1 | n | (1 << k) |
| 对整数 n 在二进制表示下的第 k 位赋值 0 | n & (~(1 << k)) |
这种方法运算简便，且节省了程序运行的时间和空间。当 m 不太大时，可以直接使用一个整数类型存储。当 m 较大时，可以使用若干个整数类型（int数组），也可以直接利用 C++ STL 提供的 bitset 实现。
相关知识点：bitset