§A4.4記数法

最終更新

nn進法とは、数をnnのべきの和∑kaknk\displaystyle\sum_k a_k n^k（各係数は0≤ak<n0 \le a_k < n）で表す記法のことです（nnは22以上の整数）。 私たちが普段使う10進法はn=10n = 10の場合で、1010個の記号（00〜99）を使い、各桁が100,101,102,…10^0, 10^1, 10^2, \dotsの位を表しています。

1 表示の存在と一意性

nn進表示が必ず存在し、しかもただ一通りに定まることは、除法の原理（整数をnnで割ると商と余りがただ一組決まる、という事実）を繰り返し使うだけで分かります。数をnnで割って余りを最下位の桁として取り出し、商をまたnnで割って次の桁を取り出し……と続ければ、いつか商が00になって表示が完成し、しかも各段階の商と余りが一意なので、表示全体も一意に決まります。

2 10進から2進への変換

「nnで割って余りを並べる」のが変換の基本操作です。1313を2進法で表してみましょう。

  1. 13÷2=613 \div 2 = 6余り11
  2. 6÷2=36 \div 2 = 3余り00
  3. 3÷2=13 \div 2 = 1余り11
  4. 1÷2=01 \div 2 = 0余り11

商が00になったら終了です。余りを下の桁から順に並べるので、下から1,0,1,11, 0, 1, 1、つまり上から読むと13=1101(2)13 = 1101_{(2)}となります。

逆に2進から10進への変換は、各桁に対応するべきを掛けて足すだけです。

1101(2)=1×23+1×22+0×21+1×20=8+4+0+1=131101_{(2)} = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13

3 コンピュータと2進・16進、そして小数の落とし穴

コンピュータの中身が2進法（オン・オフの2状態）で動いていることはよく知られていますが、2進の桁は長くなりすぎて人間には読みにくいため、4桁ずつまとめて 1桁にできる16進法（00〜99に加えてAA〜FFを使う）が、色コードやメモリアドレスの表記としてよく使われます。

小数にも同じ考え方を拡張できます。0.10.1（10進）を2進法で表そうとすると

0.1(10)=0.0001100110011…(2)0.1_{(10)} = 0.0001100110011\ldots_{(2)}

のように無限に循環してしまい、有限桁では正確に表せません。コンピュータが0.10.1を何回も足しても厳密に0.30.3にならない、といった浮動小数点の誤差の根本原因はここにあります。10進で13\frac13が0.333…0.333\ldotsと循環するのと同じ現象が、底を変えると別の分数（この場合は110\frac{1}{10}）で起きているだけなのです。

閑話休題：もっとも経済的な底は3 コンピュータの底として2進法が使われていますが、「桁数」と「1桁あたりに必要な記号の種類」の積を最小にするという観点で見ると、実は最も無駄のない底は3だと言われています。ある数を底nnで表すのに必要な桁数はおおよそlog⁡n\log nに反比例し、 1桁に必要な区別（記号の種類）はnnに比例するので、コスト（桁数 × 底、 radix economyと呼ばれる指標）を最小にするnnを求めると、答えは自然対数の底e≈2.718e \approx 2.718になります。整数でこれに一番近いのは33なので、「もっとも経済的な整数の底は3進法」ということになるのです。

この理屈を本当に実装してしまった例があります。1958年、モスクワ大学で開発されたコンピュータ「セトゥン」（Setun）は、−1,0,1-1, 0, 1の3つの状態を使うバランス 3進法で動く実機でした。少数が製造され、教育機関などで使われた記録も残っています。それでも最終的に世界を制したのは2進法でした。理由は数学的な効率ではなく物理的な単純さです——電圧の「高い・低い」の2状態だけを安定して区別するスイッチ（トランジスタ）を作るほうが、3つ以上の状態を正確に区別する素子を大量生産するよりずっと簡単で壊れにくかったからです。理論上の最適解が、工学的な現実の前に譲歩した一例と言えるでしょう。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

次の問いに答えよ。添字の (n) はその数が n 進法で書かれていることを表す（16進法では 10〜15 を A〜F で書く）。

解法の型10進→n\to n進は「n で割って余りを下の桁から並べる」、n進→10\to10進は「各桁に n のべきを掛けて足す」

  1. 448 を 8 進法で表したとき、末尾に並ぶ 0 の個数を求めよ。

    N=448を 8 進法で表したときの末尾の 0 の個数N = 448 \quad \text{を } 8 \text{ 進法で表したときの末尾の } 0 \text{ の個数}

  2. 5 進法で 2240 と表される数を10進法で表せ。

    2240(5)=?(10)2240_{(5)} = ?_{(10)}

  3. 3458 を 8 進法で表せ。

    3458(10)=?(8)3458_{(10)} = ?_{(8)}

  4. 21 を 2 進法で表せ。

    21(10)=?(2)21_{(10)} = ?_{(2)}

  5. 160 を 2 進法で表したとき、末尾に並ぶ 0 の個数を求めよ。

    N=160を 2 進法で表したときの末尾の 0 の個数N = 160 \quad \text{を } 2 \text{ 進法で表したときの末尾の } 0 \text{ の個数}

  6. 8 進法で表された 246 と 13 の和を、8 進法のまま表せ。

    246(8)+13(8)=?(8)246_{(8)} + 13_{(8)} = ?_{(8)}

  7. 16 進法で 641 と表される数を10進法で表せ。

    641(16)=?(10)641_{(16)} = ?_{(10)}

  8. 2 進法で表された 111110 と 100 の和を、2 進法のまま表せ。

    111110(2)+100(2)=?(2)111110_{(2)} + 100_{(2)} = ?_{(2)}

  9. 280 を 8 進法で表せ。

    280(10)=?(8)280_{(10)} = ?_{(8)}

  10. 5120 を 8 進法で表したとき、末尾に並ぶ 0 の個数を求めよ。

    N=5120を 8 進法で表したときの末尾の 0 の個数N = 5120 \quad \text{を } 8 \text{ 進法で表したときの末尾の } 0 \text{ の個数}

演習

問題を解いてから「解答・解説」を開けます。

次の問いに答えよ。添字の (n) はその数が n 進法で書かれていることを表す（16進法では 10〜15 を A〜F で書く）。

演習を読み込み中…

前提記事