bit全探索

bit全探索について学びます。

bit全探索とは

探索をbitを用いて行うことです。 あるN個のものから、選択する・しないを0か1で表すことで、全てのパターンを列挙することができます。 例えば、N=4のとき、2⁴=16パターンの列挙に、0000〜1111の2進数を用います。

基本的な考え方

全探索と言っているので、全てのパターンを網羅的に調べ上げます。 この時、N=4であれば、16パターンになりますが、10進数の0〜15を２進数に直します。 そこで、どのビットが1になっているかを判定することで、4種類の全ての状態を網羅できます。

実装方法

まず、入力Nに対して、2^N回のループを回します。（以下、pythonでの実装となります。）

for i in range(2 ** N)

次に、上記のループで回している数について、2進数での各bitが1になっているかをシフト演算を用いて調査します。

for j in range(N):
    #ここがシフト演算
    if (i >> j) & 1:
        #何かする

何をしているのか。
例えばN=3を例にとってみましょう。N=3の場合、2³は以下の８パターンがあります。

10進数	2進数
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

このうち、5の（101）に注目してみましょう。
0〜2ビット右シフト演算をすると、結果は以下のようになります。
101 → 101
101 → 010
101 → 001
一番下位桁が1になる場合に、その桁が表す選択肢を何か実行すれば良いわけです。
ここまでをまとめてみます。
例として、３種類の果物の選び方を全て列挙してみます。

#bit全探索
n = 3

fruits = ["みかん", "りんご", "ぶどう"]
for i in range(2 ** n):
    result = []
    for j in range(n):
        if (i >> j) & 1:
            result.append(fruits[j])
    print(result)

結果

[]
['みかん']
['りんご']
['みかん', 'りんご']
['ぶどう']
['みかん', 'ぶどう']
['りんご', 'ぶどう']
['みかん', 'りんご', 'ぶどう']

うまくできましたね。
ここまで見てきた通り、bit全探索は与えられた数に対してそれぞれ「選ぶ」「選ばない」を網羅して調べるときに使えます。
ただし、Nがあまりにも大きいと、パターンの数が膨大になってしまうため、bit全探索は使えません。

以上です。