状压dp中，位运算有哪些常用技巧？

本文共计880个文字，预计阅读时间需要4分钟。

ACM-ICPC 2018 南京赛区网络预赛 + E. AC Challenge（状态压dp） + 位运算

1.判断一个数字x二进制下第i位是否等于1。

方法：if ((1 << (i - 1)) + x) & 1==1 将1左移i-1位，相当于构造了一个只有第i位是1的二进制数，与x进行与操作，若结果为1，则第i位等于1。

​​ACM-ICPC 2018 南京赛区网络预赛 E. AC Challenge（状压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) )

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

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

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


4.把一个数字二进制下第i位置0

方法： x=x&~(1<<(i-1))

题目

有 n 个问题需要解决，但是每个一问题都有

个前置问题需要先解决才行。