§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進法が広く使われるようになりました。二つの状態を区別する素子と三つ以上の状態を区別する素子の間で、安定性や製造の条件が異なるため、表示の費用だけで計算機に用いる底が決まるわけではありません。

6 例題

レベル1 — n 進法

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

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

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

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

答22

注意 8 進法で末尾に 0 が k 個以上並ぶ⇔\Leftrightarrowその数が 8^k で割り切れる（最下位から k 桁が 0⇔\Leftrightarrow8^k の倍数）。したがって「ちょうど k 個」は「8^k で割り切れて 8^(k+1) では割り切れない」ことと同値。448==7×8² で 7 は 8 で割り切れないから、448 を割り切る 8 のべきの最大は 8²、すなわち答えは 2。実際 448 を 8 進法で書くと 700 で、末尾に 0 が 2 個並ぶ。

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

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

答320320

注意 各桁に 5 のべきを掛けて足す: 2×5³ + 2×5² + 4×5¹ +0×50=0\times5^{0} =250 + 50 + 20 + 0==320。検算は逆向きの変換（320 を 5 で割り続ける）で行うとよい。

例 6.3. 3458 を 8 進法で表せ。

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

答6602(8)6602_{(8)}

注意 8 で割った余りを下の桁から並べる: 3458 ÷ 8==432 余り 2、432 ÷ 8==54 余り 0、54 ÷ 8==6 余り 6、6 ÷ 8==0 余り 6。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 6602。

例 6.4. 21 を 2 進法で表せ。

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

答10101(2)10101_{(2)}

注意 2 で割った余りを下の桁から並べる: 21 ÷ 2==10 余り 1、10 ÷ 2==5 余り 0、5 ÷ 2==2 余り 1、2 ÷ 2==1 余り 0、1 ÷ 2==0 余り 1。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 10101。

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

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

答55

注意 2 進法で末尾に 0 が k 個以上並ぶ⇔\Leftrightarrowその数が 2^k で割り切れる（最下位から k 桁が 0⇔\Leftrightarrow2^k の倍数）。したがって「ちょうど k 個」は「2^k で割り切れて 2^(k+1) では割り切れない」ことと同値。160=5×25= 5\times2^{5}で 5 は 2 で割り切れないから、160 を割り切る 2 のべきの最大は252^{5}、すなわち答えは 5。実際 160 を 2 進法で書くと 10100000 で、末尾に 0 が 5 個並ぶ。

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

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

答261(8)261_{(8)}

注意 いったん10進に直すと 246 (8進)==166、13 (8進)==11 で和は 177。これを 8 進法に戻すと 261。桁ごとに足して 8 以上になったら上の桁へ 1 繰り上げる、と直接計算しても同じ答えになる。

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

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

答16011601

注意 各桁に 16 のべきを掛けて足す: 6×16² + 4×16¹ +1×160=1\times16^{0} =1536 + 64 + 1==1601。検算は逆向きの変換（1601 を 16 で割り続ける）で行うとよい。

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

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

答1000010(2)1000010_{(2)}

注意 いったん10進に直すと 111110 (2進)==62、100 (2進)==4 で和は 66。これを 2 進法に戻すと 1000010。桁ごとに足して 2 以上になったら上の桁へ 1 繰り上げる、と直接計算しても同じ答えになる。

例 6.9. 280 を 8 進法で表せ。

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

答430(8)430_{(8)}

注意 8 で割った余りを下の桁から並べる: 280 ÷ 8==35 余り 0、35 ÷ 8==4 余り 3、4 ÷ 8==0 余り 4。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 430。

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

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

答33

注意 8 進法で末尾に 0 が k 個以上並ぶ⇔\Leftrightarrowその数が 8^k で割り切れる（最下位から k 桁が 0⇔\Leftrightarrow8^k の倍数）。したがって「ちょうど k 個」は「8^k で割り切れて 8^(k+1) では割り切れない」ことと同値。5120==10×8³ で 10 は 8 で割り切れないから、5120 を割り切る 8 のべきの最大は 8³、すなわち答えは 3。実際 5120 を 8 進法で書くと 12000 で、末尾に 0 が 3 個並ぶ。

