44  記数法

凡算之法、先識其位。

– 「孫子算経」

古代中国では、算木を用いて計算が行われていた。現存する最古の算木は、戦国時代末期のものである。

「孫子算経」では、算木の位置によって数を表現する方法が説明されており、「凡算之法、先識其位」とは、「凡そ算の法は、其の位を識るを先とす」と訳される。

算木は算籌とも呼ばれる。経営工学における中心的な学問であるオペレーションズ・リサーチ（Operations Research、OR）の中国語訳は「運籌学」である。運籌の語源は史記の「運籌策帷幄之中決勝千里之外」に由来する。これは、「籌を帷幄に運らし、勝ちを千里の外に決す」という意味である。

ここでは、10進数、2進数、8進数、16進数の記数法について学ぶ。学習の目標は次の通りである：

44.1 10進数

私たちが日常的に使っている10進法は、0から9の数字を用いて数を表現する。各数字の位置によってその値が決まる。例えば、123という数は、以下のように表現される：

\[ 123 = 1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0 \]

このように、各数字の位置によってその値が決まる記数法を位取り記数法（くらいどりきすうほう、positional notation）と呼ぶ。

一般に、\(d_n\)をn桁目の数字、\(N\)を10進数の数とすると、以下の式が成り立つ：

\[ N = d_n \times 10^{n-1} + d_{n-1} \times 10^{n-2} + \ldots + d_1 \times 10^0 \]

44.2 他の記数法と底

底（base）とは、使用する数字の種類の数である。10進法では0から9までの10種類の数字を使用するため、底は10である。

  • 2進法では0と1の2種類の数字を使用し、底は2である。
  • 8進法では0から7までの8種類の数字を使用し、底は8である。
  • 16進法では0から9とAからFまでの16種類の数字を使用し、底は16である。

2進法は、2を底とする位取り記数法であり、0と1を使用し、数を表現する。そのため、0, 1の次には1桁を追加して10となり、次は11、100、101と続く。

以下に、10進数、2進数、8進数、16進数の対応表を示す：

10進数 2進数 8進数 16進数
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F

ここからは、下付き文字を用いて、底を示すことにする。例えば、2進数の101は、\(\texttt{101}_2\)と表記する。10進数の123は、\(\texttt{123}_{10}\)と表記する。

44.2.1 やってみよう

10進数の1~10を3進数で書いてみよう。

44.3 他の記数法から10進数への変換

上記の表を見るとわかるように、2進数2桁目の1は10進数の2で、3桁目の1は10進数の\(2^2\)である。つまり、2進数を10進数に変換する際は、下記のように計算することができる：

\[ d_n \times 2^{n-1} + d_{n-1} \times 2^{n-2} + \ldots + d_1 \times 2^0 = N_{10} \]

例えば、2進数の\(1001_2\)を10進数に変換する場合、以下のように計算する：

\[ 1001_2 = 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 9_{10} \]

\(d_n\)をn桁目の数字、\(R\)を底、\(N\)を10進数の数とすると、以下の式が成り立つ：

\[ N_{10} = d_n \times R^{n-1} + d_{n-1} \times R^{n-2} + \ldots + d_1 \times R^0 \]

また、以下のように書くこともできる：

\[ N_{10} = \sum_{i=1}^{n} d_i \times R^{i-1} \]

例えば、3進数の\(102_3\)を10進数に変換する場合、以下のように計算する：

\[ 102_3 = 1 \times 3^2 + 0 \times 3^1 + 2 \times 3^0 = 11_{10} \]

また、16進数の\(\texttt{1A3F}_{16}\)を10進数に変換する場合、以下のように計算する：

\[ \texttt{1A3F}_{16} = 1 \times 16^3 + 10 \times 16^2 + 3 \times 16^1 + 15 \times 16^0 = 6719_{10} \]

これは、16進数のAが10に相当し、Fが15に相当するからである。

44.3.1 やってみよう

次の数を10進数に変換せよ。 - \(1101_2\) - \(73_8\) - \(\texttt{CAFE}_{16}\)

44.4 2進法、8進法、16進法

2進法、8進法、16進法は、全て2の累乗を底とする記数法であるため、変換は簡単に行える。

2進数 16進数
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F

2進数の4桁ごとに16進数の1桁に対応する。例えば、2進数の\(1010110_2\)は、4桁ごとに区切ると\(0101\ 0110\)となり、これを16進数に変換すると\(56_{16}\)となる。

16進数を2進数に変換する場合は、各16進数の桁を4桁の2進数に変換すればよい。例えば、16進数の\(\texttt{1A3F}_{16}\)は、以下のように変換される：

\[ \texttt{1A3F}_{16} = 0001\ 1010\ 0011\ 1111_2 \]

8進法も同様に、3桁の2進数に対応する。

2進数 8進数
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7

2進数の3桁ごとに8進数の1桁に対応する。例えば、

\[ 1010110_2 = 001\ 010\ 110_2 = 126_8 \]

44.4.1 やってみよう

次の数を16進数と8進数に変換せよ。 - \(11010110_2\) - \(101110011_2\) - \(1111000100101001_2\)

次の数を2進数に変換せよ。 - \(\texttt{1A3F}_{16}\) - \(\texttt{7B2}_{16}\) - \(\texttt{35}_{8}\)

44.5 10進数から他の記数法への変換

