はじめに

2で割ることと3で割ることという記事があり、めっちゃいい内容が書かれています。
しかし、後輩がそれを読んだところ「よく分からない」とのことだったので、
もう一歩どころか究極にかみ砕いて自分の勉強も兼ねて説明の記事を書きたいと思います。

そもそも、コンピュータの数字とは

2進法という話はなんとなく聞いたことあると思います。
電圧がかかっているか、かかっていないかで解釈をします。

物理みたいなおはなし

コンピュータは仮想化され、クラウド化されていってるのでコンピュータ本体を注意深く見たことなのかもしれませんが、
デスクトップパソコンとかイメージすると分かりやすいかもしれません。
あれを細かく見ていくと、中学校や高校で習った物理の回路のようなものがあって、電圧がかかっているかかかっていないかで0/1を認識しています。

2進法と10進法

コンピュータが0/1を認識しているのは分かりました。
しかし、我々が日常で扱う数字は10進法です。0の次は1だし、1の次は2。8の次は9だし、9の次は10です。

ただ、コンピュータには「0/1」しか認識しません。「3」とか言われても困ります。
0の次は1だし、1の次は10です。10の次は11だし、11の次は100です。

電流が流れるレーンのようなものをイメージするといいかもしれません。
1個のレーンで数字を表現しようとすると、0, 1の2種類。
2個のレーンで数字を表現しようとすると、00, 01, 10, 11の4種類。
3個のレーンで数字を表現しようとすると、000, 001, 010, 011, 100, 101, 110, 111の8種類。

勘のいい方は気づいたかもしれませんが、n個のレーンがあれば2^nの数字が表現できます。
多くの言語では32個のレーンを用いて数字を表現しますが、これが32ビットとか言われる所以です。
javaのintとか、Cのintとか、ScalaのIntとか、KotlinのIntとか32ビットで表現する数字です。

2147483647って数字見おぼえありませんか？
これは実は32ビットで表現できる最大の数字となっております。(※符号つきの場合)

シフト演算

シフト演算というのは、文字通り数字をシフトします。

000011 → 000110
000110 → 001100
001100 → 011000

こんな感じです。それぞれ10進法だとどうなるかというと、上から順番に
3→6, 6→12, 12→24というように数字が変化しています。そう、文字を左にシフトすると数字が2倍されているのです。

まあ、よくよく考えてみると当たり前でこれは2進法だからです。
我々の世界の数字で例の数字を見てみると、10倍になっているはずです。なぜなら、10進法だから。

これで逆に右にシフトしてあげれば半分になります。
これが2で割るということです。

3で割るということ

いきなり2進法で考えるから難しいです。
10進法で考えてみましょう。また、32ビットで考えると難しいので、10000までの数字しか数えられないとしましょう。

300 ÷ 3の例を考えます。結論からいうと、3334をかけます。
いきなり飛躍しすぎて分からなくなったかもしれませんが、具体的な数値計算を以下に書くのでなんとなくイメージできてくると思います。

300 ÷ 3 を計算したい。
300 * 3334 = 1000200
右シフト演算を4回行う
100が答えとして得られる

どうでしょうか。なんとなくイメージ沸いたのではないでしょうか。
300 ÷ 3 を 300 * 3334 ÷ 10000 で計算しているだけです。
つまり、300 * 0.3334 です。こう見れば自然に感じるのではないでしょうか。

最初に紹介した記事の例では32ビット演算子なので、数が大きくなっていますがマジックナンバー1431655766は上の例でいう3334のようなもんです。結局は0.3334をかけているのと変わりません。

(以下、指摘受けて追記)

イメージしやすさを優先するため、3334という数字をあげましたが、実際にはこれでは誤差が発生し、
正しく割り算できないケースがいくつかあります。

実際の32ビット演算の場合は最大値2^31-1 に対し、(2^32+2)/3をかけていますが、
この例の場合は最大値10^4に対し、(2×10^4+1)/3をかけるのが正確です。

なので、6667をかけて、20000でわることで計算結果が得られることになります。

これを踏まえれば、3で割るというのを掛け算で表現する話も納得できるんじゃないでしょうか。

余談

ちょっとこの記事を書いてて考えてたことをおまけとして書き連ねます。

逆元と群

普段、ぼくたちが「数字」と言っているのは実数という集合を指します。

この実数という集合と「×」という二項演算を考えると、
実数の集合の任意の元g には単位元をe (掛け算だと1です)とすると、

g × x = x × g = e

となるx が存在します。これを逆元といいます。
例えば、3の逆元は1/3です。3で割るということは3の逆元をかけることと同義です。

逆元が存在するということと、単位元が存在することについて触れましたが、これに加えて
結合法則

(a × (b × c)) = ((a × b)× c)

を満たします。
これをもって、実数の集合と掛け算の二項演算が「群」であると言ったりします。

おまけですが、これに加えて交換法則

a × b = b × a

が成り立つので、この群はアーベル群の性質を満たします。

「0の場合はどうなんだよ」と気づいたそこのあなた、ご名答です。
実数から0を除いた集合は演算「×」に対してアーベル群です。

32ビットの数字の集合と掛け算に逆元は存在するのか

いきなりこれを考えると難しいので、3ビットくらいでお手軽に考えてみましょう。

	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	0	4
5	5	2	7	4	1	6	3
6	6	4	2	0	6	4	2
7	7	6	5	4	3	2	1

というわけで、2の列を見てもらえれば分かるように、単位元の1がありません。
残念ながら、逆元が必ず存在するわけではなさそうです。

あれ、でも逆元が存在するものがありますね。
1は単位元そのものなのであたりまえですが、3, 5, 7は逆元がありそうです。

6 ÷ 3 = 6 × 1/3 = 6 × 3 = 18 \equiv 2 \pmod 8

おお～たしかに3, 5, 7については逆元の数字をかければよさそうです。

ここで、3, 5, 7を見て思ったのですが、
これ2^32と互いに素な数字であれば、逆元が存在するのでは・・・？

3で割るの別解

逆元を求めてみましょう。

3 × x \equiv 1 \pmod {2^{31}} \\
x = ( 2^{31}  + 1 ) / 3 = 715827883

というわけで、715827883をかけてあげれば3で割ることと同じ結果が得られそうです。
逆元が存在しない2^31と互いに素な数字(2の倍数以外)の割り算でしか使えませんが、
この逆元とシフト演算を使えばよいのではと思いました。

感想

なんだか解説記事を書くつもりが、だんだん深みにはまって新たな疑問が生まれました。
改めてアウトプットすることで見えてくるものがあるなと実感しました。

なぜコンパイラが最初に紹介した記事で紹介されている「数字をかけた後にシフト演算が必要な方法」をとっているかが分からなくなったので、どなたか詳しい方教えていただけると嬉しいです。。。