位取り記数法

「桁」はこの項目へ転送されています。横架材については「桁 (建築)」をご覧ください。

位取り記数法（くらいどりきすうほう）、もしくは「N 進法」とは数の表現方法の一種で、予め定められたN 種類の記号（数字）を列べることによって数を表す方法である。(位取りのことを桁ともいう。)

今日の日本において通常使われているのは、 N が十のケースである十進法であるが、コンピューターでは二進法、八進法、十六進法なども用いられる。また歴史的には、十進法が世界的に広まったのはフランス革命の革命政府がメートル法とともに十進法を定めて以来であり、それ以前は国や分野により、様々な N に対する N 進法が用いられていた。

本項ではN が自然数の場合を扱う。それ以外の場合については広義の記数法の記事を参照のこと。また後述するp進数の概念とは（関連があるものの）別概念であるので注意が必要である。

概要編集

「漢数字#位取り記数法」も参照

今日の日本において最も身近な十進法を例に説明する。十進法では、十個の数字と呼ばれる記号を用いる。

アラビア数字なら

0、1、2、3、4、5、6、7、8、9

の十個であり、漢数字なら

〇、一、二、三、四、五、六、七、八、九

の十個である^[1]。以下、アラビア数字を例に説明するが、漢数字の場合も同様である。

十進法ではこれらの数字を並べる事で数を表現する。例えば、253.48は、

2\times 10^{2}+5\times 10^{1}+3+4\times {\frac {1}{10^{1}}}+8\times {\frac {1}{10^{2}}}

を表す。

また十進法では、以下の性質が満たされる

10倍するごとに一桁増える
一桁で表せる数は10-1=9までで、10以降は二桁以上必要となる。

N 進法は、以上の十進法の説明を自然に N の場合に拡張する事で得られる。

例えば四進法をアラビア数字で表した場合、使うのは

0、1、2、3

の四種類の記号であり、四進法における312.02は、

3\times 4^{2}+1\times 4^{1}+2+0\times {\frac {1}{4^{1}}}+2\times {\frac {1}{4^{2}}}

を表し、これは十進法の54.125にあたる。

また四進法では、十進法に類似した以下の性質が満たされる

4倍するごとに一桁増える
一桁で表せる数は4-1=3までで、4以降は二桁以上必要となる。

以上の話でも分かるように、同じ「312.02」でも四進法のものと十進法のものでは値が異なる。このため、位取り記数法の話をするときには、常に何進法の話であるのかを明示する必要がある。

十六進数のように、N が十より大きい場合は用いる数字は十六個となるので、アラビア数字だけではたりなくなる。そこで十以上の数を表記する「数字」として、英語のアルファベットを用いる事が(特にコンピューターの分野では)多い。

例えば十六進法であれば、「数字」として

0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F

を用い、A、B、C、D、E、Fはそれぞれ自然数10、11、12、13、14、15を表す。

従って例えば2F3.A7は

2\times 16^{2}+15\times 16^{1}+3+10\times {\frac {1}{16^{1}}}+7\times {\frac {1}{16^{2}}}

を表し、これは十進法の755.652344にあたる。

例編集

二進表記	三進表記	六進表記	十進表記	十二進表記
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

二進表記	三進表記	六進表記	十進表記	十二進表記
−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

	十進表記	十二進表記	二十進表記
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

基数の明記編集

同じ「312.02」でも四進法のものと十進法のものでは値が異なる。そこで四進法であることを明記するため

312.02₄

もしくは

(312.02)₄

と書き表す事もある。

コンピューターで特に重要性の高い二進数、八進数、十進数、十六進数には固有の表記もある(ただしコンピューター言語により表記方法が若干違う場合もある)：

0b101 ： (101)₂の意味
0o306 ： (306)₈の意味
0d248 ： (248)₁₀の意味
0xF4C ： (F4C)₁₆の意味

厳密な定義編集

以下話を簡単にする為、非負の有限小数の場合のみを扱うが、無限小数の場合も同様である。

なお以下、「数字」という言葉を通常よりかなり広範な意味に用いており、アラビア数字、漢数字、マヤ数字、英語のアルファベットなどを含めた任意の記号を指している事に注意されたい。

自然数 N を一つ固定する。( N をこの記数法の底（てい）または基数という)。

さらに N 個の記号 ${\mathfrak {c}}_{0},\ldots ,{\mathfrak {c}}_{N-1}$ を固定する。(例えばアラビア数字とアルファベットで十六進法を表す場合は、N =16 で、 ${\mathfrak {c}}_{0}=\mathbf {0} ,\ldots ,{\mathfrak {c}}_{9}=\mathbf {9} ,{\mathfrak {c}}_{10}=\mathbf {A} ,\ldots ,{\mathfrak {c}}_{15}=\mathbf {F}$ )。

さらに各 ${\mathfrak {c}}_{j}$ に対し、

\ell ({\mathfrak {c}}_{j})=j

と定義する。