10進数から他の記数法への変換は、下記の手順で行うことができる：

  1. 与えられた値を底で割り、商と余りを求める。
  2. 商が0になるまで繰り返す。
  3. 商が0になったら、余りを逆順に並べる。

このようなある問題を解決する手順をアルゴリズムと呼ぶ。

このアルゴリズムは、特定の条件（商が0になるまで）を満たすまで繰り返し処理を行う。これは、反復構造（iterative structure）と呼ばれる。

アルゴリズムは、コンピューターサイエンスや経営工学の分野では中心的な概念でる。大学4年間、経営システム工学科では、さまざまな問題解決のためのアルゴリズムが学ばれる。

例えば、10進数の\(113_{10}\)を2進数に変換する場合、以下のように計算する：

\[ 113 \div 2 = 56 \quad R_1 = 1 \\ 56 \div 2 = 28 \quad R_2 = 0 \\ 28 \div 2 = 14 \quad R_3 = 0 \\ 14 \div 2 = 7 \quad R_4 = 0 \\ 7 \div 2 = 3 \quad R_5 = 1 \\ 3 \div 2 = 1 \quad R_6 = 1 \\ 1 \div 2 = 0 \quad R_7 = 1 \]

余りを逆順に並べると、\(1110001_2\)となる。

検算として、\(1110001_2\)を10進数に戻すと：

\[ 1110001_2 = 2^6 + 2^5 + 2^4 + 2^0 = 113_{10} \]

もう一つの例として、10進数の\(268_{10}\)を16進数に変換する場合、以下のように計算する：

\[ 268 \div 16 = 16 \quad R_1 = 12 \\ 16 \div 16 = 1 \quad R_2 = 0 \\ 1 \div 16 = 0 \quad R_3 = 1 \]

余りを逆順に並べると、\(\texttt{10C}_{16}\)となる。

44.5.1 やってみよう

次の10進数を2進数、8進数、16進数に変換せよ。

  • \(45_{10}\)
  • \(100_{10}\)
  • \(255_{10}\)

44.6 ビットとバイト

情報量の最小単位はビット（bit）である。bitはbinary digit（2進数の桁）を略したもので、2進法の1桁分の情報を表す。バイト（byte）は、通常は8 bitで構成される。

例えば、\(\texttt{0101 0010}_{2}\)の情報量は8 bitであり、1 byteに相当する。

1 bitは0または1のいずれかの値をとる。そのため、1 bitは2種類の物事を表現できる。例えば、電源のオン/オフ、陽性/陰性、真/偽などである。

ビット数が増えると、表現できる種類も増える。2 bitでは、00、01、10、11の4種類を表現できる。8 bitは256種類（\(2^8\)）を表現できる。

1 Bit 2 Bit 3 Bit
0 00 000
1 01 001
10 010
11 011
100
101
110
111

一般に、\(n\) bitは\(2^n\)種類の情報を表現できる。

44.7 ビットパターン

このように、より複雑な情報を表現するために、複数のビットを並べるものはビット列（bit string）と呼ばれる。

コンピューターが扱うデータは、一般的に8, 16, 32, 64ビットなど、2の累乗のビット数で構成される。特定のビット数を持つデータは、ビットパターン（bit pattern）と呼ばれる。ビットパターンは，数値，文字，画像，音声など、様々なデータを表現するために使用される．

ビットパターンを2進数で表現すると非常に長くなる場合があるため、16進数を使用することも多い．1 byteは16進数では2桁で表現できる。例えば、8 bitのビットパターン\(10101100_2\)は、16進数では\(\texttt{AC}_{16}\)と表現される。

Macアドレスは、ネットワーク機器を識別するための一意のアドレスであり、通常は48ビット（6バイト）で表現される。16進数で表記されることが多く、例えば\(\texttt{00:1A:2B:3C:4D:5E}\)のように表現される。

Windowsでは、コマンドプロンプトでipconfig /allを実行すると、ネットワークアダプターのMACアドレスを確認できる。

44.8 練習問題

情報量の最小単位は_である。一般に、\(n\) bitは_の種類を表現できる。また、8 bitは1 ____に相当する。

44.9 まとめ

日本語 英語
10進数 decimal number
2進数 binary number
8進数 octal number
16進数 hexadecimal number
位取り記数法 positional notation

44.10 練習問題

  • google classroom

44.11 解答例

  • 3進数：
    • \(1_{10} = 1_3\)
    • \(2_{10} = 2_3\)
    • \(3_{10} = 10_3\)
    • \(4_{10} = 11_3\)
    • \(5_{10} = 12_3\)
    • \(6_{10} = 20_3\)
    • \(7_{10} = 21_3\)
    • \(8_{10} = 22_3\)
    • \(9_{10} = 100_3\)
    • \(10_{10} = 101_3\)
  • 他の記数法から10進数への変換
    • \(1101_2 = 13_{10}\)
    • \(73_8 = 59_{10}\)
    • \(\texttt{CAFE}_{16} = 51966_{10}\)
  • 2進数、8進数、16進数の相互変換
    • 省略
  • 10進数から他の記数法への変換
    • \(45_{10} = 101101_2 = 55_8 = \texttt{2D}_{16}\)
    • \(100_{10} = 1100100_2 = 144_8 = \texttt{64}_{16}\)
    • \(255_{10} = 11111111_2 = 377_8 = \texttt{FF}_{16}\)