はじめに

組み合わせを網羅する場合に利用できるアルゴリズムとして「ビット全探索」と呼ばれるものが有名です。しかしながら、背景知識がない場合は直感的に理解しづらい内容でもあります。

今回はその「ビット全探索」について簡潔に解説します。

ビットとは

２進数、つまり「0 か １」のことです。組み合わせとはつまり「組み合わせに含めるか」「含めないか」の２パターンですので、これを２進数に置き換えて考えることになります。

組み合わせに含めるそれぞれの要素について「組み合わせに含めるか」「含めないか」を考えるので、計算量は ２のn 乗になります。

数字の組み合わせを用いた例

例えば、100, 200 という2個の数字から得られる組み合わせは 以下の4通りです。

• 何も選ばない
• 100
• 200
• 100, 200

ここで、100 と 200 について、「使う」「使わない」で 「０」と「1」に見立てて考えると

• 0, 0 （何も選ばない）
• 1, 0
• 0, 1
• 1, 1

となります。

これがビットに置き換えた状態です。

シフト演算

ビットに置き換えると何が良いかというと、特殊な計算が可能になります。その一つが「シフト演算」と呼ばれるものです。実際の例を見た方がわかりやすいかと思います。

ビットシフトの例

シフト演算には「右シフト」「左シフト」があります。

• 0010 0110 -右に1シフト-> 0001 0011
• 0011 0101 -左に2シフト-> 1101 0100

１の位置が、右や左にずれていることが確認できます。難しく考える必要はありません。

要はシフトすると倍にしたり半分にしたりできるということです。

• 右1シフト: 1/2倍 100（4） -> 010（2）
• 左1シフト: ２倍 010（2） -> 100（4）

任意の位置にフラグを立てる

ではこのシフト演算がなんの役に立つかというと、「任意の位置にフラグを立てる」ことができるようになります。

大抵のプログラミング言語だとこんな書き方　(1 << i)　で、

• i = 1 なら 00000001 10進数だと1
• i = 2 なら 00000010 10進数だと2
• i = 3 なら 00000100 10進数だと4
• …

という具合に、右からi番目の位置にフラグを立てることができます。

任意の位置にフラグが立っているか調べる

さらに、ビット演算子の一つ`&`を使うと、ビット同士を並べて同じフラグが立っているか判定することができます。これをビット論理積 と言います。

• 00000100 & 00000111 => 1（true） 右から三番目が同じく１。
• 00000100 & 00000011 => 0（false） カブってる箇所がない。

ここまでを組み合わせると、`(bit & (1 << i))` という書き方で、`bit`の右から何番目のフラグが立ってるかを判定できるようになります。

ビットシフトを利用したフラグチェック

例えば2個の数字を「使うか/使わないか」{}, {0}, {1}, {0,1} の４通りの組み合わせ求めるなら

bit & (1 << i) の i に、０〜１の２個の値を入れて確かめる

実装になります。つまり、

00 & (1 << 0) つまり 00 & 01 -> false
00 & (1 << 1) つまり 00 & 10 -> false 

01 & (1 << 0) つまり 01 & 01 -> true⭐️ i=0
01 & (1 << 1) つまり 01 & 10 -> false

10 & (1 << 0) つまり 10 & 01 -> false
10 & (1 << 1) つまり 10 & 10 -> true⭐️ i=1

11 & (1 << 0) つまり 11 & 01 -> true⭐️ i=0
11 & (1 << 1) つまり 11 & 10 -> true⭐️ i=1

ビット論理積& がTrueの場合を見ることで、なぜか見事に組み合わせが網羅できます。

Rustで実装する

実装してみて、さらに理解を深めます。 以下は N 個の要素についてその全ての組み合わせを求める場合の実装です。

    // 全探索するので、n乗の計算が必要
    for bit in 0..(1 << n) {
 
        let mut combination = vec![]; // 組み合わせ配列

        for i in 0..n {
            // bitが立っている（組み合わせが有効）場合
            if (bit & (1 << i)) > 0 {
               combination.push(i);
            }
        }
        // 組み合わせの出力
        println!("{:?}", combination);
    }

※ (1 << n) は (n * n ) つまり n の２乗と同じ意味です。