二進法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年9月30日 (月) 19:16時点における210.203.247.7 (トーク)による版 (十進法との対応)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

二進法(にしんほう)とは、2(てい)とし、底およびそのを基準にして数を表す方法である。

二進法を英語バイナリ (binary) というが、これは二個一組や二単位を意味するである。

歴史

中国には古くから八卦六十四卦があり、それぞれ 3 ビットと 6 ビットの二進数に相当している。易経の六十四卦の配列は対応する二進数 (0-63) の順になっていて、それらを 1→2→4→8→16→32→64 と進展させる「加一倍の法」を11世紀の儒学者邵雍が考案した。ただし、邵雍が二進法の計算を理解していたという証拠はない。その配列はそれぞれが二種類の値をとる要素の 6 タプル辞書式順序に並べたものと見ることもできる。

インドの学者ピンガラ (Pingala, 紀元前200年頃) は韻律を数学的に表現する方法を考案し、それが現在知られている最古の二進法の記述の一つとされている[1][2]

同様の二進法的組合せの使用は、アフリカのヨルバ人が行っていた占い Ifá にもあり、中世ヨーロッパやアフリカのジオマンシーにも見られる。2 を底とする体系はサハラ以南のアフリカでジオマンシーに長く使われていた。

1605年フランシス・ベーコンはアルファベットの文字を二進数字の並びで表す体系を論じ、任意の無作為なテキストで微かに判別可能なフォントの変化に符号化できるとした。二進符号化の一般理論として彼が指摘した重要な点は、同じ方法をあらゆる物に適用できるという点であり、「2種類の異なる状態をそれらの物で表現できればよく、鐘、トランペット、光、松明、マスケット銃など同様の性質があればどんなものでもよい」とした[3]。これをベーコンの暗号と呼ぶ。

数学的に二進法を確立したのは17世紀ゴットフリート・ライプニッツで、"Explication de l'Arithmétique Binaire" という論文も発表している。ライプニッツは現代の二進法と同じく、1 と 0 を使って二進法を表した。ライプニッツはシノファイル(親中家)でもあり、後に「易経」を知って、その六十四卦に 0 から 11111 までの二進数を対応させ、彼の賞賛してきた中国の哲学的数学の偉大な成果の証拠だとした[4]

1854年イギリスの数学者ジョージ・ブール論理学代数体系を詳述した重要な論文を発表し、それがブール論理/ブール代数と呼ばれるようになった。その論理計算法は後にデジタル電子回路の設計に使われるようになった。

1937年マサチューセッツ工科大学クロード・シャノンが修士論文でブール代数と二進計算をリレーとスイッチを使った回路で実装できることを示した。"A Symbolic Analysis of Relay and Switching Circuits" と題したその論文がデジタル回路実用化の基礎を築いた。

1937年11月、ベル研究所に勤務していたジョージ・スティビッツがリレーを使った計算機 "Model K" を完成させた。これは二進数の加算ができる装置である。ベル研究所はこれを受け、スティビッツを中心とした正式な研究プログラムを1938年末に開始した。1940年1月8日に完成した "Complex Number Computer" は複素数の計算が可能だった。1940年9月11日にダートマス大学で開催されたアメリカ数学会の会議でデモンストレーションが行われ、スティビッツはテレタイプ端末でコマンドを打ち込んで、電話回線経由で遠方にある計算機を操作して見せた。これが電話回線経由で遠隔から計算機を使った世界初の事例である。この会議に出席しデモンストレーションを目にした人物として、ジョン・フォン・ノイマンジョン・モークリーノーバート・ウィーナーらがおり、彼らはその経験について文章を残している。

記数法

2 を底とする位取り記数法二進記数法と呼ぶ。十進法と区別するときは下付の 2 を用いて、(110)2 とする。二進記数法で

<math>a_Na_{N-1}\ldots a_1a_0.a_{-1}a_{-2}\ldots</math>

(各位の値 ai は 0 か 1)と表される数は二進法の定義から、

<math>a_N2^N + a_{N-1}2^{N-1} + \cdots +
a_1 2 + a_0 + {a_{-1}\over 2} + {a_{-2}\over 2^2} + \cdots

</math> という数を表している(ここで 2 は十進法の 2 である)。

二進記数法で記された数を二進数ということがある。二進数という数の体系があるわけではない。また、p進数における p = 2 の場合とは全く異なる。

二進法を用いれば 0 と 1 の二種類の数字のみで零を含む任意の自然数が表現可能であり、負号と合わせることで整数が表現可能である。更に小数点を合わせて 4 種類の記号のみで実数の表現が可能である。

機器での使用

集積回路などのデジタル回路ハードディスクなどの磁気ディスクでは、電圧の高低、磁極の N/S など、二値の物理現象を用いるため、数を二進法で表すのが最適である。コンピュータの内部で数値を表現する場合、十進法を用いると 0 から 9 の十種類の数字に対応する十種類の内部状態を区別しなければならない。これは機構を複雑にするので、現代のデジタルコンピュータは通常は二進法を採用し、0 と 1 のみによって数値を表現している。入出力で十進法を用いるときは一般に十進法と二進法とで変換を行う。二進化十進表現を用いたり、IBMPOWER のように十進法による直接演算機能を持つコンピュータもあるが、回路としては二値を用いている。

多くの応用で見られるように数が有限の場合はより限定的には有理数の部分集合が表現されているわけであるが、通常は「有限精度の実数」が表現されていると解釈される。

機器での負の数の扱い

