数学汎典

§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 位取り表示の存在と一意性

定義 1.1.nnを22以上の整数とする。正整数NNの nn進表示 (base-n representation) とは、整数k≥0k\ge 0と整数a0,…,aka_0,\ldots,a_kによる表示

N=aknk+⋯+a1n+a0,0≤ai<n(0≤i≤k),ak≠0N=a_kn^k+\cdots+a_1n+a_0, \qquad 0\le a_i<n\quad(0\le i\le k),\qquad a_k\ne 0

である。nnを底、aia_iを各桁の数字といい、表示を(ak⋯a0)(n)(a_k\cdots a_0)_{(n)}と書く。桁数はk+1k+1である。00の表示は一桁の00とし、負整数の表示は、その絶対値の表示の前に負号を付ける。底が1010を超える場合には、1010以上の数字にもそれぞれ一つの記号を割り当てる。

定理 1.2.nnを22以上の整数とする。すべての整数は、ただ一通りのnn進表示をもつ。

証明. 正整数NNに対してq0=Nq_0=Nと置く。qi>0q_i>0である間、§A4.1 定理 2.1によって

qi=nqi+1+ai,0≤ai<nq_i=nq_{i+1}+a_i,\qquad 0\le a_i<n

を満たす商qi+1q_{i+1}と余りaia_iを取る。0≤qi+1≤qi/n<qi0\le q_{i+1}\le q_i/n<q_iであるから、正整数である商は各段階で減少し、有限回の操作の後にqk+1=0q_{k+1}=0となる。このときqk>0q_k>0であり、ak=qka_k=q_kなのでak≠0a_k\ne 0である。各等式を順に代入すると

N=a0+na1+⋯+nkakN=a_0+na_1+\cdots+n^ka_k

を得る。

任意のnn進表示において、最下位の数字はNNをnnで割った余りに等しく、残りの桁が表す数はその商に等しい。除法の原理により、余りと商はただ一通りに定まる。商について同じ操作を繰り返すと、すべての数字が一致する。一方の表示だけに桁が残ることは、先頭の数字が00でない正整数の表示が00を表すことになるため、起こらない。したがって桁数も一致する。00と負整数については、定義した表示の規約から存在と一意性が従う。▨

2 10進から2進への変換

正整数を底で割り、商をさらに同じ底で割る操作によって、最下位の桁から順に数字が求まります。

例 2.1.1313を2進法で表すために、22で割る操作を繰り返す。

  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)}となる。

各桁に対応するべきを掛けて足すと、10進表示に戻る。

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

3 2進法の四則計算

公式 3.1.nnを22以上の整数、j,sj,sを00以上の整数とする。位njn^jの係数ssをnnで割った商をqq、余りをrrとすると、s=qn+rs=qn+r、0≤r<n0\le r<nであり、

snj=qnj+1+rnjsn^j=qn^{j+1}+rn^j

と書き換える。位njn^jにはrrを残し、次の位へqqを加える。逆に、一つ上の位の11を下の位のnnに書き換えても、表す数は変わらない。

例 3.2. 以下の数字列はすべて2進表示とする。

1011+11011011+1101を計算する。一の位の1+11+1は1010なので、一の位に00を置き、次の位に11を加える。次の位も1+0+1=101+0+1=10、その次の位も0+1+1=100+1+1=10となる。最上位では1+1+1=111+1+1=11となるので、答えは1100011000である。

例 3.3. 以下の数字列はすべて2進表示とする。

11010−101111010-1011を計算する。桁をそろえるために、引く数の左に00を添えて0101101011と書く。一の位の00から11を引くために、二の位の11を一の位の1010に書き換える。一の位の差は11となる。二の位は00になっているので、八の位から四の位を経て借り入れる。二の位の差は10−1=110-1=1、四の位の差は1−0=11-0=1となる。八の位では十六の位から借り入れて10−1=110-1=1となり、答えは11111111である。

例 3.4. 以下の数字列はすべて2進表示とする。

分配法則により、1011×1011011\times101は、10111011と二桁左へ移した101100101100の和である。したがって

1011×101=1011+101100=1101111011\times101=1011+101100=110111

となる。

例 3.5. 以下の数字列はすべて2進表示とする。

