bit全探索

　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　通りの組合せとなるので、２^n が記述されています。
　次に②の部分については、 bit演算子が使われており、少し見慣れない表記です。“ i >> j ” については i を2進数として、右に j だけ右ビットシフトさせる命令です。さらに“ & 1” については、難しく言えば1との論理積をとる命令で、ざっくり言えば右ビットシフトされた値の1番下の位が1かどうかを調べるものです。
　最後に③の部分で、②で True となった場合に、所定の桁（= 要素番号）へ 1を格納しています。

　上でも述べたように、このアルゴリズムは 2^n の計算を行いますので、n が大きくなると、プログラミンコンテストでは制限時間オーバー (TLE) になる可能性がありますのでご注意下さい。( n = 30 とすると 2^30 ≒ 10^9 !!）