二進数と数値 基礎

このコースのどの層もバイトを運ぶ。curl https://api.example.com/user/42 はシェルを出た瞬間にバイト列になり、ハンドラがパスから取る整数も同じだ。 8 は自然法則ではない。IBM System/360 が 1964 年に決め、バイト単位の道具が固定した。

各位置は 2 の冪を持ち、値は立っているビットの冪の総和になる —— スライダを引いて、ビットが埋まり、2 つのニブルが綴る 16 進 2 桁が追随するのを見てほしい：

16 進の桁はビットと決して食い違わない。4 ビットがちょうど 16 進 1 桁だからだ。 16 = 2⁴ なので、変換で隠れるものが何もない。 10 進にはこの性質がない —— 255 はどのビットが立っているかを何も語らないが、0xff は 8 つすべてだと語る。

デバッガも 16 進エディタもパケットキャプチャも 10 進ではなく 16 進を出すのは、これが理由だ。16 進のバイトは常に 2 列。同じバイトの 10 進表記は 1 列にも 2 列にも 3 列にもなる。行に沿ってカーソルを引いてほしい：

10 進の行が格子を失うのを見てほしい。72、84、47 は揃わないので、14 番目のバイトを探すのはセルを数えることではなく文字を数えることになる。16 進の行は定規だ。 16 進を使う理由は組版上のものであり、そしてそれは十分に強い理由だ。

バイトは型を持たない。URL の中の文字 4 は数の 4 ではない —— ASCII がその字形に割り当てたバイトにすぎない。スライダが文字列を 1 文字ずつ歩く：

文字 4 は 52、つまり 0x34。整数の 4 は 0x04。この違いを忘れたパーサはどの桁でも 48 ずれる。atoi が '0' を引くのはまさにこのためだ。ここにある 7 バイトが、curl がパスの末尾として実際に書く列そのものになる。

ASCII は最上位ビットが 0 の 1 バイトで 128 個のコードポイントを覆う。 UTF-8 はそのバイトをビット単位でそのまま残し、バイトを余分に使うことで Unicode の残りを買う —— コードポイントを上げて、先頭バイトの後ろに継続バイトが現れるのを見てほしい：

ASCII 域が変わらないので、Web が UTF-8 に移っても ASCII 用のツールは 1 行も直さず生き延びた。0x7F より上では、先頭バイトの上位ビットが長さを宣言する —— 2 バイトなら 110、3 バイトなら 1110、 4 バイトなら 11110。だからデコーダに長さフィールドは要らない。

以上のどれもメモリには保存されない。バイトはどの取り決めかを示すタグを持たず、次に読む命令が決める。読み方を切り替えて、動かない 4 バイトが 4 つの無関係な答えを出すのを見てほしい：

