例のごとくEffective Python。Item 7:Prefer enumerate over rangeを読んでいると、よくわからないコードが。

from random import randint

random_bits = 0
for i in range(32):
  if randint(0, 1):
    random_bits |= 1 << i

print(bin(random_bits))

出力

0b1100000100101110101011010000000

この章自体は、「インデックスを取得したいときにはlenとrangeを併用するよりも、enumerateを使ったほうがわかりやすいよ」というシンプルな内容だったのですが、この冒頭の部分についてはrangeの使いみちの一つとしてさらっと流されているので、まるでわからんぞ状態になりました。

特にifの条件に使われているrandintと、ビット演算らしきことを行っているrandom_bits |= 1 << iについてよくわかりませんでしたので、それぞれを調べてプログラムの挙動を理解してみました。

from random import randint

for _ in range(5):
  print(randint(0, 1))

出力

さらにこれがifの条件として利用されているので、1のときはTrueでif文の中が実行されて,0のときはFalse判定で実行されないという仕組みです。

まずrandom_bits |= 1 << iのうち、|=について。これは代入演算子のため、random_bits = random_bits | 1 << iと等価です。

bits1 = 0
bits1 = bits1 | 1 << 0
bits1 = bits1 | 1 << 3

bits2 = 0
bits2 |= 1 << 0
bits2 |= 1 << 3

print(bin(bits1), bin(bits2))

出力

0b1001 0b1001

次にビットOR演算ですが、これは2つのビット列の対応する位置でOR演算を行う、というもの。どちらも0のとき以外は1が返ってきます。

num1 = 5
print(bin(num1))
num2 = 13
print(bin(num2))
num_or = num1 | num2
print(bin(num_or))

出力

0b101
0b1101
0b1101

最後に左シフト演算ですが、これは指定した桁だけ左にずらして、空いたところはゼロ埋めするというものになっています。

bits = 1
print(bin(bits))
bits1 = bits << 1
print(bin(bits1))
bits2 = bits << 2
print(bin(bits2))
bits3 = bits << 3
print(bin(bits3))

出力

なお、ビットは2進数表現されていますので、nだけ左にシフトすると、10進数的には$2^n$倍になりますね。

num1 = 5
num2 = num1 << 1
num3 = num1 << 2
num4 = num1 << 3
print(num2, num3, num4)

出力

10 20 40

それでは本題です。みなさんもご存知の通り、演算子には優先順位が設けられています。

これをチェックしてみると、ビットOR演算子|と左シフト演算子<<では、左シフト演算子<<のほうが優先順位が高くなっています。

ここでは単純化を図るため、以下のプログラムを対象とします。

bits1 = 0
bits1 = bits1 | 1 << 0

上のプログラムでは、まず等号の右辺が評価されます。等号の右辺にはビットOR演算子|と左シフト演算子<<があるので、ここでは左シフト演算子が先に評価されて、1 << 0が計算されることになります。左に0シフトなので、特に何も変わることはありません。つまり1が左シフト演算子の計算結果です。

次にビットOR演算子|の計算が入ります。これは上述した通りビット列の対応した位置でOR演算を行うものです。先程の左シフト演算で1は1のままなので、

bits1 = bits1 | 1

というプログラムと等価になります。0と1のビットOR演算により、bits1は0から1になります。

ここまでを図にまとめると、以下のような感じになっています。

次に、bits1が1になった後の計算を考えます。今度はお相手として、1の3ビット左シフト演算とビットOR演算を行ってみます。つまり、以下のようなコードです。

bits1 = 1
bits1 = bits1 | 1 << 3

まず1を3ビット左にシフトさせる演算が先に行われます。結果は1000です。次にその1000と、1、つまり0001のビットOR演算が入ります。図に示すと以下のような感じ。

結果だけを見てみると、0001だったものが、1001になっています。言い換えると、3ビット左に1が追加されたということができるでしょう。

これは、お相手がもし2ビット左シフトだった時も同じです。こちらだと以下のような図になります。

このときは、2ビット左に1が追加されています。

つまり、

random_bits |= 1 << i

は、元の数のiビット左に1が追加される処理になります。

ここで冒頭のコードを再掲してみましょう。

from random import randint

random_bits = 0
for i in range(32):
  if randint(0, 1):
    random_bits |= 1 << i

print(bin(random_bits))

このコードは0から32までiを変化させるループの中で、1/2の確率で右からiビット目に1を追加する処理です。左シフトはゼロ埋めするので、1/2に当たらなかったときは必然的に0が入るようになります。結果的に、32ビットのランダムなビット列が生成されます。

何気ないところだったのですが、改めて調べてみると色々と理解を疎かにしていた仕様があったことを自覚しました。正直自分のプログラミング経験の中では、あえてビット列をランダム生成したくなったことがまだありませんが、頭の片隅においておきたいところです。

集合知に感謝。