こんにちは。KENTEMに入社して3ヶ月目の新卒エンジニアS・Kです。
私は学生時代、アルゴリズムが大好きでよく勉強していました。その中でも面白いなと感じたbit全探索というアルゴリズムを紹介していきたいと思います。
はじめに
簡単な問題とプログラミングでの解法
突然ですが皆さんに問題です。
ここに3つのクイズがあります。3つのうちいくつかの問題を正解したところ、合計がちょうど7点になりました。正解したのはどの問題の組み合わせでしょう？
- 1問目: 2点
- 2問目: 3点
- 3問目: 5点
簡単でしたかね… 答えは当然、1問目（2点）と3問目（5点）の組みになります。
これをプログラミングで書いてみましょう。 おそらく、多くの方がfor文を入れ子（ネスト）にして組み合わせを探す方法を思いつくのではないかと思います。
# 問題ごとの点数 points = [2, 3, 5] target_score = 7 # 1問目を正解(1)するかしない(0)かのループ for i in range(2): # 2問目を正解(1)するかしない(0)かのループ for j in range(2): # 3問目を正解(1)するかしない(0)かのループ for k in range(2): # 現在の組み合わせの合計得点を計算 # i, j, k が 1 なら点数が加算される current_score = (i * points[0]) + (j * points[1]) + (k * points[2]) # 合計がターゲットの7点になったかチェック if current_score == target_score: print("組み合わせを発見！") # どの問題を正解したかを表示 if i == 1: print(f"- 1問目 ({points[0]}点)") if j == 1: print(f"- 2問目 ({points[1]}点)") if k == 1: print(f"- 3問目 ({points[2]}点)") print(f"合計得点: {target_score}点")
出力結果
組み合わせを発見！ - 1問目 (2点) - 3問目 (5点) 合計得点: 7点
この解法自体も間違いではないのですが、クイズの数が3個から4個になるだけで新たにfor文を追加しないといけなくなります。これだとあまりに扱いづらいですよね？
では、問題の数がいくつになってもコードの基本的な構造を変えずに済む方法はないのでしょうか？
あります.... それがbit全探索になります。このアルゴリズムを使えば問題数の変化にも対応できる柔軟なコードを書くことができます。
bit全探索とは？
組み合わせを「数値」で表現する
bit全探索はbit演算を利用して考えられるすべての組み合わせを効率よく調べるアルゴリズムのことです。これだけだとあまり理解できないと思うので、具体的な例を使って説明していきます。
まず「どの問題を正解したか」に関してすべての組み合わせを書き出してみましょう。「正解」を◯、「不正解」を✕で表します。
そして、◯を1、✕を0に置き換えます。これを2進数とみなして、10進数に変換してみます。なにが起きるでしょうか？
| 1問目 | 2問目 | 3問目 | → | 2進数 | → | 10進数 |
|---|---|---|---|---|---|---|
| ✕ | ✕ | ✕ | → | 000 | → | 0 |
| ✕ | ✕ | ◯ | → | 001 | → | 1 |
| ✕ | ◯ | ✕ | → | 010 | → | 2 |
| ✕ | ◯ | ◯ | → | 011 | → | 3 |
| ◯ | ✕ | ✕ | → | 100 | → | 4 |
| ◯ | ✕ | ◯ | → | 101 | → | 5 |
| ◯ | ◯ | ✕ | → | 110 | → | 6 |
| ◯ | ◯ | ◯ | → | 111 | → | 7 |
どうでしょうか？ この表を見ると、「どの問題を正解したか」という全ての組み合わせ（全8パターン）を2進数とみなし、それらを10進数に変換すると見事に0から7までの連続した整数になることが分かります。
この発見を逆に考えて見ましょう。0から始まる連続した整数（連番）を用意し、それらを2進数に変換すれば全ての組み合わせを漏れなく作り出せることが分かるはずです。
ただ、0からどの数までを用意すればよいのかはまだ分かりませんね。
この数を特定するために、まずは問題が2問の場合で考えてみましょう。
| 1問目 | 2問目 | → | 2進数 | → | 10進数 |
|---|---|---|---|---|---|
| ✕ | ✕ | → | 00 | → | 0 |
| ✕ | ◯ | → | 01 | → | 1 |
| ◯ | ✕ | → | 10 | → | 2 |
| ◯ | ◯ | → | 11 | → | 3 |
問題が2問（N=2）の場合、組み合わせは 22=4 通りあり、これは10進数の0 から 3 までの範囲に対応していることが分かります。
次に、これまで見てきた問題が3問の場合を改めて見てみましょう。
| 1問目 | 2問目 | 3問目 | → | 2進数 | → | 10進数 |
|---|---|---|---|---|---|---|
| ✕ | ✕ | ✕ | → | 000 | → | 0 |
| ✕ | ✕ | ◯ | → | 001 | → | 1 |
| ✕ | ◯ | ✕ | → | 010 | → | 2 |
| ✕ | ◯ | ◯ | → | 011 | → | 3 |
| ◯ | ✕ | ✕ | → | 100 | → | 4 |
| ◯ | ✕ | ◯ | → | 101 | → | 5 |
| ◯ | ◯ | ✕ | → | 110 | → | 6 |
| ◯ | ◯ | ◯ | → | 111 | → | 7 |
問題が3問（N=3）の場合は23=8 通りの組み合わせがあり、これは0から7までの連番に綺麗に対応しています。
これらの法則から問題の数をN個として0から2N−1までの連番を作れば、全ての組み合わせを網羅できるということが分かります。
実装
bit全探索の実装
したがって、bit全探索の実装はこのようになります。
- 0から2N - 1までの整数を一つずつ順番にチェックする。この整数が解答パターンに対応しています。
- ループで取り出した整数を2進数とみなし各ビットが1かどうかを調べます。例えば、3桁目が1であれば3番目の問題を「正解」とみなしその問題の得点を加算する。
- 合計点を計算し終えたらその点数が目的の値（今回は7点）と一致するかを判定する。
早速実装してみましょう。
1に関してはfor文を使えば簡単に実現できますよね。
N = 3 for i in range(2 ** N):
しかし、2で大きな壁にぶつかります。
そもそも、コンピューターに数字の『5』が、『1問目と3問目を正解したパターン』だとどのように伝えればいいのでしょうか？
これらを伝えるのに必要となるのが、右シフト演算子とAND演算になります。
これらの解説を行います。
右シフト演算子 (>>)
右シフト演算子 >> は、ある数値を2進数で表現し指定した数だけビット全体を右へずらす演算です。
例：121 >> 3
- 10進数を2進数へ変換 121 → 1111001
- 3ビット右へずらす1111001 → 0001111 (右側から溢れた001は消え、左側は0で埋められます)
- 2進数を10進数へ戻す1111 → 15
この結果、121 >> 3 の答えは 15 となります。
AND演算(&)
2つの数値を2進数として扱い、桁ごとに比較して両方のビットが 1 の場合のみ、結果のビットを 1 にする演算です。それ以外の組み合わせはすべて 0 になります。
例えば、13と10でAND演算を行ってみましょう。
- まず、それぞれの数値を2進数に変換します。
- 13 → 1101
- 10 → 1010
- 次に、各桁をANDのルールで比較していきます。 bitの両方が 1 のときだけ 1、それ以外は 0なので
1101 (13) & 1010 (10) ------- 1000 (8)
結果として得られた2進数 1000 を10進数に戻すと8になります。
したがって、13 & 10の計算結果は8です。
右シフト演算子とAND演算をコードに組み込む
では、これらをどのようにコードに組み込むのか見ていきましょう。コードにするとこのようになります。
N = 3 # 問題の数 # 0から7まで (2**N - 1 まで) ループする for i in range(2**N): # N個の桁を1つずつチェックする for bit in range(N): # i の bit桁目が1かどうかを調べる if (i >> bit) & 1: print(f" {bit}桁目は 1")
このコードで重要となるのが
if (i >> bit) & 1:
の部分です。 この部分で一体何をやっているのか、i = 5 (2進数で 101) の場合を例に考えてみましょう。
bitが0の時（1桁目をチェック）
まず i >> 0 で 101 を右に0個ずらします（変化なし）。
次に & 1 で一番右の桁が1か調べます。
101 & 001 ------ 001
結果が1なので、1桁目は1であることが分かります。
bitが1の時（2桁目をチェック）
i >> 1 で 101 を右に1つずらし、010にします。
次に & 1 で一番右の桁が1か調べます。
010 & 001 ------ 000
結果が0なので、2桁目は0であることが分かります。
bitが2の時（3桁目をチェック）
i >> 2 で 101 を右に2つずらし、001にします。次に & 1 で一番右の桁が1か調べます。
001 & 001 ------ 001
結果が0ではないため、3桁目は1であることが分かります。
(i >> bit) & 1がどのような動きをしているか理解していただけたでしょうか？この一行だけでどの桁に1が立っているかを正確に調べることができます。
bit全探索で問題を解いてみる
それではbit全探索を使って、最初に出された問題のコードを作り直してみましょう。
冒頭のfor文を3つ重ねたコードが、bit全探索を使うとこのようになります。
# 問題ごとの点数 points = [2, 3, 5] target_score = 7 N = len(points) # 問題の数 # 0から7 (2**N - 1) までループし、全ての組み合わせを試す for i in range(2**N): current_score = 0 selected_problems = [] # どの問題を正解したか記録するリスト # i の各ビットをチェックし、どの問題が選ばれたか調べる for bit in range(N): # i の bit桁目が1かどうかを調べる if (i >> bit) & 1: # bit桁目が1なら、その問題は正解 current_score += points[bit] selected_problems.append(bit + 1) # 合計点がターゲットと一致するかチェック if current_score == target_score: print("組み合わせが見つかりました", selected_problems)
出力結果
組み合わせが見つかりました [1, 3]
これによって問題の数だけfor文をネストにする必要がなくなり、問題数Nに依存しない柔軟なコードになりましたね。
以前の方法では問題が1つ増えるたびにfor文を追記する必要がありましたが、このコードならpointsリストの中身を[2, 3, 5, 8]のように変更するだけで問題数の変化に自動で対応できます。
まとめ
このように、for文を何重にも重ねるしかなかったコードが「組み合わせを2進数とみなす」だけで、見通しが良く柔軟なコードに生まれ変わりました。
複雑な問題も少し見方を変えるだけでスマートに解決できる。これがプログラミングの面白さの一つですね。
計算量についての補足（競技プログラミング）
bit全探索の計算量を考えてみましょう。
外側のループ：for i in range(2 ** N) → 2N回
内側のループ：for bit in range(N) → N 回
したがって、全体の計算量は O(N * 2N) となります。
このように、bit全探索はNが大きくなると指数関数的に計算時間が増加してしまいます。
N = 10 の場合: 10 × 210 ≈ 1万
N = 20 の場合: 20 × 220 ≈ 2000万
N = 30 の場合: 30 × 230 ≈ 300億
競技プログラミングのように実行時間に制約がある場面（通常1〜2秒）では、「1秒間におおよそ108回（1億回）の計算が実行できるか」が時間内に処理が終わるかどうかのひとつの目安になります。
この基準で考えると、N=20の約2,000万回の計算は十分に間に合いますが、N=30の約300億回では到底間に合わないことが分かります。
bit全探索は、Nが比較的小さい場合にのみ有効なアルゴリズムということをぜひ覚えておいてください。
おわりに
KENTEMでは、様々な拠点でエンジニアを大募集しています！ 建設×ITにご興味頂いた方は、是非下記のリンクからご応募ください。 recruit.kentem.jp career.kentem.jp