バイトが一度も動いていないことに注目してほしい。42 28 00 00 はテキストの B( と NUL 2 個、リトルエンディアンの 10,306、ビッグエンディアンの 1,109,917,696、約 1.4×10⁻⁴¹ の float32 非正規数。型はコンパイラの約束で、ハードウェアは何も約束しない。

正の整数は自明で、面白いのは −42 の方だ。符号付き絶対値は最上位ビットを符号に与え、ゼロが 2 つと加算の 4 分岐を抱え込む。 1 の補数は全ビット反転で、巡回桁上げを必要とする。どちらも 1970 年代までに敗れた。

2 の補数は代わりに剰余の見方を取る。8 ビットが持つのは 256 を法とする剰余類だ。下の輪はその剰余類を 1 度だけ描く —— 回してみて、同じ位置が符号なしの読みと符号ありの読みを同時に持つのを見てほしい：

この輪の継ぎ目はちょうど 1 か所。時計回りに、符号なしの読みは 0 から 255 まで途切れずに数え、符号ありの読みは 0 から 127 まで数えたあと −128 に落ちる。下半分では一致し、上半分ではちょうど 256 ずれる。定義はこれで全部だ。

否定はここから落ちてくる。−x に x + (−x) ≡ 0 (mod 256) を満たしてほしいので、 −x は 256 − x になる。反転すると 255 − x になるので、 256 − x は「全ビット反転して 1 を足す」ことに等しい。スクラバを進めて、負の値が正の値から組み上がるのを見てほしい：

反転だけでは答えにならない。~42 は 213 で、42 + 213 は 255 ——折り返しに 1 足りない。その +1 が閉じる。ここに「負数専用回路」は 1 つもない。ALU がすでに持っている 2 つの操作を、代数が要求する順に並べただけだ。

つまり減算も回路ではない。加算器は 8 桁を足し、9 桁目を捨てる。 256 を法とすればそれは両方の読みにとって正しい答えになる —— 2 つのオペランドを動かして、桁上げがレジスタから出ていくのを見てほしい：

オペランドを 42 と −42 にすると、桁は 1 00000000 を作る。桁上げは捨てられ、レジスタにはゼロが残る。符号なしで読めば、同じ桁が 42 + 214 = 256 ≡ 0 と言っている。加算器は 1 つ、読みは 2 つ、データパスのどこにも符号による分岐はない。

その桁上げのうち 2 本には名前がある。ハードウェアは両方を残すからだ。最上位桁からの桁上げ出力 c₈ が桁上げフラグ CF、それと最上位桁への桁上げ入力 c₇ の排他的論理和がオーバーフローフラグ OF になる。同じ加算器を 127 の先へ進めて、どちらのランプが点くかを見てほしい：

CF = c₈ は符号なしの読みが入らなかったことを言い、OF = c₈ ⊕ c₇ は符号ありの読みが入らなかったことを言う。2 つは独立だ。100 + 100 は OF だけを立てる —— 200 はバイトには入るが、符号ありのバイトには入らない。−1 + 1 は CF だけを立てる —— 255 + 1 はバイトから出るが、符号ありの答え 0 は正しいままだ。−100 + −100 は両方を立てる。加算器が計算する和は 1 つで、フラグは 2 回付く。ADD のコストはどちらでも同じだ。この 2 つは、もともと必要な桁上げ連鎖にぶら下がった XOR ゲート 1 つでしかない。

区別が要る操作は 3 つ。いちばん見やすいのはシフトだ。動かす 8 桁は同じで、違うのは空いた上位セルに入るものだけ —— 符号の複製か、ゼロか。x を負にすると分かれる：

x ≥ 0 なら一致する。x = −100、k = 3 では算術が −13、論理が 19。x / 2^k は算術だけで、しかも −∞ へ丸めるので負の奇数では x >> 1 と x / 2 が食い違う。

持ち帰る不変条件。n ビットのレジスタが持つのは 2ⁿ を法とする剰余類で、符号ありと符号なしはその代表元 2 つの名前だ。加減乗は同じ命令、最上位ビットを符号として読むのは除算・比較・右シフトだけ —— 次に壊れる一覧そのものだ。

符号あり 8 ビットの範囲は −128 から +127。負が 128 個、正が 127 個、そしてゼロ。大きさ 128 に正の相棒はいないので、 C と C++ は abs(INT_MIN) を未定義動作にした。

反転して 1 を足す操作は 256 個のパターンの置換であり、この置換には不動点がある —— x を軸に沿って歩かせ、その負の値が動かなくなる場所を探してほしい：

−128 では反転が 01111111 を与え、+1 の桁上げが 10000000 まで戻ってくる。出発点そのものだ。abs は負の数を返し、何も報告しない。その下流にあるもの —— 配列の添字、長さ、ループの上限 —— は、起こらないと仮定して書かれた負の数を受け取ることになる。

上方向のあふれは同じ失敗の、もう少し評判のよい版だ。int8 のアキュムレータに 16 を繰り返し足すと、 9 桁目が端から落ちた瞬間に収まっている値が折り返した値になる：

8 回の加算で和は 128 になり、レジスタは −128 と読み、何も異議を唱えない。ハードウェアが黙っているのではない。加算器は折り返すと同時に OF を立てる。§02 のとおりだ —— 捨てるのは言語の側だ。 C にはステータスビットを読む式がなく、規格は符号ありのあふれを未定義動作と呼ぶ。だからコンパイラは i + 1 > i を仮定してベクトル化できる。 Rust の checked_add は同じ ADD にフラグ分岐を足しただけで、検査は予測しやすい分岐であって余分な加算ではない。

最も引用される事例は平均だ。lo + hi が 2³¹ − 1 を超えた瞬間に (lo + hi) / 2 はあふれる。下の軸は符号あり 32 ビット整数の全幅そのものだ ——hi を右へ引いてほしい：

素朴な中点がゼロを越えて負の側に着地するのを見てほしい。そのとき 2 つの添字はどちらもごく普通の値のままだ。lo + (hi − lo) / 2 は区間から出ない。大きな和をそもそも作らないからだ。Joshua Bloch は 2006 年に、出荷から 9 年後の JDK 自身の二分探索の中でこれを見つけた。

時刻も整数だ。Unix の time_t は 1970-01-01 からの符号あり 32 ビットの秒数で、下の軸はその秒数をピクセルに比例させたものだ —— 時計を前へ引いてほしい：

それが名指しできる最後の 1 秒は 2038-01-19 03:14:07 UTC。その 1 秒後、カウンタは −2,147,483,648 と読み、同じコードが 1901-12-13 と表示する。いまも 32 ビットの time_t を格納する列、ログ形式、回線上のフィールドが、その日付を抱えている。

最後の罠にあふれは要らない。C の通常の算術変換は、比較で符号ありと符号なしが出会うと符号あり側を符号なしに昇格させる。だから比較はあなたが選んでいない軸の上で起きる —— x をゼロより下へ動かしてほしい：

int x = −1; if (x < 1u) は偽だ。x が図の軸そのもの、4,294,967,295 になる。size_t なら昇格先はその型の幅で、LP64 では 18,446,744,073,709,551,615 として比較される。幅は変わるが裏返りは変わらない。コンパイラは暗黙の変換を見逃し、コードはきれいに通って出荷される。

float32 はワードを 1 + 8 + 23 に、float64 は 1 + 11 + 52 に分ける。どちらも同じ 1 文を意味する。値 = (−1)^s × 1.m × 2^{e − バイアス}、バイアスはそれぞれ 127 と 1023 だ。

3 つのフィールドはこの順に、隙間なく並んでいる。そしてこの順番は偶然ではない —— ビット番号をワード全体に走らせて、各ビットがどのフィールドに属するかを見てほしい：

指数が仮数の上に置かれていることに注目してほしい。符号ビットを無視すれば、 2 つの正の浮動小数点数の大小関係は、そのビットパターンを符号なし整数として読んだときの順序と一致する。だから整数の比較器が両方を賄える —— 1985 年にはシリコンの都合、いまも浮動小数点配列を基数ソートできる理由だ。

1.m の先頭の 1 は格納されない。正規数は定義上必ずそれを持つので、規格はそのビットを回収し、1 桁ぶんただで手に入れる ——指数と仮数から値を組み立て、ステージの下端にある式を読んでほしい：

格納される 23 ビットの仮数は 24 ビットの有効数字、およそ 10 進 7.2 桁を買う。float64 の 52 ビットは 53 ビット、およそ 15.9 桁を買う。この数 —— 53 ビット —— こそ持ち帰るべきものだ。次のセクションの結果はすべてここから落ちてくる。

指数は符号付きフィールドとしてではなくバイアス付きで格納される。下の 2 本の軸は目盛りの間隔を共有しているので、そのずらしがただのずらしとして見える：

格納形式がただの符号なしバイトなので、指数が大きければビットパターンも大きく、順序を壊す符号付き絶対値のような不連続が真ん中に入らない。代償は 2 つの予約コードだ。0 と 255 はどの 2 の冪も表さない。

その 2 つのコードこそ、数体系の残りが住んでいる場所だ。 5 つの符号化を切り替えて、予約された指数が範囲の両端を占めるのを見てほしい：

噛みつくのは NaN だ。NaN == NaN は規格に従うどの言語でも偽で、だから x != x が移植性のある判定になり、だからソートの比較器に NaN が 1 つ混じると配列が整列しないままになる —— 比較器が厳密弱順序でなくなるからだ。非正規数はゼロと最小の正規数の間の隙間を埋めるが、タダではない。Sandy Bridge 世代の Intel コアでは非正規のオペランドや結果がマイクロコード支援に落ち、Agner Fog の実測でおよそ 150 クロックかかる。通常の mulps のレイテンシは 5 サイクルだ。 Skylake 以降は多くの場合でその代償を取り除いたが、全部ではない —— だからオーディオや DSP のコードは今も FTZ と DAZ を立て、非正規数をゼロに潰す方の代金を払う。

この仕組み全体が買っているのは到達範囲だ。float32 と int32 を 1 本の対数軸に載せて、引いてみてほしい：

どちらも 32 ビットだ。int32 は 2.1×10⁹ まで届き、その下のすべての整数が厳密になる。float32 は 10³⁸ でもまだ値を持てるが、その途中の値はほとんど厳密ではない。取引はこれで全部だ。同じ予算を、分解能ではなく到達範囲に使ったということ。

その予算は数えておく価値がある。それがこの節の全部だからだ。 32 ビットが名指せるのは 2³² ≈ 4.29×10⁹ 個の値で、呼び方をどう変えてもそれ以上にはならない。int32 は予算を 1 本の連続区間に全部使うので、値の間隔はどこでも 1 だ。float32 はそのうち 2²³ 個を、254 個ある正規の 2 進区間のそれぞれの内側に使う —— 区間をたどって、 2 つの個数が交わる場所を見てほしい：

float32 の個数は平ら、int32 は 1 段ごとに倍になるので、出会うのは 1 か所だ。2²³ —— どちらも 8,388,608 個、間隔はどちらも 1。1 つ上の2²⁴ では値は 840 万個のまま区間だけ倍になり、間隔は 2、奇数は消える。 §07 の梯子はこれを数えただけだ。到達範囲の代金は分解能から取られる。

10 分の 1 は 2 進で 0.000110011001100… と無限に繰り返す。 10 進で 3 分の 1 が 0.333… になるのと同じことだ。有効数字 53 ビットの形式はそのうち 53 桁を残し、残りを入口で一度だけ丸めて捨てる。

小数を選び、その 2 進の桁を 1 つずつ足していってほしい。下のバーはまだ足りない分で、 1 桁ごとに半分になるので対数目盛りで描いてある：

0.5、0.25、0.75 は終わる。分母が 2 の冪だからだ。 0.1 は 24 桁 でもまだ足りず、 53 桁でも足りない —— 格納される double は 0.1000000000000000055511151231257827 で、5.55×10⁻¹⁸ だけ高い。

その丸めが 2 回、さらにもう 1 回。それがこの分野で最も有名な 1 行を作る。 1 歩ずつ進めて、各バーが書かれたときの 10 進数からどれだけ離れているかを見てほしい：

格納された 0.1 は高く、格納された 0.2 も高い。その厳密な和は 10 分の 3 より 1.67×10⁻¹⁷ 高く、その和を double に丸めると 4.44×10⁻¹⁷ 高いところまで押し上げられる。 0.3 に最も近い double は 1.11×10⁻¹⁷ 低い。両者はちょうど 1 ULP 離れて着地する。0.1 + 0.2 == 0.3 がどの IEEE-754 言語でも偽なのは、この理由であって、他の理由ではない。

この ULP は定数ではない。double はゼロの近くに密集し、離れるほど広がり、2 の冪をまたぐたびに間隔が倍になる —— 曲線に沿って引いて、各桁でのすき間の広さを読んでほしい：

1 ではすき間は 2.22×10⁻¹⁶。10¹⁶ では 2 になる。この桁より上では隣り合う double の距離が隣り合う整数の距離より大きいので、そこにある整数のほとんどは double として存在すらしない。

この交差点には名前と厳密な値がある。2⁵³ 未満ならどの整数も double になる。そこから上では有効数字の桁が尽きる —— 指数を上げて、使われている仮数ビットが行の端に届くのを見てほしい：

2⁵³ = 9,007,199,254,740,992 で n + 1 === n が真になり、以後ずっと真のままだ。有効数字にその 1 を置くビットがもう残っていないからだ。 JavaScript はすべての数を double で持つので、それはちょうど Number.MAX_SAFE_INTEGER + 1 にあたる —— BigInt が言語に追加された理由であり、64 ビット id を JSON の数値で返す API が格納したものと違う id を返してしまう理由でもある。

最後の代償は蓄積だ。加算のたびに丸めが起き、ループの中のその誤差は打ち消し合わない —— 1 セントを 1000 回足して、累積誤差がさまよう様子を見てほしい：

この誤差は単調でも、1 回の丸めで抑えられてもいない。 0.01 を 1000 回足すと 10 より 1.69×10⁻¹³ 少ない。ダッシュボードでは無、台帳では突合不能 —— だから金額は最小単位の整数か decimal 型で持つ。

リトルエンディアンは最下位バイトを最も低いアドレスに置く。x86、x86-64、既定設定の ARM、Apple Silicon、RISC-V がこれだ。ビッグエンディアンはそこに最上位バイトを置く。PowerPC、SPARC、 IBM メインフレーム —— そしてすべての標準ネットワークプロトコルがこれだ。

0x12345678 を連続する 4 アドレスに書き、バイト順を切り替えて、最下位バイトと最上位バイトがどこに着地するかを見てほしい：

変わったのはアドレスだけで、値は変わっていないことに注目してほしい。 CPU は自分のメモリを読むかぎりバイト順を一切見ない —— バイト順はマシンの外からしか見えず、16 進ダンプもパケットキャプチャもディスク上のファイルも、まさにその外側に立っている。

リトルエンディアンには 1 つ具体的な言い分がある。値を狭めるのがタダなのだ。下位バイトがもともと先頭にあるからだ。同じアドレスを 1 バイト、2 バイト、4 バイトで読んでみてほしい：

リトルエンディアン配置のアドレスを 1 バイト読むと 0x78 が得られる。これは値の 256 を法とする剰余、つまりタダの切り詰めだ。同じ読み取りをビッグエンディアン配置で行うと 0x12 になり、これは何かの切り詰めではない。狭めるには元の幅を知ってオフセットを足す必要がある。多倍長加算の桁上げが下から上へ流れるのも同じ理由だ。

ビッグエンディアンの言い分は「先に来た」ことだ。ARPANET のホストはほとんどがビッグエンディアンだったので、IP・TCP・UDP・DNS はそれをヘッダに凍結し、あらゆるマルチバイトのフィールドはいまもその形で流れている：

ntohs と ntohl がその入れ替えだ。ビッグエンディアンのホストでは何にもコンパイルされず、x86 では 1 命令、レイテンシ 1 サイクルの bswap になる。 TCP の固定ヘッダは 20 バイトで、そのうち18 バイトがマルチバイト整数だ —— ポート 2 つ、32 ビットの番号 2 つ、ウィンドウ、チェックサム、緊急ポインタ。カーネルは双方向のすべてのセグメントでそのすべてを入れ替える。残る 19、20 バイト目はデータオフセットとフラグビットで、 1 ワードとして読まれるが数ではない。

このセクションが存在する理由は、その壊れ方にある。リトルエンディアンの読み手にビッグエンディアンのバイトを読ませ、値を 1 つずつ辿ってほしい：

たいていの値は派手に壊れる。305,419,896 は 2,018,915,346 として届く。しかし 0x12121212 でも、ゼロでも、0x7f7f7f7f でも入れ替えは見えず、両方の読みが一致する。だからバイト順のバグは小さいか回文的なフィクスチャを素通りし、本番の最初の実データで落ちる。 PNG も ELF も TIFF も WAV も、自分のバイト順を仕様に書いている。

幅が答える問いは「どれだけ大きいか」ではなく嘘をつかずにどれだけ大きいかだ。整数型は届く範囲がそのまま厳密で、浮動小数点型ははるかに遠くまで届く。その 2 つの数の差こそ、バグが住む場所だ。

下の梯子は各幅が厳密に持てる最大の整数の対数になっている —— 幅をそこで上へ歩かせ、右端で届く範囲を読んでほしい：

float32 がどこに落ちるかに注目してほしい。厳密に持てる整数は 2²⁴ = 16,777,216 まで、int32 より下だ。届く範囲は 10²⁹ 倍遠いのに、整数としては 128 倍劣る。

4 行がこのページをすべて生む。前半が abs(INT_MIN) と折り返しを、後半が 0.1 + 0.2 と MAX_SAFE_INTEGER を生む：

n bits hold a residue mod 2^n
bit n-1 set: signed = unsigned-2^n
float = (-1)^s x 1.m x 2^(e-bias)
exact ints: 2^24 f32, 2^53 f64

この梯子は走らせられるテストでもある。言い方は全編で 1 つに揃える。ある幅は、その下のすべての整数を名指せなくなる最初の 2 の冪で厳密な範囲から出る。桁を横へドラッグすると、float32 は 2²⁵ で出る —— 24 ビットの仮数が届く 2²⁴ の 1 つ上だ —— 同じ 32 ビットの int32 は 2³¹で出る：

float32 が int32 より 2 の冪 6 つ分早く色を変えるのを見てほしい。バーの先に伸びる短い部分が、その幅がいま嘘をついている距離で、尺はバーと同じ log₂ だ。 2⁵⁴ で float64、2⁶³ で int64 が加わり、 2⁶⁴ では厳密なものが 1 つも残らない。

• 浮動小数点への ==。 2 回の丸めが一致したかを聞いている。桁に合わせた許容差か ULP で比べること。
• 外から来た値への abs(x)。 INT_MIN で未定義であり、例外ではなく負の数を返す。先に広げること。
• 符号ありの値と size_t の比較。 i < v.size() は符号ありの i を昇格させ、負のカウンタはその符号なし型の最大値として比較される —— 32 ビットの unsigned なら 40 億、LP64 の size_t なら 1.8×10¹⁹ だ。
• 金額を double に入れること。 最小単位の整数で持つこと。ループ内の誤差は蓄積する。
• マルチバイトの struct へ直接 fread すること。 バイト順が違うと成功したうえででたらめを返す。

どれも珍奇ではない。警告なく通り、例外を投げず、数を返す。