奇数判定とbit演算子

この記事は例としてPythonのコードが書いてありますが、Pythonに限らず多数のプログラミング言語で共通の概念です。

---

変数numが奇数か偶数か判定するのに`num % 2 != 0`として剰余の有無で調べる方法は一般的だと思います[^1]  
しかし`num & 1`でも判定できると聞きました。
とりあえずやってみましょう。


```python
def fn1(num):
    if num % 2 == 1:
        return "odd"
    else:
        return "even"


def fn2(num):
    if num & 1:
        return "odd"
    else:
        return "even"


for i in range(1, 100):
    a = fn1(i)
    b = fn2(i)
    assert a == b
```

forで1-99までの数値`i`を2つの関数で比較、assertで確認しています。もし2つの関数が違う値を返したらエラーになりますが、何回やってもエラーは出ませんでした。

「ふーん、そっかそりゃ良いこと聞いた」で終われれば良いのですが、理屈がわからないと気持ち悪いので調べました。

## ビット演算子

`num & 1`の`&`はビット演算子です。
ビットとは何か？それはザックリ言うとコンピューターの最小単位、1か0かです。つまり2進数の一桁目。
`&`は右辺と左辺を比較して**どちらも1なら1、どちらかが0なら0を返します**

| 左辺 | 右辺 | 結果 |
|:-:|:-:|:-:|
|  0 |  0 | 0  |
|  0 |  1 | 0  |
|  1 |  0 | 0  |
|  1 |  1 | 1  |

`num & 1`で言うと右辺は1で固定です。なので`num`が0なら偶数、1なら奇数になります。数値を条件式に使える言語[^2]では1はTrue、0はFalseと判定されるのでこれだけで判定できるということです。

[ビット演算入門 \- Qiita](https://qiita.com/Ingward/items/43acda931c8a62c70d2f)

「なるほどなるほど。これで解決だね」…とはいきません。
`num`は2かもしれないし3かもしれない。もしかしたら100億兆円かもしれない(←?)  

*まだまだ謎は解けない...*

## バイト

「コンピューターは1と0の集合体」と同じくらいよく耳にするのが「コンピューターはバイト単位で計算する」ということ。
「1バイト=8ビット」とも聞きますね。
つまり`8桁=1バイト`です。そこに含まれる数字はもちろん1か0です。つまり8桁の2進数ということ。

変数`num`に`1`を入れた時、プログラムは`1`ではなく`00000001`というバイト単位で格納します。
`2`は2進数だと`10`ですが、これもバイト単位で`00000010`として処理します。
ここで10進数と2進数の対応表を見て下さい。

|10進数|2進数|
|--:|:--|
|0|0|
|1|1|
|2|10|
|3|11|
|4|100|
|5|101|
|6|110|
|7|111|
|8|1000|
|9|1001|
|10|1010|
|11|1011|
|12|1100|
|13|1101|
|14|1110|
|15|1111|
|16|10000|
|17|10001|
|18|10010|
|19|10011|
|20|10100|

このまま数が増えていき、10進数の`255`は2進数で`11111111`となり1バイトで表す最大値になります。
同様に数が増えていき`65536`が2バイトでの最大値になります。
mysqlの`TINYINT `、`SMALLINT`(共に符号なし)と同じになりますね。

ちょっと脱線しました。話は大きく戻ってビット演算子です。最初にビット演算子は**どちらも1なら1、どちらかが0なら0を返します**と言いましたが、実はコレもバイト単位で比較しているのです。



*お...何かが見えてきたぞ...?*

## 解決編

例えば`16&20`という演算をする場合、16はバイト単位で`00010000`、20は`00010100`となります。
この**全ての桁で演算をして**結果を出しています。

||A|B|C|D|E|F|G|H|
|:--|:--|:--|:--|:--|:--|:--|:--|:--|
|16|0|0|0|1|0|0|0|0|
|20|0|0|0|1|0|1|0|0|
|結果|0|0|0|1|0|0|0|0|

D列は`どちらも1`なので結果は1になっていますが、他の列は全て`どちらかが0`なので結果も0になっています。
この結果を10進数に戻すと16。すなわち`16 & 20 == 16`となります。


話を最初に戻しましょう。何故`num&1`で奇数判定ができるのかという話です。

`num&1`の右辺は常に`1`ですので`num`が何桁あろうとも結果の1桁目以外は必ず`0`になります。

||A|B|C|D|E|F|G|H|
|:--|:--|:--|:--|:--|:--|:--|:--|:--|
|num|||||||||
|1|0|0|0|0|0|0|0|1|
|結果|0|0|0|0|0|0|0|?|


そして10進数と2進数の対応表をもう一回見て下さい。ある法則が見えてきます。
`奇数の1桁目は常に1`であり、`偶数の1桁目は常に0`なのです!

**謎は全て解けた！！！**

1. `num`の1桁目を見れば偶数か奇数か判定できる
2. `num`と1の論理積を求めれば`num`の1桁目が返る
3. `num&1`の解が`1`なら奇数、`0`なら偶数である

ちなみに、**どちらも1なら1、どちらかが0なら0を返します**というヤツは**論理積**というらしいです。
「積」つまり掛け算。

- 0x0=0
- 0x1=0
- 1x0=0
- 1x1=1


[論理積](https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E7%A9%8D)


### まとめ

「奇数判定するスマートな方法ないかなぁ」でググって知るまで3分。
`num&1`で判定できると知ったものの理屈がわからなくて調べるのに1時間半。
この記事を書くのに1時間半。

この3時間が無駄なのかどうかはわかりませんが、これだけ時間をかけたのでもう忘れません。
たぶん忘れない。忘れないんじゃないかな。ま、ちょっと覚悟はしておけ。

( 完 )

### 追記

自分なりの解釈で間違ってないとは思いますが、もし間違っていたらコメント欄から教えて頂けると喜びます。

[^1]: 奇数判定を剰余で行うには`num % 2 == 1`ではなく`num % 2 != 0`とした方が良いそうです（コメント欄参照）
[^2]: True/False以外の値を条件式でどのように扱うかについては[こちら](https://qiita.com/BlueRayi/items/a7753cc1657791f6504a#truthy%E3%81%A8falsy%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E9%9B%91%E8%AB%87)に説明があります