位取り記数法

出典: フリー百科事典『ウィキペディア（Wikipedia）』

位取り記数法（くらいどりきすうほう）は、数の表現方法の一種で、適当な自然数 N (> 1) を指定して N 種類の記号（数字）を用意し、それを列べることによって数を表すための規則である。

位取り記数法で指定された自然数 N をこの記数法の基数といい、基数が N であるような位取り記数法を「N 進法」「N 進記数法」という。N 進法では、N 種類の数字からなる記号列において、隣り合う上位の桁に下位の桁の N 倍の意味を持たせる位取りによって数を表現する。

数を N 進法で表記することを「N 進表記」という。また、N 進表記された数という意味で「N 進数」という呼称を使用することもある。

関連が深い概念として、素数 p 毎に定まる p 進数というものもある。両者は別概念ではあるが非常に関連があり、整数のp進表記を（可算）無限桁の自然数の範囲に拡張したものがp進整数で、さらにそこに有限桁の少数部分を許したものがp進数である。ただし「無限桁の整数」（の一部は有理数として再解釈できるもののほとんど）はこの項目で扱う普通の数（実数）とは異なる。

N 進法の表記において正負や小数を表現する場合には、符号や小数点が併用される。

日常的に最多用されている記数法は十進法である。又、時間は三百六十単位を基本にして、十二単位、三十単位、六十単位の組合せで表現され、場合によってはこれらの累乗数（十二進法、六十進法。三十進法は今の所使われていない）が用いられる。

概説

日常用いられている、十倍毎に位をとる数の表記法は十進法と呼ばれ、零から九までの十通りの数値については、それぞれ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 というように独自の文字（数字）が用意されている。そして 9 より一大きい十を一文字で表記せず、1 と 0 の二文字を組み合わせて 10 と桁を上げて表記することになる。

同様に、二文字の数字を使えば、00 から 99 まで百通り（十の平方）の数を表現することができる。99 より大きな数を表現するには、更にもう一文字（桁）増やして、100 と表記する。

このように、十種類の文字を列べて十通りの数を一桁で表し、百通りの数を二桁で、千通りの数を三桁で、というように十の N 乗通りの数を N 桁で表すのが十進法である。十進表記で記された数を十進数と呼ぶ流儀もある。

ここで、「十」という数を二に変えると二進法に、二十に変えると二十進法になる。例えば、二十進法では普通、0 から 9 までの数字十種類と、A から J までのアルファベット十種類、合わせて二十種類の文字を共に数字として扱い、数を表現する。例えば、十進法では 15 と二桁で表記される数も、二十進法では F と一文字で表記できる。

逆に、八進法では 0 から 7 までの八種類の文字を数字として扱い数を表現するので、十進法で 8 と書き表される数は、八進法では 10 と表され、二桁を必要とする。

自然数の表記

任意の自然数 T に対し、r を十分大きく取れば、

$T = c_0\cdot 1 + c_1N + c_2N^2 + \dots + c_rN^r$

を満たし、各 c_i は 0, 1, 2, 3, ..., N - 1 のいずれかであるような {c_i} を一意的に取ることができる。

実際、次のようにすれば {c_i} と r を求めることができる（基数変換アルゴリズム）。

T を N で割った商を T₁, 余りを c₀ とする。
T₁ を N で割った商を T₂, 余りを c₁ とする。
以下 T_i を N で割った商を T_i+1, 余りを c_i とする操作を繰り返す。
T_k = 0 となった時 r = k - 1 とする。

さて、このとき、0 から N - 1 までの自然数に何らかの記号（数字）を対応させておいて、 c_r, c_r-1, ..., c₁, c₀ に対応する記号を順に並べれば、任意の自然数 T を有限個の記号で表記できることになる。この表記のことを T の N 進表記 という。

なお、上記ではアルゴリズムが終了するまで r が幾つになるか分からないが、対数を用いれば

$\left\lfloor\log_N T\right\rfloor$

として事前に r を求めておくこともできる。ただし、

$\lfloor x\rfloor$

は x を超えない最大の整数である（床関数参照）。

また、このアルゴリズムを考えると N を自然数に限定する必要性はない。また、 {c_i} についても、任意の整数 a を取れば、 a, a+1, a+2, a+3, ..., a+N-1 でも構わない。（ただし、どれかが0でないと不便である。）

T = T 1 + N c 1

