整数のビット表現を0から説明してみた

こんにちは。つい先日、炭化水素を頑張って数え上げる記事を投稿しました。その際、隣接行列をビットを使って表現するといった手法を使いました。

このあたりで一度基礎に立ち返って、プログラムで整数を扱うときにどのようにビット表現されているか？について復習してみようと思います。

二進法
符号なし整数
符号付き整数
(特殊な例) Python の int 場合
(特殊な例) JavaScript の Number の場合
まとめ

二進法

私たちは普段、十進法の表記を使って数を表現しています。十進法とは何かというと、十数えると位が一つ進む表記のことです。0 から順に数えるとこんな感じですね。

$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \textbf{10}, 11, 12, \dots$ 一の位が $0, 1, 2, \dots, 9$ と増えていって、次に増えるタイミングに次の十の位が生成されます。十の位も同様に $1, 2, \dots, 9$ と増えていき、次に増えるタイミングで次の百の位が生成されます。

二進法は、表記に使う数字を減らして、0 と 1 だけで表記する方法です。十進法では 9 になった次に新しい位が現れましたが、二進法の場合は 1 の次にすぐ新しい位が生成されます。0 から順に数えるとこんな感じになります。

$0, 1, \textbf{10}, 11, \textbf{100}, 101, 110, 111, \textbf{1000}, 1001, \dots$ 使う数字の種類が少ないので、すごい勢いで桁数が増えていきます。

十進法と二進法は、単なる表記の違いです。そのため、0 から数えて同じ場所にある表記は、同じ数を表していると考えます。

何進法の表記であるかを強調するときには、数字の右下にカッコ付きで表現します。十進法なら ${\cdot}_{(10)}$ , 二進法なら ${\cdot}_{(2)}$ という具合です。これを使って対応関係を書いていくと、以下のようになります。

$\begin{align}0_{(10)} &= 0_{(2)} \\ 1_{(10)} &= 1_{(2)} \\ 2_{(10)} &= 10_{(2)} \\ 3_{(10)} &= 11_{(2)} \\ 4_{(10)} &= 100_{(2)} \\ 5_{(10)} &= 101_{(2)} \\ &\vdots \end{align}$

符号なし整数

コンピュータの内部では 0 と 1 の状態を保持することができます。コンピュータはこの 0 or 1 の状態を大量に組み合わせて、これをいい感じに更新していくことで、あらゆるものを表現しています。この 0 か 1 の状態を保持できる単位のことを bit といいます。

このようなコンピュータで、整数をどのように表現できるか考えてみましょう。具体的に 4 つの bit (4 bit) を使ってみます。具体的に書き出してみると、以下の16通り*1が考えられることがわかります。

$0000\\0001\\0010\\0011\\0100\\0101\\0110\\0111\\1000\\1001\\1010\\1011\\1100\\1101\\1110\\1111$
ところで、この並びは二進法を順番に並べていったものと似ていますね。左端から続く 0 たちを無視すれば、もう完全に二進法です。そこで、この bit の状態の並びをそっくりそのまま二進法として解釈することにしましょう。これが符号なし整数です。 $\begin{alignat}{2}0000 &= 0_{(2)} &= 0_{(10)} \\ 0001 &= 1_{(2)} &= 1_{(10)} \\ 0010 &= 10_{(2)} &= 2_{(10)} \\ 0011 &= 11_{(2)} &= 3_{(10)} \\ 0100 &= 100_{(2)} &= 4_{(10)} \\ 0101 &= 101_{(2)} &= 5_{(10)} \\ 0110 &= 110_{(2)} &= 6_{(10)} \\ 0111 &= 111_{(2)} &= 7_{(10)} \\ 1000 &= 1000_{(2)} &= 8_{(10)} \\ 1001 &= 1001_{(2)} &= 9_{(10)} \\ 1010 &= 1010_{(2)} &= 10_{(10)} \\ 1011 &= 1011_{(2)} &= 11_{(10)} \\ 1100 &= 1100_{(2)} &= 12_{(10)} \\ 1101 &= 1101_{(2)} &= 13_{(10)} \\ 1110 &= 1110_{(2)} &= 14_{(10)} \\ 1111 &= 1111_{(2)} &= 15_{(10)}\end{alignat}$

Rust や C# では、4bit ではなく 8bit, 16bit, 32bit, 64bit で表現した符号なし整数が用意されています。並べる bit の個数は違いますが、考え方は全く同じで、0 or 1 を並べたものをそのまま二進法の表記として解釈すればOKです。

符号付き整数

私たちが整数を取り扱うとき、マイナスの数を取り扱うこともあります。しかし、先ほど説明した方法だと 0 以上の数しか表現することができません。プラスとマイナスを含めた、いわゆる符号付き整数を取り扱うにはどうすればよいでしょうか？

答えはシンプルです。半分をマイナスの表記に割り当てるだけです。

4bit の場合で具体的に考えてみましょう。符号なし整数では以下のように対応していました。