7 演習

レベル1 — n 進法

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

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

問題 7.1. 2 進法で 110010 と表される数を10進法で表せ。

110010(2)=?(10)110010_{(2)} = ?_{(10)}
解答.

答5050

注意 各桁に 2 のべきを掛けて足す:1×251\times2^{5}+1×241\times2^{4}+ 0×2³ + 0×2² + 1×2¹ +0×20=0\times2^{0} =32 + 16 + 0 + 0 + 2 + 0==50。検算は逆向きの変換（50 を 2 で割り続ける）で行うとよい。▨

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

N=875を 5 進法で表したときの末尾の 0 の個数N = 875 \quad \text{を } 5 \text{ 進法で表したときの末尾の } 0 \text{ の個数}
解答.

答33

注意 5 進法で末尾に 0 が k 個以上並ぶ⇔\Leftrightarrowその数が 5^k で割り切れる（最下位から k 桁が 0⇔\Leftrightarrow5^k の倍数）。したがって「ちょうど k 個」は「5^k で割り切れて 5^(k+1) では割り切れない」ことと同値。875==7×5³ で 7 は 5 で割り切れないから、875 を割り切る 5 のべきの最大は 5³、すなわち答えは 3。実際 875 を 5 進法で書くと 12000 で、末尾に 0 が 3 個並ぶ。▨

問題 7.3. 8 進法で表された 603 と 205 の和を、8 進法のまま表せ。

603(8)+205(8)=?(8)603_{(8)} + 205_{(8)} = ?_{(8)}
解答.

答1010(8)1010_{(8)}

注意 いったん10進に直すと 603 (8進)==387、205 (8進)==133 で和は 520。これを 8 進法に戻すと 1010。桁ごとに足して 8 以上になったら上の桁へ 1 繰り上げる、と直接計算しても同じ答えになる。▨

問題 7.4. 5 進法で 432 と表される数を10進法で表せ。

432(5)=?(10)432_{(5)} = ?_{(10)}
解答.

答117117

注意 各桁に 5 のべきを掛けて足す: 4×5² + 3×5¹ +2×50=2\times5^{0} =100 + 15 + 2==117。検算は逆向きの変換（117 を 5 で割り続ける）で行うとよい。▨

問題 7.5. 33 を 2 進法で表せ。

33(10)=?(2)33_{(10)} = ?_{(2)}
解答.

答100001(2)100001_{(2)}

注意 2 で割った余りを下の桁から並べる: 33 ÷ 2==16 余り 1、16 ÷ 2==8 余り 0、8 ÷ 2==4 余り 0、4 ÷ 2==2 余り 0、2 ÷ 2==1 余り 0、1 ÷ 2==0 余り 1。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 100001。▨

問題 7.6. 80 を 5 進法で表せ。

80(10)=?(5)80_{(10)} = ?_{(5)}
解答.

答310(5)310_{(5)}

注意 5 で割った余りを下の桁から並べる: 80 ÷ 5==16 余り 0、16 ÷ 5==3 余り 1、3 ÷ 5==0 余り 3。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 310。▨

問題 7.7. 3537 を 8 進法で表せ。

3537(10)=?(8)3537_{(10)} = ?_{(8)}
解答.

答6721(8)6721_{(8)}

注意 8 で割った余りを下の桁から並べる: 3537 ÷ 8==442 余り 1、442 ÷ 8==55 余り 2、55 ÷ 8==6 余り 7、6 ÷ 8==0 余り 6。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 6721。▨

問題 7.8. 1145 を 8 進法で表せ。

1145(10)=?(8)1145_{(10)} = ?_{(8)}
解答.

答2171(8)2171_{(8)}

注意 8 で割った余りを下の桁から並べる: 1145 ÷ 8==143 余り 1、143 ÷ 8==17 余り 7、17 ÷ 8==2 余り 1、2 ÷ 8==0 余り 2。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと 2171。▨

