bit演算
Pythonでの記法
論理積 AND : a & b
論理和 OR : a | b
排他的論理和 XOR : a ^ b
ビット反転 NOT : ~a
算術シフト : a << b, a >> b
小技
-1 & x = x
xがどんなに大きくてもちゃんと処理してくれる。そう、Pythonならね。
最も下の立っているビット : x & -x
x = 01011000
-x = 10101000
x & -x = 00001000
配列の後ろから（0-indexedで）i番目 : A[~i]
A[-i]は1-indexedっぽくて使いづらいときに
A[-i-1]とするよりもスマート
(x+1) = -~x
x = 01011000
~x = 10100111
-~x = 01011001 = x+1
(x-1) = ~-x
x = 01011000
-x = 10101000
~-x = 01010111 = x-1
この2つはコードゴルフでしか使わなそう
bitDPでiに対して部分集合j ⊂ iを列挙する : j = (j - 1) & i
実際の運用
code:bitDP.py
j = i
while j > 0:
'''何らかの処理'''
j = (j - 1) & i
$ O(4^N)を$ O(3^N)に減らせるので普通に重要
その他
$ s \oplus t = (1 - s)t + s(1-t) = (~s)*t + s*(~t)
あるいは$ (0, 1) を$ (-1, 1) に変換して積を取る→符号を反転→逆変換
andorの演算
a and bはb if a else a
a or bはa if a else b
になるっぽい。a & bやa | bとは意味が異なる。
『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』に色々載ってるらしい。
実用性は微妙らしいが気になる木