【Python】【小ネタ】ビットOR演算とシフト演算について

### まえがき
例のごとく[Effective  Python](https://www.amazon.co.jp/Effective-Python-Specific-Software-Development-ebook/dp/B07ZG18BH3/ref=tmm_kin_swatch_0?_encoding=UTF8&qid=1622279038&sr=8-2)。Item 7:Prefer ```enumerate``` over ```range```を読んでいると、よくわからないコードが。

```python:
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```についてよくわかりませんでしたので、それぞれを調べてプログラムの挙動を理解してみました。

### ```randint```の動作について
これは少し調べてすぐにわかりました。```random.randint(a, b)```は「a以上b以下の整数をランダムで返す」働きが[あります](https://docs.python.org/ja/3/library/random.html)。今回は```randint(0, 1)```なので、0以上1以下の値を返します。

```python:
from random import randint

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

```:出力
1
0
0
1
0
```

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

### ```if```の中で行われているビット演算について

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

```python:
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演算子```|```について

次にビットOR演算ですが、これは2つのビット列の対応する位置でOR演算を行う、というもの。どちらも0のとき以外は1が[返ってきます](https://www.javadrive.jp/python/num/index4.html#section1-1)。

```python:
num1 = 5
print(bin(num1))
num2 = 13
print(bin(num2))
num_or = num1 | num2
print(bin(num_or))
```

```:出力
0b101
0b1101
0b1101
```

#### 左シフト演算子```<<```について

最後に左シフト演算ですが、これは指定した桁だけ左にずらして、空いたところはゼロ埋めするというものになって[います](https://www.javadrive.jp/python/num/index4.html#section1-5)。

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

```:出力
0b1
0b10
0b100
0b1000
```

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

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

```:出力
10 20 40
```

#### それぞれの演算子の優先順位と結論
それでは本題です。みなさんもご存知の通り、演算子には優先順位が[設けられています](https://docs.python.org/ja/3/reference/expressions.html#operator-precedence)。

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

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

```python:
bits1 = 0
bits1 = bits1 | 1 << 0
```

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

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

```python:
bits1 = bits1 | 1
```

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

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

![ビット演算.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/278439/4913114d-c6d3-85f8-966f-968094cc2be5.jpeg)

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

```python:
bits1 = 1
bits1 = bits1 | 1 << 3 
```

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

![ビット演算 (2).jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/278439/1d03ccaa-8217-aed0-1e2a-8f9c145c1bdf.jpeg)

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

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

![ビット演算 (3).jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/278439/4e71adec-33ba-56a6-3bb5-5cddc2e66c80.jpeg)

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

つまり、

```python:
random_bits |= 1 << i
```

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

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

```python:
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ビットのランダムなビット列が生成されます。

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

集合知に感謝。

### 参考サイト様(アルファベット順)
 - [ Let'sプログラミング: ビット演算に関する演算子](https://www.javadrive.jp/python/num/index4.html#section1-1)
 - [Python.org: random --- 擬似乱数を生成する 整数用の関数](https://docs.python.org/ja/3/library/random.html#functions-for-integers)
 - [Python.org: 6.17. 演算子の優先順位](https://docs.python.org/ja/3/reference/expressions.html#operator-precedence)