(一)在状压dp中,对于二进制状态,我们可以通过多种方式提取,改变,以下是操作规则
1.取出整数n在二进制下表示下的第k位 :(n >> k) & 1
2.取出整数n在二进制表示下的第0~k - 1位(后k位):n & ((1 << k) - 1)
3.把整数n在二进制表示下的第k位取反 :n xor (1 << k)
4.把整数n在二进制表示下的第k位赋值1 :n | (1 << k)
5.把整数n在二进制表示下的第k位赋值0 :n & (~(1 << k))
也可以用bitset实现.
(二)lowbit的实现:
n & (~n + 1):推导:~后面的的0都变成1,最后一个1变成0,+1变成1000…
获取每一位1:n = n - lowbit(n)
(三)成对变换
通过计算可以发现,对于非负整数n:
n为偶数时,n xor 1等于n + 1,
n为奇数时,n xor 1等于n - 1,
0与1,1与2,2与3,..n与n + 1构成”成对变换”.
(四)如果进行位运算的时候不进位,那么每一位就是相互独立的,就可以分成每一位分别解决