奇数判定とbit演算子

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

---

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

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なら奇数になります。数値を条件式に使える言語²では1はTrue、0はFalseと判定されるのでこれだけで判定できるということです。

ビット演算入門 - Qiita

「なるほどなるほど。これで解決だね」…とはいきません。
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

論理積

まとめ

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

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

( 完 )

追記

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

1. 奇数判定を剰余で行うにはnum % 2 == 1ではなくnum % 2 != 0とした方が良いそうです（コメント欄参照） ↩

2. True/False以外の値を条件式でどのように扱うかについてはこちらに説明があります ↩