競技プログラミングの過去問を試しているのですが、全然解けなくて、「bit全探索？」という状態から自分なりに理解するためにまとめました。
Androidアプリを作成しました。
感情用のメモ帳です。
bit全探索を使うとき
bit全探索は組み合わせを考えるときに、すべての選択肢を選んでもいいし、選ばなくてもいいときに使えます。
たとえばトランプが3枚あって（J、Q、K）、これら3枚とも選んでもいいし、1枚でも、2枚でも、またすべてを選ばなくてもいい、といった場合の組み合わせを得たいときなどです。
bit全探索で得られる組み合わせは、2nで、トランプ3枚の場合、23の8パターン、4枚だと24の16となります。
ただnは指数なので、nの大きさによって、得られるパターン・計算量は急増する傾向にあります。
すべてのトランプ（52枚）を組み合わせると、252――4,503,599,627,370,496と膨大な数になり、もしコードを書いて実行したとしても、結果はいつまで経っても返ってこないことになります。
（私の環境でコードを実行して計算が終わるまでの時間を計測したところ、220で3秒、225で2分6秒、230では30分待っても終わらなかったため諦めました。パソコンの性能や使用するプログラミング言語によって差はあるはずですが参考までに）
コード
カード3枚の組み合わせを実際にコードとして書くと、次のようになります。
cards = ['J', 'Q', 'K']
n = len(cards)
for bit in range(1 << n):
combination = []
for i in range(n):
shift_i = 1 << i
if bit & shift_i > 0:
combination.append(cards[i])
print(combination)4行目の「1 << n」というのは、1（2進数で表すと0001）をn桁ぶん左側にシフトさせる、というものです。
nはリストの長さなので、0001を左に向かって3桁移動させると、1000になり、つまり十進数の8になります。（rangeの中身を(2**n)と書いても結果は同じ）
※<<と>>はpythonの演算子。「a << b」はaを対象としてb桁左シフト、「a >> b」はaを対象にb桁右シフトを行います。
7行目の「shift_i = 1 << i」は、iの数値分、1を左シフトし、変数に代入します。
8行目の「if bit & shift_i > 0:」でbitとi桁シフトされた1とのAND演算を行い、0より大きければ、組み合わせを入れる変数に追加します。
実行してみると、以下のような結果が得られます。
[]
['J']
['Q']
['J', 'Q']
['K']
['J', 'K']
['Q', 'K']
['J', 'Q', 'K']変数を追いかける
これだけでは理解しづらかったので、変数等の中身を確認できるようにコードにいくつか変更を加えました。
cards = ['J', 'Q', 'K']
n = len(cards)
def print_lines(line, *text):
line *= 17
print(line)
for t in text:
print(t)
print(line)
for bit in range(1 << n):
print_lines('=', f'bit: {bit}')
combination = []
for i in range(n):
shift_i = 1 << i
if bit & shift_i > 0:
print_lines('-',
f'i: {i}',
f'{bit:03b} & {shift_i:03b} -> {(bit&shift_i):03b}')
combination.append(cards[i])
print_lines('+', 'Result', combination)出力を整えるための変更で、「if bit & shift_i > 0」が真になったときの、変数を表示させます。
長いので結果を一部抜粋。
=================
bit: 0
=================
+++++++++++++++++
Result
[]
+++++++++++++++++
=================
bit: 1
=================
-----------------
i: 0
001 & 001 -> 001
-----------------
+++++++++++++++++
Result
['J']
+++++++++++++++++
=================
bit: 2
=================
-----------------
i: 1
010 & 010 -> 010
-----------------
+++++++++++++++++
Result
['Q']
+++++++++++++++++「bitが0」のときは、結果のリストは空です。
AND演算は片方が0なら、結果も0になります。
「bitが1、iが0」の時にリストに追加されています。
iは数値の1を左シフトする桁数だったので今回はシフトが行われず、「001 & 001」のAND演算となり結果「001」になり、0より大きく真となるためです。
iが1だった場合、左に1桁シフトされるので、「001 & 010」、結果「000」の偽になります。
「bitが2、iが1」の時も真です。
2の2進数「010」と1を左に1桁シフトした「010」がAND演算により「010」となるからです。
こうして見ていくと、bitを2進数で表したものを下位の桁から順に確認していき、1かどうか確かめていく構造だと言えます。
そしてbitの2進数表記と、組み合わせ方のパターンが対応していることがわかります。
bitが3以降の結果を掲載。
=================
bit: 3
=================
-----------------
i: 0
011 & 001 -> 001
-----------------
-----------------
i: 1
011 & 010 -> 010
-----------------
+++++++++++++++++
Result
['J', 'Q']
+++++++++++++++++
=================
bit: 4
=================
-----------------
i: 2
100 & 100 -> 100
-----------------
+++++++++++++++++
Result
['K']
+++++++++++++++++
=================
bit: 5
=================
-----------------
i: 0
101 & 001 -> 001
-----------------
-----------------
i: 2
101 & 100 -> 100
-----------------
+++++++++++++++++
Result
['J', 'K']
+++++++++++++++++
=================
bit: 6
=================
-----------------
i: 1
110 & 010 -> 010
-----------------
-----------------
i: 2
110 & 100 -> 100
-----------------
+++++++++++++++++
Result
['Q', 'K']
+++++++++++++++++
=================
bit: 7
=================
-----------------
i: 0
111 & 001 -> 001
-----------------
-----------------
i: 1
111 & 010 -> 010
-----------------
-----------------
i: 2
111 & 100 -> 100
-----------------
+++++++++++++++++
Result
['J', 'Q', 'K']
+++++++++++++++++bitが1（001）のときリストは「Ｊ 」
bitが3（011）のときリストは「Ｊ・Ｑ 」
bitが5（101）のときリストは「Ｊ・ Ｋ」
bitが7（111）のときリストは「Ｊ・Ｑ・Ｋ」
このように対応しています。
まとめ
bit全探索は組み合わせを考えるとき、すべての選択肢を選んでもいいし、選ばなくてもいいときに使える。
指数関数的に計算量が増えるため、指数の大きさに注意。
2進数の表記と得られるパターンは一致する。
コードの部分は分かりやすいように変数に代入し、演算と比較を行っていました。
shift_i = 1 << i
if bit & shift_i > 0:特に()をつけず直接書いても優先順位的に問題はありません。
if bit & 1 << i > 0:また次のように書いても同じ結果を得ることができます。
if bit >> i & 1 > 0:bitの方をi桁ずつ右にずらしていき、下位から上位桁まで1とのAND演算をします。
このページが少しでもお役に立てたのなら幸いです。