見出し画像

Cinderella で数学・情報：基数変換

クリヤキン

　基数変換について，Cinderella を利用して学びます。CindyScript を使ったプログラミングの練習にもなります。

2進法と16進法

　コンピュータは2進法で計算を行います。2進法で表された数の１桁のことを ビット(bit）といいます。コンピュータでは、4bit、8bit、16bit・・ という単位で数を処理します。その場合、上位桁が０の場合も「0」を書いて、常に0か１を４個、８個、16個、・・・と書くのが普通です。
　たとえば，4bit の2進法で表された数は $${0000_{(2)}}$$ から $${1111_{(2)}}$$ まで，8bitの2進法で表された数は $${00000000_{(2)}}$$　から，$${11111111_{(2)}}$$ までです。
　なお，ｎ進法で表された数は、右下に (n) と表記します。（10進法で表された数の場合は略す。）
　コンピュータは2進法で計算をしますが、コンピュータを扱う人間は16進法で表された数を用います。16だけ進むと桁が上がる位取り記数法が16進法です。16進法で表された数では15まで桁が上がらないので、0〜9の数字と、アルファベットA〜Fを用いて数を表します。これは，2進法の表記とうまく対応しています。
　たとえば，4bit の2進法で表された$${0000_{(2)}}$$ から $${1111_{(2)}}$$までの数は，16進法では $${0}$$ から $${F_{(16)}}$$ まで，8bitの2進法で表された $${00000000_{(2)}}$$　から，$${11111111_{(2)}}$$ までは $${00_{(16) }}$$から $${FF_{(16)}}$$ までです。

位取り記数法と基数変換

　私たちが通常扱っている整数は、10進法で表されています。「10まで進んだら桁が上がる」というものです。このような「桁」によって数を表す方法を「位取り記数法」といいます。一般に、nだけ進むと桁が上がる位取り記数法をn進法といいます。
　m進法で表された数をn進法に変換することを基数変換といいます。10進法と2進法の変換は数学や情報の教科書に載っていますが，きちんと理解するには位取り記数法の理解が必要です。
　たとえば，次のようにします。
　　$${4052=4 \times 10^3 + 0 \times 10^2 + 5 \times 10^1 + 2 \times 10^0}$$
　　$${1101_{(2)}=1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0}$$

　この表記法を利用すると，ｎ進法で表された数を10進法で表された数にするには，上のように指数を用いて和を求めればよく、逆に10進法で表された数をｎ進法で表された数に変換するには，ｎで割った余りをどんどん求めていけばよいことがわかります。

【例】1970 を16進法で表された数にする。
　1970 を 16  で割ると商が 178 ，余りが 7。178 を 16 で割ると商が 11， 余りが２，11 は16進法で B なので，$${1970=7B2_{(16)}}$$

　表計算ソフトには，10進法，2進法，16進法の換算を行う関数があります。たとえば，Excelの場合次のような関数があります。
　DEC2BIN ：10進法から2進法への変換。
　DEC2HEX ：10進法から16進法への変換。
　BIN2DEC ：2進法から10進法への変換。
　HEX2DEC ：16進法から10進法への変換。
しかし，あまり大きな数の換算はできません。
これらの変換をするプログラムをCindyScript で作ってみましょう。

10進法から2進法へ

　10進法から２進法に変換する関数を作ります。
　８ビット（１バイト）の2進法では、10進法の０から255まで（負でない整数の場合）まで表せます。１６ビットでは０から65535までです。現在のコンピュータは64ビットでの計算が普通ですが、まずは16ビットくらいまでは変換できるようにしましょう。
　10進法を２進法に変換するには、正の整数の場合、2で次々に割りながら、その余りをビットとして立てていくのでした。このことは、単に手続きとして暗記するのではなく、位取り記数法の原理として理解しておきましょう。これについては，「生徒が苦手な基数変換」という記事を書いています。

　では、10進数を２進数に変換する関数を作ります。関数定義なのでInitializationスロットに書くとよいでしょう。

bin = ["0", "1"];
dec2bin(n):=(
  keta = if(n > 255, 16, 8);
  binstr = "";
  repeat(keta,
    binstr = bin_(mod(n, 2) + 1) + binstr;
    n = floor(n/2);
  );
  binstr;
);

１行目：２進数の各桁で使う文字、０と１をリストにしておきます。
２行目が関数の名前。引数はｎです。ここで、ｎは正の整数であるという前提です。そうでない場合はどうするかはあとで考えましょう。
３行目、引数のnの大きさにより、8ビットで表すか16ビットで表すかを決めます。この数は、6行目の繰り返し数にもなります。
４行目、戻り値の文字列です。最初は空。
５行目から８行目が計算。繰り返しです。
６行目、nを2で割った余りを求めます。０か１ですので、１を足してbinリストから該当する文字を取り出します。たし算になっていますが、文字列のたし算は文字の追加になります。
７行目、nを2で割った商をあらためてnとします。floorという関数は床関数というもので、その数を超えない最大の整数を求めるものです。数学の教科書ではガウス記号で表されるものです。floorはCindyScriptに用意されている関数です。
途中でnは０になることがありますが、かまわず繰り返します。それによって8ビットもしくは16ビットの表示ができるわけです。
９行目、戻り値です。CindyScriptの関数定義では、最後に評価された（計算された）結果が戻り値となります。ここでは何も計算していませんが，binstrを「評価」したので、binstr が戻り値となります。この行がないと、戻り値は７行目のnになってしまいます。

これで関数定義ができたので、Drawスロットに書いて実行してみましょう。

10進法から16進法へ

　10進法を16進法に変換する関数を作ります。原理は２進法の場合と同じですから、先ほどのスクリプトを少し書き換えればいいですね。
　最初に16進法で使う文字０からＦまでのリストを作っておきます。16進法なのでこんどは hex とします。

hex=["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"];

あとは、255以下なら2桁表示、256以上なら4桁表示とし、2で割るところを16で割るようにすればいいだけです。実際のコードは読者の課題としましょう。
こんな結果になります。

２進法から１０進法へ

　２進法の数も16進法の数も，プログラム上では文字列として扱わなければなりません。そこで，引数も文字列として渡します。
　２進法なら右から１ビットずつとって数に変換し，２のｎ乗（ｎは桁数）をかけて足していけばいいのです。数に変換するには，parse という組み込み関数があります。

bin2dec(str):=(
  ret = 0;
  repeat(length(str), n,
    bit = str_(-n);
    ret = ret + parse(bit)*2^(n-1);
  );
ret;
);

dectbin で２進法にした数を，これで戻してみましょう。

１６進法から１０進法へ
これも，左から１文字ずつとって10進数にし，16のn乗（nは桁数）をかけて足していけばいいでしょう。16進法の文字は，文字列 "0123456789ABCDEF" の何文字目かを取得すれば10進法の数になります。

hex2dec(str):=(
  ret = 0;
  repeat(length(str), n,
    w = str_(-n);
    m = indexof("0123456789ABCDEF",w);
    ret = ret + (m-1)*16^(n-1);
  );
  ret;
);


負の数へ拡張

　ExcelやCalcのDEC2HEX関数は、負の整数も変換します。−512までです。つまり、ExcelやCalcでは、２進法への変換については、10ビットまでできるということになります。ただ、プログラミングの観点からすると、10ビットというのは中途半端なので、ここでも8ビットまたは16ビットとしましょう。
　さて、8ビットで正の数と負の数を表すためには、まず、「正か負か」という情報が必要になり、そのために最上位（一番左）の1ビットを使います。ここが0なら正、1なら負、とします。残り7ビットで数を表すので、正の数は127まで表せます。次に負の数ですが、「絶対値が同じ正の数と負の数の和は０」ということに着目します。さらに、２進法では、1＋1＝10 と「１たす１」で桁が上がって０になる、ことも考慮すると
　　0001＋1111＝10000
となって、はみだした一番左の１を除けば4ビット分は０になります。すなわち、−１を4ビットで表すと1111です。このような表現方法を「２の補数」というのですが、この「補数」というのがわかりにくい言葉で、これでめげてしまう人も結構います。教科書によっては「各ビットを反転させた１の補数に１を加える」という説明がしてあるのもあり、「補数」でますますわけがわからなくなる人もいるでしょう。
　「補数」はパスして、「1111（8ビットなら11111111）が −１でそこから１ずつ引いていく（−２は1110、−３は1101・・・）」と考えたり、「とにかく足して 0000・・・になるようにする」と考えたり、そこは人によって覚えやすい方法をとればよいでしょう。
　では、スクリプトを書くには、どのアルゴリズムを使えばよいでしょう。
「各ビットを反転させた１の補数に１を加える」の「１を加える」がヒントになります。実際の表記を眺めてみましょう。簡単のため４ビットにします。

10進法　 −５    −４    −３    −２   −１     ０       １       ２       ３       ４      ５
２進法　 1011  1100  1101  1110  1111  0000  0001  0010  0011  0100  0101

　たとえば，「−４に１を加えて−３。符号を変えた３のビットを反転させれば−４の２進表記」になっています。「−４の符号を変えて４，1を引いて３，３のビットを反転」でもいいでしょう。　
　次のようなスクリプトにしてみました。関数名は、符号付ということでsgnをつけました。

dec2binsgn(n):=(
  regional(bin);
  keta = if(or(n>127, n<-128), 16, 8);
  if(n < 0,
    bin = reverse(bin);
    wn = abs(n) - 1;
    ,
    wn = n;
  );
  binstr = "";
  repeat(keta,
    binstr = bin_(mod(wn, 2) + 1) + binstr;
    wn = floor(wn/2);
  );
  binstr;
);

２行目：bin をこの関数の中だけで使う局所変数にします。というのは，５行目でbin を書き換えてしまうからです。こうすれば，この関数を呼び出すたびに，bin が定義されます。
４，５行目： nが負の数だったら、binの順序を入れ替えて bin=["1","0"] にするのです。つまりビット反転。
６行目： wnを設定します。「nの符号を変えて１を引く」
８行目 ：nが負でなければ、wnはそのままnを代入します。
１０行目から後は dec2bin と同じ。次々に２で割っていきます。

小数の変換

　まず、小数の表記を分数表記で見てみましょう。
10進法では次のようになっています。
　$${0.1 = \frac{1}{10}}$$ , $${0.01 = \frac{1}{10^2}}$$ , $${0.001 = \frac{1}{10^3}}$$ ・・・・
2進法では
　$${0.1 _{(2)}= \frac{1}{2}}$$ , $${0.01_{(2)} = \frac{1}{2^2}}$$ , $${0.001_{(2)} = \frac{1}{2^3}}$$ ・・・・ 
たとえば、 0.8125 を２進法で表すと
$${0.8125=0.5+0.25+0.0625=\frac{1}{2}+\frac{1}{2}^2+\frac{1}{2}^4}$$
なので $${ 0.1101_{(2)}}$$ となります。
したがって，次々に２をかけながら、その整数部分をとっていけばよいことになります。ただし、整数の場合と違って、いつまでたっても終わらないことがあります。無限小数になるのです。そこで、どこかで打ち切ることにしますが、16ビットまでいったら打ち切ることにしましょう。そのためには、repeat文での繰り返しではなくwhile文での繰り返しを行ないます。整数の場合と違って少し複雑です。

decimal2bin(x):=(
  regional(bin);
  bin = ["0","1"];
  if(x >= 1,
    binstr = "換算する数は１未満の小数です";
    ,
    binstr="0.";
    keta =0;
    while(and(x != 0, keta < 16),
      wx = x*2;
      binstr = binstr + bin_(floor(wx) + 1);
      x = wx - floor(wx);
      keta = keta + 1;
    );
    if(and(keta == 16, x != 0),
      binstr = binstr + "・・以下さらに続きます";
    );
  );
  binstr;
);

４行目： 1より小さい小数の変換をする関数ですので１以上の場合はここでエラーメッセージを出すようにします。
７行目から xが1未満であればここからあとが実行されます。binstrは小数なのでまず "0." にします。
８行目： 整数の場合と異なり、桁数ははじめに決めるのではなく、カウントをしていきます。はじめは０にしておきます。
９行目 while(A,B) はAが成り立つ間Bを実行する、という繰り返し構文です。and(C,D)は、CかつDです。終了するのは、2倍していって整数部分を取り除き、最後に０になったときです。ですから、xが０でない（!=0）あいだ繰り返します。もうひとつ、桁数が16桁未満なら繰り返します。この２つの条件が両方とも成り立つときなので、and です。
１０行目： xに２をかけたものをwxとします。
１１行目：２をかけた wxが1より大きくなったら１を、そうでなければ０を取り出すために、床関数 floor を使います。floor(wx) は０か１なので、０ならば、bin=["0","1"]の1番目、１ならば2番目を取り出して、binstrの右に付け加えます。
１２行目 wxから０か１を引いてあらためてxとします。
１３行目 何桁作ったかカウントします。
１６行目 ：16桁までやって終わらない場合、「さらに続きます」という文字を付け加えます。

次が実行結果です。

0.1 は２進法では無限小数になるのです。

浮動小数点数

　実数は、浮動小数点という方法で表します。
　10進法で表された数で大きな数や微小な数を表すとき、次のように指数を使って表す方法があります。
【例】地球の体積　およそ　$${1.0833207 \times 10^{12} km^3}$$　　（1兆833億・・・）
　　　水素原子の原子核の大きさ　およそ　$${1.0 \times 10^{-15} m}$$

これと同様に、２進法で表された数でも指数を使って実数を表すことができます。

【例】10進法で表された数 150.8125 を2進法で表された数で表すと，
　　$${10010110.1101}$$ となる。
　　小数点を7つ左にずらすと
　　　$${1.00101101101 \times 2^7}$$
　　この数は、小数点以下の 00101101101 と 指数 ７ (2進法で表すと 0111) で
　　表現できる。

00101101101 を仮数部、 0111 を指数部といい、これに正負の符号を表す１ビットを加えて、次のように表します。（実際の指数部は指数７に127を加えた 134 を2進法で表された数にします）
　　　０ １００００１１０ ００１０１１０１１０１００００００００００００
　　符号部　指数部(8bit)　　　仮数部（23bit 左から埋めて右方は０にする）

　これは、32ビットで実数を表す単精度浮動小数点数です。さらに64ビットを用いて精度の高い数を表す倍精度浮動小数点数もあります。
　プログラムについては，読者の課題としましょう。

基数変換ツール


，10進法，2進法，16進法の相互変換をする「基数変換」をWeb上で実行できるページを作りました。いままでに作った関数の確かめとしても使えるでしょう。

リンク先を開くと次の画面になります。

実数10進法→2進法　の実行例がタイトル画像です。

← Cinderellaで数学・情報記事一覧に戻る