であるが、 T₁ が一意に決まれば a 及び N は何でも良いと考えられる。ただし、 N が整数でない場合は各 {c_i} の個数について吟味が必要である。例えば、虚数単位を j とすると、 N=-1+j の場合は整数のみで構成される複素数 x+yj （ただしx,y は整数）は p+qj （p,q は整数）を用いて、

${x + yj - c_1 \over -1 + j} = p + qj$

と表せられる。分母分子に -1 - j をかけると、

${-x + y + c_1 \over 2} = p$

${-x - y + c_1 \over 2} = q$

という2つの式が得られるから、各 {c_i} の数は2でなければ T₁ が一意に決まらない。

二進表記	三進表記	六進表記	十進表記	十二進表記
1	1	1	1	1
10	2	2	2	2
11	10	3	3	3
100	11	4	4	4
101	12	5	5	5
110	20	10	6	6
111	21	11	7	7
1000	22	12	8	8
1001	100	13	9	9
1010	101	14	10	A
1011	102	15	11	B
1100	110	20	12	10

例

十進表記の 5213 を五進表記に置き換える場合：

5213 ÷ 5 = 1042 余り 3
1042 ÷ 5 = 208 余り 2
208 ÷ 5 = 41 余り 3
41 ÷ 5 = 8 余り 1
8 ÷ 5 = 1 余り 3
1 ÷ 5 = 0 余り 1

より 5213 = 3 + 2 × 5 + 3 × 5² + 1 × 5³ + 3 × 5⁴ + 1 × 5⁵ となるので、五進表示では 131323 と表す事ができる。また、5⁵ = 3125, 5⁶ = 15625 から 5⁵ < 5213 < 5⁶ が成り立っているので、対数を用いれば

5 < log 5 5213 < 6

となり、

$r=\left\lfloor\log_{5}5213\right\rfloor =5$

が分かる。

二百七十の表記法は、以下のような意味となる。（便宜上、計算式を十進表記で記す）

二進表記（100001110）：270 = 256 + 14 = 2⁸ + 2³ + 2² + 2¹
六進表記（1130）：270 = 216 + 54 = 6³×1 + 6²×1 + 6¹×3
十進表記（270）：270 = 200 + 70 = 10²×2 + 10¹×7
十二進表記（1A6）：270 = 144 + 126 = 12²×1 + 12¹×10 + 6
二十進表記（DA）：270 = 260 ＋ 10 = 20¹×13 + 10

また、500 と表記される数は、十進表記では五百だが、十二進表記では七百二十を、二十進表記では二千を意味する。

これは、十二進表記では「五倍の百四十四（=十二の平方）」を意味し、二十進表記では「五倍の四百（=二十の平方）」を意味するからである。従って、十二進表記の“500 ÷ 26 = 20”は、十進表記では“720 ÷ 30 = 24”と直される。

整数の表記

T が負の数である場合には記号列の先頭に負符号 − を付けて、その後に絶対値 |T| の N 進表記を続けることにすれば、任意の整数を同様にして表記できる。

二進表記	三進表記	六進表記	十進表記	十二進表記
−110	−20	−10	−6	−6
−101	−12	−5	−5	−5
−100	−11	−4	−4	−4
−11	−10	−3	−3	−3
−10	−2	−2	−2	−2
−1	−1	−1	−1	−1
0	0	0	0	0

有理数・実数の表記

小数表現

任意の有理数・実数は

$a_l N^l + a_{l-1}N^{l-1} + \cdots + a_1 N + a_0 + {a_{-1}\over N} + {a_{-2}\over N^2} + \cdots$

（各位の a_i は 0 以上 N 未満の整数）の形に表される。これを N 進法では（0 以上 N 未満の整数にそれぞれ記号を与えて）

$a_la_{l-1}\ldots a_1a_0.a_{-1}a_{-2}\ldots$

と表記する。

	十進表記	十二進表記	二十進表記
1 ÷ 2	0.5	0.6	0.A
1 ÷ 3	0.3333…	0.4	0.6D6D…
1 ÷ 4	0.25	0.3	0.5
1 ÷ 5	0.2	0.2497…	0.4

例1

二進法で 0.111 と表される数は、零、二分の一、四分の一、八分の一を加えた数という意味で、例えば十進法などでは

$0 + 1 \times{1\over 2} + 1 \times{1\over 4} + 1 \times{1\over 8} = {7\over 8} = 0.875$

と表される。

例2

十進法で表された絶対値が1未満の小数をN進法に変えたい場合、次のようにすればよい。

