Pythonでもbitsetを使いたい
「Python bitset」で検索すると以下のツイートがヒットする。
maspy @maspy_stars
pythonでbitsetが欲しいときには、多倍長整数をそのままbitsetとして扱うとよいぞ。
演算
集合演算operator&=operator|=operator^=operator<<=operator>>=
同様にa & ba | ba ^ ba << na >> nとすればいい
a << nは範囲オーバーする可能性アリ。MLEやTLEの可能性があるので対処したいところだが……
a >> nはaの正負によって挙動が若干変わる。
ビット設定set
i番目を1にするならa | (1 << i)、0にするならa & ~(1 << i)
ビット反転operator~flip
~aでOK。ただし正負は入れ替わる
要素アクセス
アクセスoperator[]test
(a >> i) & 1でi番目のビットだけを取り出せる。
iが範囲外のときの動作には注意が必要
ビットカウントcount
a.bit_count()（Python 3.10以降）
aが負のときは-aでの個数を数えるらしい
判定allanynone
anyはa != 0、noneはa == 0。
allは……前もってX = 0b1111...111を用意してa & X == Xとかだろうか
言語アップデートでbitarrayライブラリが追加された。
速度が遅いという噂もあるが……