bit全探索で沼った！！ #Python

bit全探索で沼ったのでそもそものpythonでのbit演算子周りの知識をまとめた自分用の備忘録です。

bit全探索のお気持ち表明

for i in range(2**N):
    for j in range(N):
        if (i>>j) & 1:

まずはpythonでbit全探索をするときの基本となるこの形の意味を簡単にまとめる。

そもそもbit全探索のお気持ちは、 $N$ 個あるYes,Noの選択肢の取り得るすべてのパターン$2^N$通りを全て探索したいということ。

考え方をステップごとに細分化します。

ステップ１（一行目）：
$2^N$パターンのそれぞれの状態に、その状態を表す番号として10進数表記で $0$ から $2^N-1$ をふる。

ステップ２（二行目）：
それを2進数表記にすると全部で $N$ 桁なので（$N$個の選択しに対して）、

ステップ３（三行目）：
それぞれの桁が $0$ か $1$ か（選択しないか選択するか）を順に調べていく。

って感じでしょうか。

つまるところ、選ぶか選ばないかの状態を、2進数表記のそれぞれの桁が $0$ か $1$ かで紐付けて表現することにより、各ビットが $0$ か $1$ かの判別を繰り返すだけですべての状態の評価ができるということです。

例えば、「○×クイズを3問解いたとき、解答として考え得る組み合わせを調べる」、という場合は以下の表のようになりますね。

この $2^3$ 通りのパターンをすべて調べるには $3$ bit分を調べればよいとわかりますね。当たり前です。

bit全探索のお気持ちはここまで。次はbitの扱いについて触れていきます。

組み込み関数のbin()を使うことで2進数表記にすることができます。
解説していくのは>>と&です。

&は論理積といわれ、bin()で2進数表記の文字列に変換した結果を出力します。

比較する値のビット数が等しいときは、そのまま自然な出力です。

> bin(5)    #'0b101'
> bin(6)    #'0b110'
> bin(5&6)  #'0b100'
> 5&6       #4

一方、ビット数が異なるときは短い方のビットまでの論理積が出力されます。

> bin(1)    #'0b1'
> 5&1       #1
> 6&1       #0

$5→101, 6→110$ であるので $1$ ビット目はそれぞれ $1,0$ です。
つまり、 $1$ との論理積をとることで、任意の２進数表記の値の $1$ ビット目が $0$ か $1$ かを判別できるということですね！

>>は右ビットシフトと呼ばれています。動作は以下の通り。

> bin(5)    #'0b101'
> bin(5>>1) #'0b10'

出力を見ての通りで、右に $1$ ビットシフトしているのがわかります。
何がうれしいかというと、 $1$ との論理積をとったときに今度は次のビットが $0$ か $1$ かの判別ができるということですね。
&と組み合わせることで一つずつビットをずらしながら調べることができますね。

畢竟、冒頭のコードの、

for i in range(2**N):
    for j in range(N):
        if (i>>j) & 1:

というのは、判定するビットを右に一つずつずらして全てのビットに対して順に $1$ との論理積をとることで、そのビットが立っているのか立っていないのかを判別していたのです。

繰り返しになりますが、bit全探索のうまみは一対一対応で各状態を $0$ と $1$ の表記で表せることであり、かつbit演算子を使えば簡単に全パターンを評価できるということです。