$\begin{align}0000 &= 0_{(10)} \\ 0001 &= 1_{(10)} \\ 0010 &= 2_{(10)} \\ 0011 &= 3_{(10)} \\ 0100 &= 4_{(10)} \\ 0101 &= 5_{(10)} \\ 0110 &= 6_{(10)} \\ 0111 &= 7_{(10)} \\ 1000 &= 8_{(10)} \\ 1001 &= 9_{(10)} \\ 1010 &= 10_{(10)} \\ 1011 &= 11_{(10)} \\ 1100 &= 12_{(10)} \\ 1101 &= 13_{(10)} \\ 1110 &= 14_{(10)} \\ 1111 &= 15_{(10)}\end{align}$

これの後半をマイナスに割り当てます。

$\begin{align}0000 &= 0_{(10)} \\ 0001 &= 1_{(10)} \\ 0010 &= 2_{(10)} \\ 0011 &= 3_{(10)} \\ 0100 &= 4_{(10)} \\ 0101 &= 5_{(10)} \\ 0110 &= 6_{(10)} \\ 0111 &= 7_{(10)} \\ 1000 &= -8_{(10)} \\ 1001 &= -7_{(10)} \\ 1010 &= -6_{(10)} \\ 1011 &= -5_{(10)} \\ 1100 &= -4_{(10)} \\ 1101 &= -3_{(10)} \\ 1110 &= -2_{(10)} \\ 1111 &= -1_{(10)}\end{align}$ これで無事 -8 から 7 の整数を取り扱うことができるようになりました！*2

Rust や C# では、符号なし整数の場合と同様、4bit ではなく 8bit, 16bit, 32bit, 64bit で表現した整数が用意されています。こちらも表現できる数のうち後半にあたる部分を全部マイナスの数に割り当てればOKです。

ちなみに豆知識ですが、(一部例外はありますが) 符号を反転させることは、各 bit を一斉に反転させた後に、1を足す操作と一致します。試しに先ほどの一覧で、どれか好きな数を選んで、各 bit を反転させたものの一個下を見ると、元の数の符号違いになっていることを確認してみてください (-8 は例外です)。

(特殊な例) Python の int 場合

Python で整数を扱いたい場合は int 型が使われます。この型は特定の bit 数の設定がなく、(メモリがある限り) いくらでも大きい整数を取り扱えるようになっています。同時に負の数も取り扱うことができます。

試しに Python の REPL で 5 と -5 を表示してみると以下のようになります。

>>> bin(5)
'0b101'
>>> bin(-5)
'-0b101'

"0b" は「二進法ですよ」という意味です。5を二進法で表すと $101_{(2)}$ で、マイナスをつければ $-101_{(2)}$ なので、人間が書く二進法の表記を表示してくれていることがわかります。でもこれでは bit でどう表現されているのか分かりません。

実際に内部でどのように実装されているのかは分かりませんが、いくつか実験してみた結果、見かけ上は以下のように考えればよいようです。

まず 5 については、4bit で表したときの表記の左側に無限個の0を並べたものに対応します。

$\cdots 0000101 = 5_{(10)}$ 次に -5 については、4bit で表したときの表記の左側に無限個の1を並べたものに対応します。 $\cdots 1111011 = - 5_{(10)}$

一般のもっと大きな整数を表すには、次の手順を取ります*3。

$2^{n - 1}$ がその整数の絶対値よりも大きくなるような $n$ をひとつ取る (必ずあります)
$n$ bit での符号付き整数の対応を考えて、表したい整数の $n$ bit 表現を見つける (表現できる範囲が $- 2^{n - 1} \sim 2^{n - 1} - 1$ なので、必ずあります)
一番左側にある bit を左側に無限個並べる

この方法で導かれる表現が $n$ の取り方によらないことの証明は読者の演習問題とします。

この表記を使えば (0 の場合は無限の繰り上がりが発生することに目を瞑れば) どの整数に対しても「符号を入れ替える = 全 bit 反転して1を足す」が成り立つようになります。

(特殊な例) JavaScript の Number の場合

JavaScript では基本的に 64 bit 浮動小数点数型の Number で整数も含めてすべてを賄います*4。Number 型はこの記事で紹介したようなものとは全く別のビット表現を使っていると思われます。

一方 JavaScript にもビット演算が定義されており、ビット演算は浮動小数点数と相性が悪いため、以下のような振る舞いになるよう実装されているようです。

まず 32 bit 符号つき整数になるように丸める（どう丸めているかは未調査）
ビット演算を施す
64 bit 浮動小数点数型に再度変換する

64 bit 浮動小数点数で正確に表現できる整数の範囲は 32 bit 符号なし整数よりも広いので、Number 型を 32 bit 整数だと思い込んでビット演算する分には問題なさそうです。

まとめ

ビット演算を使った高速化を行う上では、整数をどのようにコンピュータが解釈しているのか知っておくのは不可欠です。不安になったときのリファレンスとして、この記事が役立てばいいなと思います。

ではまた。

*1:0 か 1 の二つの状態が取れるものが4つあるので $2^{4} = 16$ 通り。

*2:巷ではこのルールで割り当てることを「2の補数表現」と呼ぶそうです。

*3:「'-0b101' と表示されるんだから、符号を保存する bit と 101 の組み合わせで表現しているのではないのか？」と思った方もいたかもしれません。そうでないことは、5 >> 3 が 0 になるのに対して -5 >> 3 が -1 になることから確かめられます。

*4:JavaScript には BigInt 型という整数型もありますが、新しめの仕様のようで若干癖があるようです。BigInt 型は Python の int と同様、任意の桁数の整数を取り扱えるようです。