bit全探索は、その名の通り bit(2進数の1桁)を用い、全探索を行う方法です。bit をフラグのように使う事に特徴があります。
以下に3つの要素が与えられた場合を例に、考えられる組合せをすべて列挙するプログラムを紹介します。
python3での実装
n = 3 #要素数
for i in range(2 ** n): #①
mylist = [0 for i in range(n)] #結果を出力するためのlistの初期化
for j in range(n):
if ((i >> j) & 1): #②
mylist[n - 1 - j] = 1 #③
print(mylist)
# -->
#[0, 0, 0]
#[0, 0, 1]
#[0, 1, 0]
#[0, 1, 1]
#[1, 0, 0]
#[1, 0, 1]
#[1, 1, 0]
#[1, 1, 1]
まず、コードの中①の部分については、3つの要素について、使う場合 or 使わない場合 の2通りが考えられるので、2 x 2 x 2 = 2^3 = 8 通りの組合せとなるので、2^n が記述されています。
次に②の部分については、 bit演算子が使われており、少し見慣れない表記です。“ i >> j ” については i を2進数として、右に j だけ右ビットシフトさせる命令です。さらに“ & 1” については、難しく言えば1との論理積をとる命令で、ざっくり言えば右ビットシフトされた値の1番下の位が1かどうかを調べるものです。
最後に③の部分で、②で True となった場合に、所定の桁(= 要素番号)へ 1を格納しています。
上でも述べたように、このアルゴリズムは 2^n の計算を行いますので、n が大きくなると、プログラミンコンテストでは制限時間オーバー (TLE) になる可能性がありますのでご注意下さい。( n = 30 とすると 2^30 ≒ 10^9 !!)