「2種類の選択肢が複数ある問題」の「ありえる選択肢の組み合わせを」すべて列挙するためのアルゴリズムです。
以下の例だと、0か1を入れられる枠が５こあった時の組み合わせを列挙しています。
from itertools import product
N = 5
for p in product((0, 1), repeat=N):
print(p)
for i in range(N):
if p[i]:
# p[i]が1のときにやりたい処理
(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
(0, 0, 1, 0, 1)
(0, 0, 1, 1, 0)
(0, 0, 1, 1, 1)
(0, 1, 0, 0, 0)
(0, 1, 0, 0, 1)
(0, 1, 0, 1, 0)
(0, 1, 0, 1, 1)
(0, 1, 1, 0, 0)
(0, 1, 1, 0, 1)
(0, 1, 1, 1, 0)
(0, 1, 1, 1, 1)
(1, 0, 0, 0, 0)
(1, 0, 0, 0, 1)
(1, 0, 0, 1, 0)
(1, 0, 0, 1, 1)
(1, 0, 1, 0, 0)
(1, 0, 1, 0, 1)
(1, 0, 1, 1, 0)
(1, 0, 1, 1, 1)
(1, 1, 0, 0, 0)
(1, 1, 0, 0, 1)
(1, 1, 0, 1, 0)
(1, 1, 0, 1, 1)
(1, 1, 1, 0, 0)
(1, 1, 1, 0, 1)
(1, 1, 1, 1, 0)
(1, 1, 1, 1, 1)
枠の数をNとすると、上の例はN=5です。
ビット全探索では、Nが増えると指数関数的に計算量が増えてしまう（２のN乗）ので、Nが20を超えるときは使えないとされています。
pythonではitertoolsのproductを使えば一瞬でbit全探索を実装できますが、一応どの言語でもできる方法も試します。
N = 5
for bit in range(1 << N):
print(bin(bit))
for i in range(N):
if bit & (1 << i):
# bitの下からi桁目が1の時にやりたい処理
0b0
0b1
0b10
0b11
0b100
0b101
0b110
0b111
0b1000
0b1001
0b1010
0b1011
0b1100
0b1101
0b1110
0b1111
0b10000
0b10001
0b10010
0b10011
0b10100
0b10101
0b10110
0b10111
0b11000
0b11001
0b11010
0b11011
0b11100
0b11101
0b11110
0b11111
ビットの桁が少ないものは前がゼロ埋めされていると考えてください。
そうすると、intertoolsのproductで出力したビット全探索の結果と同じものが出力されていることがわかります。
for bit in range(1 << N):
例えばN=3のとき
1 << 3
の結果は、左シフト演算子に3を渡しているので1の右に0を3つ付けた以下になります
0b1000
これをrangeに食わせると、0から111のビットが全列挙されます。
for i in range(1 << 3):
print(bin(i))
"""
0b0
0b1
0b10
0b11
0b100
0b101
0b110
0b111
"""
if bit & (1 << i):
「bitの下からi桁目が1の時」をなぜこれで判定出来ているか。
N=5のとき、
1 << i
のiを1ずつ大きくして各桁の論理積をチェックしている様子を見てみると一目瞭然です。
>>> bin(0b10100 & 0b1)
'0b0'
>>> bin(0b10100 & 0b10)
'0b0'
>>> bin(0b10100 & 0b100)
'0b100'
>>> bin(0b10100 & 0b1000)
'0b0'
>>> bin(0b10100 & 0b10000)
'0b10000'