状态压缩动态规划（简称状压\(dp\)）是另一类非常典型的动态规划，通常使用在\(NP\)问题的小规模求解中，虽然是指数级别的复杂度，但速度比搜索快，其思想非常值得借鉴。
一、位运算相关知识
为了更好的理解状压\(dp\)，首先介绍位运算相关的知识。
1.&符号，\(x\&y\)，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如\(3(11)\) & \(2(10)=2(10)\)。
2.|符号，\(x\)|\(y\)，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如\(3(11)\) | \(2(10)=3(11)\)。
3.\(\wedge\)符号，\(x\)^\(y\)，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如\(3(11)\) ^ \(2(10)=1(01)\)。
4.<<符号，左移操作，\(x<<2\)，将\(x\)在二进制下的每一位向左移动两位，最右边用\(0\)填充，\(x<<2\)相当于让\(x\)乘以\(4\)。相应的，’\(>>\)’是右移操作，\(x>>1\)相当于给\(x/2\)，去掉\(x\)二进制下的最有一位。
这四种运算在状压\(dp\)中有着广泛的应用，常见的应用如下：
1.判断一个数字x二进制下第i位是不是等于1。
if(((1<<(i-1))&x)> 0){
}
将\(1\)左移\(i-1\)位，相当于制造了一个只有第\(i\)位上是\(1\)，其他位上都是\(0\)的二进制数。然后与\(x\)做与运算，如果结果>\(0\)，说明\(x\)第\(i\)位上是\(1\)，反之则是\(0\)。
2.将一个数字x二进制下第i位更改成1。
x = x | (1<<(i-1))
3.把一个数字二进制下最靠右的第一个1去掉。
x=x & (x-1)