Nを掛け、整数部と小数部に分ける。
その小数部にNを掛け、再度整数部と小数部に分ける。
小数部が0になるまで同様の操作を繰り返す。
整数部を上位から並べる。

例えば十進表記の0.8125を2進表記に置き換える場合、

0.8125×2=1.625=0.625+1
0.625×2=1.25=0.25+1
0.25×2=0.5=0.5+0
0.5×2=1.0=0.0+1

となるので、2進表記では0.1101と表される。

一進法

nを表記するとき1をn個並べる記法を一進記数法と呼ぶ。主に計算機科学で用いられる用語。たとえば10進数の4は一進数表記は「1111」。

この「一進記数法」という呼び方はあくまで便宜的なもので、上述のn進法でnを1にした場合とは異なる。

平衡三進法

3を基数とし、-1,0,1を三つの記号に対応させる記数法を平衡三進法（へいこうさんしんほう）と呼ぶ。符号を使わずに整数を表記できる、演算の過程で繰り上がる確率が低い、という特徴がある。

-1を $\bar{1}$ と書いて平衡三進表記と十進法との対応を下に示す。

十進表記	平衡三進表記
-9	$\bar{1}00$
-8	$\bar{1}01$
-7	$\bar{1}1\bar{1}$
-6	$\bar{1}10$
-5	$\bar{1}11$
-4	$\bar{1}\bar{1}$
-3	$\bar{1}0$
-2	$\bar{1}1$
-1	$\bar{1}$
0	$0$
1	$1$
2	$1\bar{1}$
3	$10$
4	$11$
5	$1\bar{1}\bar{1}$
6	$1\bar{1}0$
7	$1\bar{1}1$
8	$10\bar{1}$
9	$100$

符号つき二進展開

平衡三進法の類似物として符号つき二進展開がある。これは2を基数とし、-1,0,1を三つの記号に対応させる記数法の一つ。各整数はこのような表記方法を複数持つが、それらのうち隣接する二桁がともに非0にはならないものを符号つき二進展開（ふごうつきにしんてんかい）と呼ぶ。このような表記方法は各整数に対して一つあって一つに限る事が知られている。この表記方法は通常の二進展開に比べて0の桁が多いという利点がある。

より厳密な定義を述べる。数列 $a_ma_{m-1} \cdots a_1a_0$ が整数nの符号つき二進展開であるとは次の3性質を満たすときに言う。

$a_i \in \{0,1,-1\}$
$n = Σ i a i 2 i$
任意のiに対し、 $a i$ 、 $a i + 1$ の少なくとも一方は0。

符号つき二進展開の応用例として例えば、符号つき二進展開を使って楕円曲線上のスカラー倍算を効率的に計算する方法が知られている。

-1を $\bar{1}$ と書いて符号つき二進展開と十進法との対応を下に示す。

十進表記	符号つき二進展開
-9	$\bar{1}00\bar{1}$
-8	$\bar{1}000$
-7	$\bar{1}001$
-6	$\bar{1}010$
-5	$\bar{1}0\bar{1}$
-4	$\bar{1}00$
-3	$\bar{1}01$
-2	$\bar{1}0$
-1	$\bar{1}$
0	$0$
1	$1$
2	$10$
3	$10\bar{1}$
4	$100$
5	$101$
6	$10\bar{1}0$
7	$100\bar{1}$
8	$1000$
9	$1001$

Nが自然数でないもの

基本的にNは自然数であるが、自然数でないものも考えられている。コンピュータでは二進数を用いている場合がほとんどだが、符号の扱いが難しい。そこで、Nを-2とする-2進数が考えられた。この方法では、0と1を用いてすべての整数を表すことが出来る。ただし、演算（特に除算）が複雑になるため用いられることは極めて稀である。その他に虚数単位をiとして、-1+i進数等も考えられている。ただし、こちらも演算が複雑なため用いられることは極めて稀である。

十進表記	-2進表記
-10	1010
-9	1011
-8	1000
-7	1001
-6	1110
-5	1111
-4	1100
-3	1101
-2	10
-1	11
0	0
1	1
2	110
3	111
4	100
5	101

代表的な基数

参考文献

ヘンリー・S・ウォーレン、ジュニア『ハッカーのたのしみ』 ISBN 4434046683

"http://ja.wikipedia.org../../../%E4%BD%8D/%E5%8F%96/%E3%82%8A/%E4%BD%8D%E5%8F%96%E3%82%8A%E8%A8%98%E6%95%B0%E6%B3%95.html" より作成

カテゴリ: 半保護 | 数の表現 | 数学に関する記事