テンプレート:See also コンピュータ等で負の整数を扱う場合、広く一般的に用いられている方法は1番上位のビット(桁)を符号の用に扱い、すべてのビットが 1 のものを -1 とする方法である(2の補数を参照)。-2 は最下位ビットが 0 になる。8 ビットの場合(二進で 8 桁まで扱える場合)、-1 は 111111112、-2 は 111111102 と表現する。この方法は 111111102 + 12 = 111111112、111111112 + 12 = 02 となり、加減乗の演算において特別な処理が不要であるという特徴を持つ。ただし、最上位ビットで繰り上がり・繰り下がりが生じた場合に 9 ビット目より上を捨てて演算することになる。また 100000002 は -128 となるが、例えばC言語では符号付char型の数は -127 から 127 の数が扱えることが保証されるのみで、-128 が扱えることは保証されず、処理系依存となる(char型が最低限 8 ビットとして、2の補数以外の負数表現の利用も考慮した仕様)。

十進法から二進法への変換方法

正の整数

正の整数 m を十進法から二進法に変換するのは次のようにする。

  1. m を x に代入する。
  2. x を 2 で割って、余りを求める。
  3. x/2 の商を x に代入する。
  4. 2. に戻る。x = 0 であれば終了。

余りを求めた順の逆に並べると、それが二進法に変換された結果になる。

例:192を二進法に変換する。

2)192   192=20×192
2) 960 192=21× 96+20×0
2) 480 192=22× 48+21×0+20×0
2) 240 192=23× 24+22×0+21×0+20×0
2) 120 192=24× 12+23×0+22×0+21×0+20×0
2) 60 192=25× 6+24×0+23×0+22×0+21×0+20×0
2) 30 192=26× 3+25×0+24×0+23×0+22×0+21×0+20×0
2) 11 192=27× 1+26×1+25×0+24×0+23×0+22×0+21×0+20×0
0…1

よって 19210 = 110000002 である。

正で 1 未満の数

正で 1 未満 (0 < m < 1) である数 m を十進法から二進法に変換するのは次のようにする。

  1. 1 を n に、m を x に代入する。
  2. 2x < 1 ならば、小数点以下第 n 位は 0 になる。2x > 1 ならば、小数点以下第 n 位は 1 になる。
  3. 2x = 1 ならば終了。
  4. 2x > 1 ならば 2x - 1 を x に代入する。2x < 1 ならば 2x を x に代入する。
  5. n + 1 を n に代入する。
  6. 小数点以下の桁数が必要な桁数まで求まっているか、循環小数となったら終了する。
  7. 2. へ戻る。

計算の例1: 1/3 を二進法に変換する。

処理 (途中)結果
<math>\begin{matrix} \frac{1}{3} \end{matrix}</math> 0.
<math>\begin{matrix} \frac{1}{3} \times 2 = \frac{2}{3} < 1 \end{matrix}</math> 0.0
<math>\begin{matrix} \frac{2}{3} \times 2 = 1\frac{1}{3} \ge 1 \end{matrix}</math> 0.01
<math>\begin{matrix} \frac{1}{3} \times 2 = \frac{2}{3} < 1 \end{matrix}</math> 0.010

ここで「処理」の部分の最後「<math>\begin{matrix} \frac{1}{3} \times 2 = \frac{2}{3} < 1 \end{matrix}</math>」はそれ以前に出てきた式である。このため、これ以上続けても同じ式の繰り返しで永久に終わらないことがわかる。すなわち小数部の「01」が循環することがわかるので終了する。

よって1/310=0.010101…2=0.012

(なお、アンダーバーの部分(01)は無限に繰り返しという意味)

計算の例 2: 十進法での 0.1 を二進法に変換する。

処理 (途中)結果
0.1 0.
0.1×2=0.2<1 0.0
0.2×2=0.4<1 0.00
0.4×2=0.8<1 0.000
0.8×2=1.6≥1 0.0001
0.6×2=1.2≥1 0.00011
0.2×2=0.4<1 0.000110
0.4×2=0.8<1 0.0001100

ここで「処理」の部分の最後「0.4×2 = 0.8 < 1」はそれ以前に出てきた式である。このため、これ以上続けても同じ式の繰り返しで永久に終わらないことがわかる。すなわち小数部の「0011」が循環することがわかるので終了する。

よって 0.110 = 0.0001100110011…2 = 0.000112 である。

十進法との対応

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

命数法

二進命数法とは、2 を底とする命数法である。真の二進命数法では、2n に対応する数詞があり、数はそれらの和で表される。自然言語では、このような命数法はパプアニューギニアのメルパ語[5] (Melpa) でのみ知られている[6]

  メルパ語
1 tenta
2 ralg
3 raltika
4 timbakaka
5 timbakaka pamb ti
6 timbakaka pamb ralg
7 timbakakagul raltika
8 engaka
9 engaka pamb ti
10 engaka pamb ralg pip


通常、二進法の数詞を持つとされるものは二つ組で数える体系であり、乗算が含まれないため、真の二進法ではない。以下にパプアニューギニアの南キワイ語[7] (Southern Kiwai) およびシッサノ語[8] (Sissano) の数詞を示す[6]

  南キワイ語 シッサノ語
1 neis puntanen
2 netewa eltin
3 netewa nao eltin puntanen
4 netewa netewa eltin eltin
5 netewa netewa nao eltin eltin puntanen

参考文献

テンプレート:Reflist

関連項目


  1. テンプレート:Citation
  2. W. S. Anglin and J. Lambek, The Heritage of Thales, Springer, 1995, ISBN 0-387-94544-X
  3. テンプレート:Citation
  4. テンプレート:Citation
  5. テンプレート:Citation
  6. 6.0 6.1 テンプレート:Citation
  7. テンプレート:Citation
  8. テンプレート:Citation