介绍位运算相关的知识：

1.’ & ’符号，x&y，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。

例如 3(11)&2(10)=2(10)。

2.’ | ’符号，x|y，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。

例如 3(11)|2(10)=3(11)。

3.’ ^ ’符号，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 ((x>>i)&1)

2.将一个数字 x 二进制下第 i 位更改成 1。

方法：x = x | 1<<i

证明方法与 1 类似，此处不再重复证明。

3.把一个数字二进制下最靠右的第一个 1 去掉。

方法：x=x&(x-1)

位运算在状压 dp 中用途十分广泛。