二進法

2を底とし、底およびその冪を基準にして数を表す方法

二進法にしんほう: binary numeral system, base-2 numeral system)とは、底を2とする位取り記数法および命数法である。二進法によって表された数を二進数にしんすう: binary number)と呼ぶ。二進法において、位は順に底2の冪…, 1/4, 1/2, 1, 2, 4, …)ごとに取り、位の値は 0 または 1 を取る(例:十進数7 (= 4 + 2 + 1) は二進法で 1111.75 (= 1 + 0.5 + 0.25)1.11 と表される)。

記数法 編集

 
二進法で表された数

を底とする位取り記数法二進記数法または単に二進法と呼ぶ。二進法による数の表示は、一の位を k = 0 とし添字 k で位の位置を表し、位の値を dk ∈ {0, 1} で表せば、以下のように書ける:

 

これは以下の総和の略記と見なせる:

 

例えば十進法における 21.25 は二進法において、

 

と表される(添字の 2 は二進表記であることを示す)。負の数は一般的な記数法と同じく、負号をつけて表す(例:−10101.012)。

十進法など一般の位取り記数法と同様に、二進法においても小数部が有限の長さとなる数は一部の有理数に限られ、また円周率のような無理数を厳密に表すことはできない。二進法の場合、有理数を表す既約分数について、分母が2の冪ならば有限小数として書けるが、そうでないならば有限小数としては書けない。例えば十進法では 1/5 を有限小数 0.2 で表せるが、二進法では循環小数 0.00112 = 0.00110011…2 で表さなければならない。

デジタル機器での使用 編集

電子式コンピュータ電子回路などのデジタル回路(デジタル論理回路)、磁気ディスク等の記憶メディアでは、電圧の高低、磁極の N/S など、物理現象を二状態のみに縮退して扱う(離散化などと言う[注 1])ので、それに、真と偽の2つの値(2値の真理値)のみを使用する二値論理(しばしば、電子的には HL、論理的には TF という記号が使われる)をマッピングする。更にそこで数値を扱うには、それに「01」の二進法をマッピングするのが最適である。

多くの応用で見られるように数が有限の場合は、数学的に言うなら「有理数の部分集合」が表現されているわけであるが、通常は「有限精度の実数」が表現されていると解釈される。このため、コンピュータやデジタル機器は二進数が使用される。

また、八進法十六進法三十二進法は同じく2の冪を底とするためしばしば利用される。

負数の扱い 編集

ビット列によって負の数の値を表すため広く用いられる方法の一つとして、2の補数表現がある。2の補数表現は、n 桁のビット列の最上位ビットの重みを +2n−1 ではなく −2n−1 とするものである。2の補数表現は、そのビットパターンが、加減(及び、乗)の演算において特別な処理が不要なものになる、という特長を持つ。ただし、溢れ(オーバーフロー)の扱いが違ってくる(これは、例えばx86プロセッサにおける、キャリーフラグとオーバフローフラグの違いのことである(ステータスレジスタ#キャリーとオーバーフローを参照))。

他のN進法から二進法への変換方法 編集

十進法から二進法への変換方法」などといったものを考える必要はない。どちらも数の「表現法」に過ぎないのだから、単に「表現法 → 数 → 表現法」といったようにして変換すれば良いのである。

正の整数 編集

正の整数 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 を二進法に変換する。

処理 (途中)結果
  0.
  0.0
  0.01
  0.010

ここで「処理」の部分の最後「 」はそれ以前に出てきた式である。このため、これ以上続けても同じ式の繰り返しで永久に終わらないことがわかる。すなわち小数部の「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 である。

命数法 編集

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

十進 二進 南キワイ語 シッサノ語
1 1 neis puntanen
2 10 netewa eltin
3 11 netewa nao eltin puntanen
4 100 netewa netewa eltin eltin
5 101 netewa netewa nao eltin eltin puntanen

現代日本における万進、あるいは十二進法体系であるダース・グロスなどのように、2倍ごとに新しい単位が命名される体系は、自然言語では、パプアニューギニアメルパ語[4] (Melpa) でのみ知られている[3]

十進 二進 メルパ語
1 1 tenta
2 10 ralg
3 11 raltika
4 100 timbakaka
5 101 timbakaka pamb ti
6 110 timbakaka pamb ralg
7 111 timbakakagul raltika
8 1000 engaka
9 1001 engaka pamb ti
10 1010 engaka pamb ralg pip

歴史 編集

 
ライプニッツによる八卦と二進法の比較[5]

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

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

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

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

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

1800年代中頃、イギリスの数学者ジョージ・ブールブール代数ブール論理)により、二進的な数(ここで言う「数」は、数学的な広義の意味であり、普通の二進法の対象である、数値という意味ではない)の代数による命題論理の形式化を示した。

1936-1937年の中嶋章と榛沢正男による「継電器回路に於ける単部分路の等価変換の理論」、1937年のクロード・シャノンによる "A Symbolic Analysis of Relay and Switching Circuits" により相次いで、リレーのようなスイッチング素子による回路(ディジタル回路)の設計がブール代数によって行えることが示され、1940年代に始まり今日まで続くコンピュータの理論の基礎のひとつとなっている。

脚注 編集

注釈 編集

  1. ^ 量子化とも言うが、量子物理におけるいわゆる量子のような意味(重ね合わせ状態など)ではない。

出典 編集

  1. ^ Gordon, Raymond G., Jr., ed. (2005), “Kiwai, Southern”, Ethnologue: Languages of the World (15 ed.), http://www.ethnologue.com/show_language.asp?code=kjd 2008年3月12日閲覧。 
  2. ^ Gordon, Raymond G., Jr., ed. (2005), “Sissano”, Ethnologue: Languages of the World (15 ed.), http://www.ethnologue.com/show_language.asp?code=sso 2008年3月12日閲覧。 
  3. ^ a b Lean, Glendon Angove (1992). “TALLIES AND 2-CYCLE SYSTEMS”. Counting Systems of Papua New Guinea and Oceania. Ph.D. thesis, Papua New Guinea University of Technology. オリジナルの2007年9月5日時点におけるアーカイブ。. https://web.archive.org/web/20160304132322/http://www.uog.ac.pg/glec/thesis/ch2web/ch2.htm 
  4. ^ Gordon, Raymond G., Jr., ed. (2005), “Melpa”, Ethnologue: Languages of the World (15 ed.), http://www.ethnologue.com/show_language.asp?code=med 2008年3月12日閲覧。 
  5. ^ a b ライプニッツ『ライプニッツ著作集 10 中国学・地質学・普遍学』下村寅太郎ほか 監修、工作舎、1991年、p12。
  6. ^ Sanchez, Julio; Canton, Maria P. (2007), Microcontroller programming : the microchip PIC, Boca Raton, Florida: CRC Press, p. 37, ISBN 0-8493-7189-9 
  7. ^ W. S. Anglin and J. Lambek, The Heritage of Thales, Springer, 1995, ISBN 0-387-94544-X
  8. ^ Bacon, Francis (1605), The Advancement of Learning (英語), vol. 6, London, Chapter 1

関連項目 編集