このとき、記号 ${\mathfrak {c}}_{0},\ldots ,{\mathfrak {c}}_{N-1}$ を数字として用いた N 進法とは、自然数 n 、 m を用いた

a_{n}a_{n-1}\cdots a_{1}a_{0}.a_{-1}\cdots a_{-m},~~~~~a_{-m},\ldots ,a_{n}\in \{{\mathfrak {c}}_{0},\ldots ,{\mathfrak {c}}_{N-1}\}

という形に表記( N 進表記、もしくは N 進数表記)に非負の実数

\sum _{i=-m}^{n}\ell (a_{i})N^{i}

を対応させる表記体系の事である。

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

N 進数表記の先頭に「+」もしくは「-」の符号をつけることで、数の正負を表現することもできる。

符号をつけた場合の N 進数表記の詳細な説明は省略する。

表記の一意性に関して編集

この節では特に断りがない限り十進数について述べるが、他の基数についても同様である。

実数の N 進表記は一意ではない。よく知られているように、

1=1.000…=0.999…

である。また、以下のように、上位桁に不要な0を付け加えることもできる

0013=13

通常は「0013」のような表記は許さないとする事が多いが、コンピューターなどでは、最大で4桁の整数値であることを示すため、あえて「0013」のような表記をする場合がある。

以上のような例をのぞくと0以外の実数は一意に表現できる。

しかし0のみは

「+0」、「-0」

の二通りの表記が可能である(いわゆる負のゼロの問題)。これが原因で、コンピューター・プログラムでは0のみ例外処理を求められる場合がある。

底の変換アルゴリズム編集

与えられた非負整数 T を、記号 ${\mathfrak {c}}_{0},\ldots ,{\mathfrak {c}}_{N-1}$ を数字として用いた N 進表記

a_{r}\cdots a_{0}

で表すには、以下のアルゴリズムを用いればよい。

なお、このアルゴリズムは、 M ≠ NによりM 進表記されている T を N 進表記に書き換えるときに使われる事が多いので、このアルゴリズムを底の変換アルゴリズムと呼ぶ。

入力T を受け取る。
T=0 なら ${\mathfrak {c}}_{0}$ を出力して停止。
iを0に初期化
while(T≠0){
- T を N で割った商を T' 、余りを k とし、 $a_{i}\gets {\mathfrak {c}}_{k}$ とする。
- T ←T'、i←i+1
}
r←i-1
$a_{r}\cdots a_{0}$ を出力

なお、T >0に対しては等式

r=\left\lfloor \log _{N}T\right\rfloor

が知られている(なお、添え字を0から始めているので、T の桁数はr +1) 。ここで $\left\lfloor x\right\rfloor$ は床関数である。

例編集

十進表記の 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\leq \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 = 1×6³ + 1×6² + 3×6¹
十進表記 270₁₀ : 270 = 200 + 70 = 2×10² + 7×10¹
十二進表記 (1A6)₁₂ : 270 = 144 + 126 = 1×12² + 10×12¹ + 6
二十進表記 (DA)₂₀ : 270 = 260 ＋ 10 = 13×20¹ + 10

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

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

複数の基数の混在編集

10進法では、基数は必ず10であるので、一桁増えるたびに10倍、10倍、10倍、10倍…となっていくのに対し、2-5進法（にごしんほう。二十五進法とは別概念）では2と5の二つの基数があるので桁があがるたびに5倍、2倍、5倍、2倍…と交互になる。

これはそろばんと同じ桁上がりルールだが、計算機にも応用されている。

日常生活で用いている数には、このように複数の基数が混在するものがあり、例えば時刻の単位は1日＝24時間、1時間＝60分、1分＝60秒であるから、これを2-5進法と同様に名付けるとすれば「24-60-60進法」である。(ただし一日の一つ上の単位である一週間は60日ではなく7日なので、2-5進法とは若干ルールが異なる)。

また日本の硬貨・紙幣には、一万円、五千円、千円、五百円、百円、五十円、十円、五円、一円があるので、硬貨・紙幣を一つの単位と見れば、これは前述の2-5進法である。

英語表記編集

「倍数接頭辞」も参照

「基数 N 」を英語で、base N という。特定のNに関しては倍数接頭辞をもとに名称がついているが、名称の付け方は不規則である。

以下は「基数 N 」、もしくはより一般に「 N 個のものからなる」という意味の形容詞である。

2：binary
3：ternary
4：quaternary
5：quinary
6：senary
7：septenary
8：octal
10：decimal
12：duodecimal
15：pentadecimal
16：hexadecimal
20：vigesimal
60：sexagesimal

これらを使い、a base-2 numberで「2進数」、the base-2 numeral systemで「2進法」を表す名詞となる。同様にa binary number、the binary numeral systemでもそれぞれ「2進数」、「2進法」を表す名詞となる。他の基数も同様。

p進数編集

詳細は「p進数」を参照

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

脚注・参照編集

^ 専門な注であるが、以下、太字で書かれた数字はシンタックスの体系内の記号であり、太字ではない数字はセマンティクスを記述するメタな記号である。

参考文献編集

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

^β