問題 7.9. 5 進法で表された 311 と 231 の和を、5 進法のまま表せ。

311(5)+231(5)=?(5)311_{(5)} + 231_{(5)} = ?_{(5)}
解答.

答1042(5)1042_{(5)}

注意 いったん10進に直すと 311 (5進)==81、231 (5進)==66 で和は 147。これを 5 進法に戻すと 1042。桁ごとに足して 5 以上になったら上の桁へ 1 繰り上げる、と直接計算しても同じ答えになる。▨

問題 7.10. 16 進法で表された 5A と 98 の和を、16 進法のまま表せ。

5A(16)+98(16)=?(16)5A_{(16)} + 98_{(16)} = ?_{(16)}
解答.

答F2(16)F2_{(16)}

注意 いったん10進に直すと 5A (16進)==90、98 (16進)==152 で和は 242。これを 16 進法に戻すと F2。桁ごとに足して 16 以上になったら上の桁へ 1 繰り上げる、と直接計算しても同じ答えになる。▨

問題 7.11. 8 進法で 5242 と表される数を10進法で表せ。

5242(8)=?(10)5242_{(8)} = ?_{(10)}
解答.

答27222722

注意 各桁に 8 のべきを掛けて足す: 5×8³ + 2×8² + 4×8¹ +2×80=2\times8^{0} =2560 + 128 + 32 + 2==2722。検算は逆向きの変換（2722 を 8 で割り続ける）で行うとよい。▨

問題 7.12. 3066 を 16 進法で表せ。

3066(10)=?(16)3066_{(10)} = ?_{(16)}
解答.

答BFA(16)BFA_{(16)}

注意 16 で割った余りを下の桁から並べる: 3066 ÷ 16==191 余り 10（A）、191 ÷ 16==11 余り 15（F）、11 ÷ 16==0 余り 11（B）。商が 0 になったら終了で、余りを逆順（下の桁から上の桁へ）に読むと BFA。16進法では 10〜15 を A〜F で表す。▨

問題 7.13. 96 を 16 進法で表したとき、末尾に並ぶ 0 の個数を求めよ。

N=96を 16 進法で表したときの末尾の 0 の個数N = 96 \quad \text{を } 16 \text{ 進法で表したときの末尾の } 0 \text{ の個数}
解答.

答11

注意 16 進法で末尾に 0 が k 個以上並ぶ⇔\Leftrightarrowその数が 16^k で割り切れる（最下位から k 桁が 0⇔\Leftrightarrow16^k の倍数）。したがって「ちょうど k 個」は「16^k で割り切れて 16^(k+1) では割り切れない」ことと同値。96==6×16 で 6 は 16 で割り切れないから、96 を割り切る 16 のべきの最大は 16、すなわち答えは 1。実際 96 を 16 進法で書くと 60 で、末尾に 0 が 1 個並ぶ。▨

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

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

答66

注意 2 進法で末尾に 0 が k 個以上並ぶ⇔\Leftrightarrowその数が 2^k で割り切れる（最下位から k 桁が 0⇔\Leftrightarrow2^k の倍数）。したがって「ちょうど k 個」は「2^k で割り切れて 2^(k+1) では割り切れない」ことと同値。192=3×26= 3\times2^{6}で 3 は 2 で割り切れないから、192 を割り切る 2 のべきの最大は262^{6}、すなわち答えは 6。実際 192 を 2 進法で書くと 11000000 で、末尾に 0 が 6 個並ぶ。▨

問題 7.15. 5 進法で表された 200 と 203 の和を、5 進法のまま表せ。

200(5)+203(5)=?(5)200_{(5)} + 203_{(5)} = ?_{(5)}
解答.

答403(5)403_{(5)}

注意 いったん10進に直すと 200 (5進)==50、203 (5進)==53 で和は 103。これを 5 進法に戻すと 403。桁ごとに足して 5 以上になったら上の桁へ 1 繰り上げる、と直接計算しても同じ答えになる。▨

前提記事