リリース・改善中
Algorithm
ビット演算は整数を2進数のビット列として扱い、AND・OR・XOR・シフトで集合、フラグ、bit DP を高速かつ簡潔に表現する手法です。
ビット演算は、整数を 0 と 1 の並びとして捉え、AND、OR、XOR、NOT、シフトで特定のビットを読み取り、立て、下ろし、反転させる手法です。コンピュータは整数を2進数で、負の数を2の補数で保存しているため、これらの演算はたいてい CPU の1命令で終わります。x & -x で最下位の1ビットを取り出し、x & (x - 1) でそのビットを消すように、短い式ひとつでループを置き換えられることもあります。
ビット演算が重要なのは、20個前後の要素からなる集合を整数ひとつで表し、すべての部分集合を列挙したり、集合を状態とする bit DP(ビットマスク DP)を組んだりできるからです。競技プログラミングやコーディング面接では部分集合の列挙、XOR の性質、popcount がよく出題され、実務でもファイルのパーミッション、機能フラグ、サブネット計算、ハッシュテーブル、ビットマップインデックスに使われています。ただし、Python の整数は上限がなく、JavaScript は32ビットに変換して >>> を持ち、Java にも >>> があり、C++ では符号なし型を使うのが安全というように、言語ごとに規則が異なる点に注意が必要です。
学習は、数値を手で2進数や2の補数に変換してみるところから始めるのがおすすめです。次に、1ビットを立てる・下ろす・反転する・調べるという4つの操作に慣れ、マスクを 0 から 2^n - 1 まで回して部分集合を出力してみます。そのうえで部分マスクの列挙や、割り当て問題・巡回セールスマン問題などの bit DP に進み、最後に自分の使う言語の整数幅とシフトの規則を確認します。
負の数は全ビットを反転して1を足した2の補数で表されます。左シフトは2倍、右シフトは2で割る操作で、言語によって算術シフトと論理シフトが区別されます。
マスク 1 << i と OR、AND NOT、XOR で i 番目のビットを立て、下ろし、反転します。x & -x は最下位の1ビット、x & (x - 1) はそのビットを消した値です。
n 要素の部分集合は 0 から 2^n - 1 までの整数と一対一に対応し、和集合・積集合・差集合はビット演算1回で求まります。
立っているビット数は x &= x - 1 の繰り返しや組み込み関数で数えます。a ^ a = 0 を使えば、ペアのない値の検出、ハミング距離、グレイコードが簡単に求まります。
popcount は x &= x - 1 で最下位の1ビットを1つずつ消しながら、立っているビットの数を数えます。subsets はマスクを 0 から 2^n - 1 まで回し、i 番目のビットが立っている要素を選んですべての部分集合を作ります。最後の行は、12 & -12 が最下位の1ビットである 4、12 & 11 がそのビットを消した 8、x ^ x が 0 になることを示します。python bit_manipulation.py で実行します。
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pyインストールから ビット演算 の中心となる考え方まで、6 章で順を追って学びます。
ビット演算 について質問し、経験を共有し、意見を交わす場所です。
まだディスカッションはありません。最初の話題を始めましょう。
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。