二進数

二進数は 2 を基数とする位取りで整数を表す。符号なし 8 ビット語の重みは左から 128、64、32、16、8、4、2、1 で、0–255 を表せる。

各桁に 0 と 1 しかない走行距離計を考えるとよい。下の桁が満杯なら 0 に戻して左へ繰り上げる。最上位も満杯なら、桁上がりを受ける九つ目の桁はない。8 ビットだけを残すとゼロへ戻る。本課では 77 の表し方と、符号なし 8 ビットの折り返しで 255+1 が 0 になる理由を追う。

二進数の仕組み

重みは位置で決まる。右端を 0 とし、位置 k は 2^k。ビット 0 は 1、ビット 3 は 8、ビット 7 は 128 の重みを持つ。1 の列の重みを加え、0 の列は加えない。

01001101 はビット 0、2、3、6 が 1 なので、1+4+8+64=77 となる。

数をビットへ変えるには奇偶で最下位を取り出す。ビット 0 以外の重みはすべて偶数なので、n % 2 が最下位ビットを与える。n // 2 でそのビットを捨て、残りを一位置右へずらす。n が 0 になるまで繰り返す。余りは下位から出るため、紙の左から右への表記順とは逆になる。

1 を足すとき、最下位が 0 なら 1 にして終える。1 なら 0 に戻し、左へ桁上がりを送る。連続する 1 を消し、最初の 0 に到達して止まる。01111111 + 1 は 8 ビットを書き換えるが、01110000 + 1 は 1 ビットだけだ。

ステップ実行

既定値 n = 77 を 8 ビットへ変える。全ビットを 0 で初期化し、右から埋める。

1. 77 % 2 = 1 なのでビット 0 は 1。77 // 2 = 38。
2. 38 % 2 = 0 なのでビット 1 は 0。38 // 2 = 19。
3. 19 は奇数なのでビット 2 は 1、商は 9。
4. 9 は奇数なのでビット 3 は 1、商は 4。
5. 4 は偶数なのでビット 4 は 0、商は 2。
6. 2 は偶数なのでビット 5 は 0、商は 1。
7. 1 は奇数なのでビット 6 は 1、商は 0。ここで終える。

ビット 7 は訪問しておらず、初期値 0 が残る。結果 01001101 を読み戻せば 64+8+4+1=77 となる。

Decode に切り替えると逆の手順を追う。ビット 0 で 1 を加え、1 では加えず、2 で 4、3 で 8 を加える。4、5 は 0、6 で 64 を加え、7 は 0。最終値は 77 で、二つの変換を相互確認できる。

Count は 13（00001101）から 4 回増やす。

• 13→14：ビット 0 を消し、桁上がりをビット 1 へ置く。00001110、変更は 2 ビット。
• 14→15：最下位を 1 にし、00001111。変更は 1 ビット。
• 15→16：ビット 0–3 を消し、ビット 4 を立てる。00010000、変更は 5 ビット。
• 16→17：最下位だけを 1 にする。

セルが語を表し、上のラベルが重み、下のカーソルが現在の読み書き位置を示す。台帳には除算、重みの加算、インクリメントが記録され、計算とビットを照合できる。

8 ビットが 255 で終わる理由

8 個の位置に二つずつ選択肢があり、パターン数は 2⁸=256。0 から数えた 256 個の値の最後は 255 だ。11111111 は 128+64+32+16+8+4+2+1=255 で、256 に 1 足りない。

ここへ 1 を加えると全桁が 0 になり、キャリーはビット 7 の外へ出る。九つ目の桁がないので捨て、00000000 を残す。Odometer wrap は 253 から 254、255 と進み、ゼロへの折り返しでデモを終える。語自体はその後も数えられる。

固定幅の符号なし折り返しは、カウンターのリセット、時刻の巻き戻り、レベル値の異常などにつながる。幅を広げても境界は移るだけだ。折り返しが許されなければ増加前に上限を確認するか、検査付き演算を使う。下位ビットだけでは失ったキャリーを報告しないが、ハードウェアのフラグや検査 API は検出できる。

計算量

W ビットの変換は最大 W ビットを訪ねるので O(W)。固定の 8 ビットなら定数上限となる。インクリメントはキャリーが全ビットを通ると最悪 O(W)。全 256 開始パターンで平均すると、反転数は一回あたり 2 ビット弱だ。

境界ケース

• n = 0 は変換ループへ入らず、初期値 00000000 を保つ。
• n = 255 は除算 8 回で全位置を書く。
• 2 のべき乗は 1 が一つだけ。64 は 2⁶ なのでビット 6 だけが立つ。
• 00000000 のデコードはエラーではなく 0。
• 255 を越えた 8 ビットカウントは 0 に戻り、パターン自体には警告がない。

よくある間違い

• 余りの生成順に左から書く。低位が先に出るが、表記の左は高位だ。01001101 を反転した 10110010 は 77 ではなく 178。
• 先頭のゼロも計算したと思う。77 の除算は 7 回で、ビット 7 は初期値だ。文字列を構築する実装なら幅までゼロ埋めする。
• 左端をビット 0 と数える。左はビット 7、右が 0。
• この 8 ビット語に 256 を保存できると思う。数学的な和は 256 でも、下位 8 ビットは 0。
• 反転数を数値の増分と混同する。15→16 は 5 ビット、14→15 は 1 ビットを変えるが、どちらも数学的には 1 増える。境界の折り返しは法 256 で読む。

モデルの範囲

位取り、変換、キャリーを一列で追うため符号なし 8 ビットに固定する。実機には 16、32、64 ビットなどもあり、境界での言語動作は異なる。Python 整数は拡張され、固定幅では折り返さない。C の符号なし整数は型の幅で剰余を取り、Rust はデバッグ時に整数オーバーフローを検査して panic し得る。明示的な wrapping 演算で折り返しも指定できる。Rust のオーバーフロー規則を参照。C の符号付きオーバーフローは未定義動作だ。負数には追加の符号化規約が必要で、二の補数のレッスンで扱う。ここでのモデルは機械算術の全規則ではない。