46  記数法

凡算之法，先識其位．

– 「孫子算経」

ノート算木と「運籌学」

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

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

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

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

46.1 10進数

私たちが日常的に使っている10進法は，0から9の数字を用いて数を表現する．各数字の位置によってその値が決まる．

例 46.1 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

46.2 他の記数法と底

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

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

以下に，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進法は，2を底とする位取り記数法であり，0と1を使用し，数を表現する．そのため，0, 1の次には1桁を追加して10となり，次は11，100，101と続く．

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

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

上記の表を見るとわかるように，

\begin{align*} \texttt{0}_2 &= \texttt{0}_{10} = 0 \times 2^0 \\ \texttt{1}_2 &= \texttt{1}_{10} = 1 \times 2^0 \\ \texttt{10}_2 &= \texttt{2}_{10} = 1 \times 2^1 + 0 \times 2^0 \\ \texttt{11}_2 &= \texttt{3}_{10} = 1 \times 2^1 + 1 \times 2^0 \\ \texttt{100}_2 &= \texttt{4}_{10} = 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0\\ \texttt{101}_2 &= \texttt{5}_{10} = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \\ \end{align*}

である．つまり，2進数を10進数に変換する際は，下記のように計算することができる：

d_n \times 2^{n-1} + d_{n-1} \times 2^{n-2} + \ldots + d_1 \times 2^0 = N_{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}

例 46.2 (2進数から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}

例 46.3 (16進数から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に相当するからである．

46.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

16進数を2進数に変換する場合は，各16進数の桁を4桁の2進数に変換すればよい．

例 46.4 (2進数から16進数への変換) 2進数の 1010110_2 は，4桁ごとに区切ると0101\ 0110となり，これを16進数に変換すると56_{16}となる．

例 46.5 (16進数から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桁に対応する．

例 46.6 (2進数から8進数への変換) 2進数の1010110_2は，3桁ごとに区切ると001\ 010\ 110となり，これを8進数に変換すると126_8となる． 1010110_2 = 001\ 010\ 110_2 = 126_8

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

任意の10進数 x を n 進数へ変換するには，次の手順を繰り返す．

  1. x を底 n で割り，商（小数点以下切り捨て）と余りを求める．求めた余りを記録しておく．
  2. 商を新しい x とみなし，商が 0 になるまで手順1を繰り返す．
  3. 記録した余りを逆順に並べる．
ノートアルゴリズムとは

このような，ある問題を解くための明確な手順をアルゴリズムと呼ぶ．上記の変換手順は，次のように記述できる．

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

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

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

\begin{align*} 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 \end{align*}

余りを逆順に並べると，1110001_2となる．

検算として，1110001_2を10進数に戻すと：

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

例 46.8 (10進数から16進数への変換) もう1つの例として，10進数の268_{10}を16進数に変換する場合，以下のように計算する：

\begin{align*} 268 \div 16 &= 16 \quad R_1 = 12 \\ 16 \div 16 &= 1 \quad R_2 = 0 \\ 1 \div 16 &= 0 \quad R_3 = 1 \end{align*}

余りを逆順に並べると，\texttt{10C}_{16}となる．

46.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 種類の情報を表現できる．

例 46.9 (ナップサック問題の例) 容量10のナップサックに次の表にある品物を詰め込むことにする．この時，詰め込んだ品物の総価値を最大にするためには何をいくつ詰め込むと良いだろうか．

品物 重さ 価値
A 2 3
B 3 4
C 4 5

このとき，0を「詰め込まない」，1を「詰め込む」として，品物A，B，Cの組み合わせを2進数で表すと，次のようになる：

2進数 品物A 品物B 品物C 重さ 価値
000 詰め込まない 詰め込まない 詰め込まない 0 0
001 詰め込まない 詰め込まない 詰め込む 4 5
010 詰め込まない 詰め込む 詰め込まない 3 4
011 詰め込まない 詰め込む 詰め込む 7 9
100 詰め込む 詰め込まない 詰め込まない 2 3
101 詰め込む 詰め込まない 詰め込む 6 8
110 詰め込む 詰め込む 詰め込まない 5 7
111 詰め込む 詰め込む 詰め込む 9 12

よって，品物A，B，Cをすべて詰め込むと，重さ9で価値12となり，総価値を最大にすることができる．

46.7 ビットパターン

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

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

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

ノートMACアドレス

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

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

46.8 練習問題

情報量の最小単位は ____ である．一般に，n bitは ____ 種類の情報を表現できる．また，8 bitは1 ____ に相当する．

46.9 まとめ

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

46.10 練習問題

  • google classroom

練習 46.1 10進数の1〜10を3進数で書け．

解答 46.1.

  • 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

練習 46.2 次の数を10進数に変換せよ．

  • 1101_2
  • 73_8
  • \texttt{CAFE}_{16}

解答 46.2.

  • 1101_2 = 13_{10}
  • 73_8 = 59_{10}
  • \texttt{CAFE}_{16} = 51966_{10}

練習 46.3 次の数を16進数と8進数に変換せよ．

  • 11010110_2
  • 101110011_2
  • 1111000100101001_2

次の数を2進数に変換せよ．

  • \texttt{1A3F}_{16}
  • \texttt{7B2}_{16}
  • \texttt{35}_{8}

練習 46.4 次の10進数を2進数，8進数，16進数に変換せよ．

  • 45_{10}
  • 100_{10}
  • 255_{10}

解答 46.3.

  • 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}