111010111010を101101で割る。101000101000を引くと1001010010が残り、そこから10101010を引くと10001000が残り、さらに101101を引くと1111が残る。引いた数はそれぞれ101×1000101\times1000、101×10101\times10、101×1101\times1なので、商は1000+10+1=10111000+10+1=1011、余りは1111である。

111010=101×1011+11,0≤11<101111010=101\times1011+11,\qquad 0\le11<101

であるから、商と余りは除法の条件を満たす。

4 桁数と数の大きさ

系 4.1.nnを22以上の整数、N,kN,kを正整数とする。NNのnn進表示がちょうどkk桁であるための必要十分条件は

nk−1≤N<nkn^{k-1}\le N<n^k

である。

証明.NNのnn進表示の桁数をjjとする。先頭の数字は11以上であり、すべての数字はn−1n-1以下であるから、

nj−1≤N≤(n−1)(1+n+⋯+nj−1)=nj−1<njn^{j-1}\le N\le(n-1)(1+n+\cdots+n^{j-1})=n^j-1<n^j

が成り立つ。和の等式は(n−1)ni=ni+1−ni(n-1)n^i=n^{i+1}-n^iをi=0,…,j−1i=0,\ldots,j-1について足すことで得られる。したがってj=kj=kならば、求める不等式が成り立つ。逆にnk−1≤N<nkn^{k-1}\le N<n^kを仮定する。j<kj<kならばN<nj≤nk−1N<n^j\le n^{k-1}となり、j>kj>kならばN≥nj−1≥nkN\ge n^{j-1}\ge n^kとなる。どちらも仮定に反するので、j=kj=kである。▨

例 4.2.29=512≤1000<1024=2102^9=512\le1000<1024=2^{10}なので、系 4.1により、10001000の2進表示は1010桁である。

5 コンピュータと2進・16進、小数の表示

コンピュータでは、二つの状態を区別する2進法が広く用いられます。 2進表示を人が読む場合には、4桁ずつまとめて1桁にする16進法が用いられます。 16進法では、00〜99に加えてAA〜FFを使います。 4桁の2進表示が表す数は00以上1515以下なので、16進法の一桁に対応します。色コードやメモリアドレスにも16進法が使われます。

注意 5.1. 小数の位には、底の負の指数のべきを用いる。10進法の0.10.1は、2進法では

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

と循環する。小数点以下mm桁までの有限2進表示なら、2m2^mを掛けると整数になる。しかし2m/102^m/10はどの非負整数mmに対しても整数でないので、1/101/10は有限2進表示をもたない。 10進法で1/3=0.333…1/3=0.333\ldotsが循環するのと同じく、底を変えると、有限桁で表すことができない分数も変わる。

0.10.1を有限の2進表示で保存する場合には近似値を使います。浮動小数点では、数を限られた桁数で保存するため、入力値の近似や演算時の丸めによる誤差が生じます。0.10.1の加算結果を調べる場合にも、保存される近似値と丸めの方式を区別する必要があります。

閑話休題：底と表示の費用 底bbにおける正整数NNの桁数をkkとし、記号の種類と桁数の積bkbkを費用とする。桁数をlog⁡bN\log_b Nで近似すると、費用はblog⁡bNb\log_b Nとなる。この連続近似では底e≈2.718e\approx2.718が最小値を与え、整数の底では33が最小値を与える。一方、実際の桁数は整数であるため、特定のNNについて底33が費用を最小にするとは限らない。実際、15=1111(2)=120(3)15=1111_{(2)}=120_{(3)}では、底22の費用は2×4=82\times4=8、底33の費用は3×3=93\times3=9である。記号の種類と桁数の積は radix economy と呼ばれる指標であり、計算機の素子の製造費用や演算時間を直接表すものではない。

1958年、モスクワ大学で開発されたコンピュータ「セトゥン」（Setun）は、−1,0,1-1,0,1の三つの数字を使うバランス3進法で動く実機であった。少数が製造され、教育機関などで使われた記録も残っている。一方、計算機では2進法が広く使われるようになった。二つの状態を区別する素子と三つ以上の状態を区別する素子では、安定性や製造の条件が異なるため、表示の費用だけで計算機に用いる底が決まるわけではない。

例題

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

次の問いに答えよ。添字の (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 で書く）。

演習を読み込み中…

前提記事