状压dp中常用的位运算如何改写成一个长尾词的？

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

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

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

方法：if ((1 << (i - 1)) + x & 1) 将1左移i-1位，相当于构造了一个只有第i位为1的二进制数，与x进行与操作，判断结果是否为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 个问题需要解决，但是每个一问题都有

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