Pythonでのbit全探索の実装

Question

前提・実現したいこと

以下に記す単純な全探索のコードを理解したい。
for文の文法はわかっている。
if文の内容が何をしているかよくわからないので、そこを理解したい

該当のソースコード

N = 3

for i in range(1<<N):
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):
            cond[j] = 1
    print(cond)

試したこと

ネットで解説をしらべて参考にした。

Comments

[can110]

提示コードの出典（書籍、URLなど）があれば追記ください。

Answer 1

まず、提示コードは間違っています。正しくは以下です。

for i in range(1<<3):
    cond = [0,0,0]
    for j in range(3):
        if 1&(i>>j):
            cond[j] = 1
    print(cond)

上記のrange(1<<3):によって、0...7の2**3個の値が得られます。
つぎにポイントのif 1 & i>>j:は、たとえばi=5の場合、以下のように動作しています。

• j = 0 にて 5 >> 0 の結果は5(b101)。それと1(b001) とのandの結果はTrue
• j = 1 にて 5 >> 1 の結果は2(b010)。それと1(b001) とのandの結果はFalse
• j = 2 にて 5 >> 2 の結果は1(b001)。それと1(b001) とのandの結果はTrue

よって[1,0,1]が得られます。
i=5以外も同様で、結果的に0...7の全ビット表現が得られます。

Comments

[pussy_pussy]

なるほど、1桁ずつずらして2進数表示のけたを1つずつ調べているのですね。
＞＞という論理演算子が使われたとき、〇＞＞の〇の数字は2進数表記で扱われるという理解でよろしいでしょうか(デフォルトで)

[can110]

そうですね、二進表記というか数値として扱われます。