提供：Japanese Scratch-Wiki
ここでは、Scratchで二進数(2進数、二進法、バイナリ、バイナリ―、binary)を扱う方法を説明する。
なお、以降の説明で、10進数と対をなす意味で"二進数"と言う単語が使われる場合は"2進数"と表記する。
また、この記事のスクリプトで使用している定義はすべてこのページ内に定義している物を使用している。
Scratch 3.0以降では、二進数は0bを頭につけて表現できるようになった。(例: 0b1001)
二進数の性質
二進数は、2を底として、数を表現する方法である。
底とは、ある位が桁上げして"0"になるために必要な最大の数値のことである。
二進数の表記
<10進数> 0,1,2,3,4,5,6,7,8,9,10←10が底(この例だと10で１の位が0になる) <2進数> 0,01,10←2が底(2進数では"10"と言う表記は10進数の"2"を表す)
また、他の進数表記と混同することを防ぐため2進数には表記上数値の後に"(2)"を付けることがある。
ただし、プログラムで扱う数値には"(2)"は付かないので注意。
10101101(2)←"(2)"が付いているので2進数
10101101 ←"(2)"が付いていないので10進数("(10)"と表記する場合もあるが、一般的には付けない事のほうが多い)
10101101(8)←この場合は8進数
10101101(16)←この場合は16進数
2進数を10進数に変換する
10010010(2)を10進数に変換する方法を次に示す。2進数の各桁は{ N x 2^(d-1) }と言う式で表すことができる。
この式の"N"は2進数の1か0のどちらかを表し、dは右から何桁目かを表している。この式に10010010(2)を当てはめると以下のようになる。
(1x2^7)+(0x2^6)+(0x2^5)+(1x2^4)+(0x2^3)+(0x2^2)+(1x2^1)+(0x2^0) = 128 + 0 + 0 + 16 + 0 + 0 + 2 + 0 = 146
次に上の式をScratchで実装する際の例を以下に示す。
定義 2進数を10進数に変換(2進数::custom-arg)
[2進数 v]を(2進数::custom-arg)にする::variables
[10進数出力 v]を(0)にする::variables
[カウンター v]を(0)にする::variables
((2進数::custom-arg)の長さ::operators)回繰り返す{
もし<((2進数::custom-arg)の(((2進数::custom-arg)の長さ)-(カウンター))番目の文字::operators)=(1)>なら{
[累乗記憶 v]を(1)にする::variables
(カウンター)回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする::variables
}::control
[10進数出力 v]を((10進出力)+(累乗記憶))にする::variables
}::control
[カウンター v]を(1)ずつ変える::variables
}::control
もっとも、Scratch 3.0では、0bをつけて変換できることから、(([0b]と(2進数::variables))+(0)などでも変換は可能である。
10進数を2進数に変換する
10進数を2進数に変換する場合、最も簡単なのは10進数のある値を余りが1か0になるまで2で割り、その余りを並べるというものだろう。Scratchでも、10進数から2進数への変換は変数2つで簡単に実装することができる。
定義 10進数を2進数に変換(10進数::custom-arg)
[2進数出力 v]を()にする::variables
[10進数入力 v]を(10進数::custom-arg)にする::variables
<(10進数入力)<(2)>まで繰り返す{
[2進数出力 v]を(((10進数入力)を(2)で割った余り)と(2進数出力))にする::variables
[10進数入力 v]を(((10進数入力)/(2))の[切り下げ v]::operators)にする::variables
}::control
[2進数出力 v]を((10進数入力)と(2進数出力))にする::variables
二進数の論理演算
論理演算とは、各桁を真偽値で評価する演算である。論理演算には、論理和(or)/論理積(and)/否定(not)/排他的論理和(xor)/否定論理和(nor)/否定論理積(nand)/否定排他的論理和(nxor)の7つがある。
否定(not演算)
否定は、入力値が1つである唯一の論理演算である。入力された二進数の桁すべてを反転させる。
10010110 ↓否定 01101001
定義 否定 (二進数)
[二進数出力 v]を()にする::variable
<((二進数出力)の長さ)=((二進数::custom-arg)の長さ)>まで繰り返す{
もし<((二進数::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators)=(1)>なら{
[二進数出力 v]を((二進数出力)と(0)::operators)にする::variable
}でなければ{
[二進数出力 v]を((二進数出力)と(1)::operators)にする::variable
}::control
}::control
論理和(or演算)と否定論理和(nor演算)
論理和は、2つ以上の入力された値の共通桁において、"1"が1つでも含まれる場合は"1"を出力する。また、否定論理和は論理和の出力を反転させたものである。
・論理和 10010110 or 10101010 → 10111110 ・否定論理和 10010110 nor 10101010 → 01000001
定義 論理和(二進数-1)(二進数-2)
[二進数出力 v]を()にする::variable
もし<((二進数-1::custom-arg)の長さ)=((二進数-2::custom-arg)の長さ)>なら{
<((二進数出力)の長さ)=((二進数-1::custom-arg)の長さ)>まで繰り返す{
もし<(((二進数-1::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators)+((二進数-2::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators))>(1)>なら{
[二進数出力 v]を((二進数出力)と(0)::operators)にする::variable
}でなければ{
[二進数出力 v]を((二進数出力)と(1)::operators)にする::variable
}::control
}::control
}::control
否定論理和は、論理和の結果を否定演算すれば良いだけなのでスクリプトは省略する。
論理積(and演算)と否定論理積(nand演算)
論理積は、2つ以上の入力された値の共通桁に置いて、すべてを掛けた結果が"1"だった場合のみ1を出力する演算である。また、否定論理積は論理積の出力を反転させたものである。
・論理積 10010110 and 10101010 → 10000010 ・否定論理和 10010110 nand 10101010 → 01111101
定義 論理積(二進数-1)(二進数-2)
[二進数出力 v]を()にする::variable
もし<((二進数-1::custom-arg)の長さ)=((二進数-2::custom-arg)の長さ)>なら{
<((二進数出力)の長さ)=((二進数-1::custom-arg)の長さ)>まで繰り返す{
もし<(((二進数-1::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators)*((二進数-2::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators))=(1)>なら{
[二進数出力 v]を((二進数出力)と(0)::operators)にする::variable
}でなければ{
[二進数出力 v]を((二進数出力)と(1)::operators)にする::variable
}::control
}::control
}::control
否定論理積は、論理積の結果を否定演算すれば良いだけなのでスクリプトは省略する。
排他的論理和(xor演算)と否定排他的論理和(nxor演算)
排他的論理和は、2つの入力された値の共通桁に置いて、どちらかの桁が"1"の場合のみ1を出力する演算である。また、否定排他的論理和は排他的論理和の出力を反転させたものである。
・排他的論理和 10010110 xor 10101010 → 00111100 ・否定排他的論理和 10010110 nxor 10101010 → 11000011
定義 排他的論理和(二進数-1)(二進数-2)
[二進数出力 v]を()にする::variable
もし<((二進数-1::custom-arg)の長さ)=((二進数-2::custom-arg)の長さ)>なら{
<((二進数出力)の長さ)=((二進数-1::custom-arg)の長さ)>まで繰り返す{
もし<(((二進数-1::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators)+((二進数-2::custom-arg)の(((二進数出力)の長さ)+(1))番目の文字::operators))=(1)>なら{
[二進数出力 v]を((二進数出力)と(1)::operators)にする::variable
}でなければ{
[二進数出力 v]を((二進数出力)と(0)::operators)にする::variable
}::control
}::control
}::control
二進数の算術演算
Scratchでは二進数の計算はサポートされていない。しかし、一度10進数に戻してから計算し、2進数に戻すという方法で一部の算術演算は簡単に実装することができる。
自然数同士の加算/乗算
自然数同士の加算/乗算は、演算結果に負数もしくは小数を含まないため、以下のスクリプトで十分に対応することができる。なお、以下のスクリプトに登場する定義はすべて前述のものを利用している。
2進数を10進数に変換(2進数入力)::custom//2進数の加算（疑似的な2進数どうしの加算） 10進数を2進数に変換((10進数出力)+(加算したい数値))::custom 2進数を10進数に変換(2進数入力)::custom//2進数の乗算（疑似的な2進数どうしの乗算） 10進数を2進数に変換((10進数出力)*(乗算したい数値))::custom
整数どうしの減算
自然数同士の減算を行った場合でも、結果が負の値を取る場合がある。ここでは、二進数での負数の表し方と二進数の減算について解説する。
二進数における負数の表現
二進数で負の数を表現するためには、一般的に"2の補数"と呼ばれるものを使用する。2の補数とは、固定長ビット列において負数を表現する方法であり、内部的には加算で減算を表現するために使用される負数の表現方法である。例えば、10進数で、5-8を加算で表現すると、5+(-8)と表すことができるように、負の数を足すことで減算を表現できる。ただし、この表現は固定長(例えば32桁で二進数の桁を固定する表現)以外の表現では使用することができない。理由は後述。
2の補数は二進数のすべての桁を反転し、1を足すことで求めることができる。
1001101(2)の2の補数を求める場合、すべての桁を反転し 0110010(2)にし、これに1を加算して 0110011(2)2の補数を求めることができる
2の補数が元の数の負数を表すことは、元の数とその数の2の補数を足して最上位桁以外が0になることから証明することができる。
1001101(2) +0110011(2) ----------- 10000000
この最上位桁以降はすべての桁が1である。なぜかというと2の補数を求める際、すべての桁を反転させているからである。
つまり固定長ではない二進数の場合、最上位桁より先の桁は、永遠に1が続いていることになるため、固定長での二進数以外での2の補数表現は困難である。
上記の証明から、二進数をプログラムとして扱う場合は固定長のほうが都合がよいことが分かった。よって、下記に二進数を固定長に整形するスクリプトを示す。
定義 固定長に整形する(非固定長二進数)(桁数)
[二進数出力 v]を(非固定長二進数::custom-arg)にする::variable
[スタック v]を()にする::variable
もし<((二進数出力)の長さ)<(桁数::custom-arg)>なら{
<((二進数出力)の長さ)=(桁数::custom-arg)>まで繰り返す{
[二進数出力 v]を((0)と(二進数出力))にする::variable
}::control
}でなければ{
<((スタック)の長さ)=(桁数::custom-arg)>まで繰り返す{
[スタック v]を(((二進数出力)の(((二進数出力)の長さ)-((スタック)の長さ))番目の文字::operators)と(スタック))にする
}::control
[二進数出力 v]を(スタック)にする::variable
}::control
補数表現と普通の数値との区別の仕方
2の補数はある数値の負の値を表現する方法であると書いたが、2の補数を負の数値として扱うかどうかはプログラム側にゆだねられている。
1011010(2)と言う二進数の数値を 普通の数値として10進数に変換して"90"という数値として扱うのか、それとも 2の補数として10進数に変換して"-36"という数値として扱うのかを決めるのは プログラム側の処理である
そこで、一般的に広く使われている区別の仕方は、最上位の桁を符号桁として扱う方法である。
固定長二進数の最上位桁を"符号桁"として扱う。符号桁が1なら負数として処理することを表し、 符号桁が0なら正の数値として処理することを表す。 0100100101000100 ←この場合は最上位桁が"0"なので正の数値として処理する 1100100101000100 ←この場合は最上位桁が"1"なので負の数値として処理する と言うように、正か負かを区別する符号桁を設けることでプログラムで負の値を区別することができる。
テキストベースのプログラミング言語でデータ型(変数型)が設けられているのは、「この型なら32bitの長さの二進数で符号を区別するよ」などと、プログラムに処理の仕方を指定するためである。
2の補数の実装
補数を求めるスクリプトを下記に示す。
定義 2の補数を求める(二進数)
2進数を10進数に変換(二進数)::custom
[累乗記憶 v]を(1)にする::variable
(((二進数::custom-arg)の長さ)+(1))回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする::variable
}::control
10進数を2進数に変換((累乗記憶)-(10進数出力))::custom
固定長に整形する(二進数出力)((二進数::custom-arg)の長さ)::custom
2の補数表現に対応するパッチ
"定義:10進数を2進数に変換"を2の補数に対応させ、符号付きの10進数を出力できるようにするパッチ定義を下記に示す。
定義 符号付き二進数に対応するパッチ(2進数)
もし<((2進数::custom-arg)の(1)番目の文字::operators)=(1)>なら{
[累乗記憶 v]を(1)にする::variable
(((2進数::custom-arg)の長さ)-(1))回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする::variable
}::control
[10進数出力 v]を((-)と((累乗記憶)-(10進数出力))::)にする::variable
}::control
上記のパッチは以下のようにして使用する。
定義 2進数を10進数に変換(2進数::custom-arg)
[2進数 v]を(2進数::custom-arg)にする::variables
[10進数出力 v]を(0)にする::variables
[カウンター v]を(0)にする::variables
((2進数::custom-arg)の長さ::operators)回繰り返す{
もし<((2進数::custom-arg)の(((2進数::custom-arg)の長さ)-(カウンター))番目の文字::operators)=(1)>なら{
[累乗記憶 v]を(1)にする::variables
(カウンター)回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする::variables
}::control
[10進数出力 v]を((10進出力)+(累乗記憶))にする::variables
}::control
[カウンター v]を(1)ずつ変える::variables
}::control
符号付き二進数に対応するパッチ(2進数::custom-arg)::custom//←この1ブロックを追加
減算の実装
二進数の減算を行うスクリプトの例を下記に示す。ただし、このスクリプトは非常に低効率なので、高速な演算には向いていない。もしこの処理に速度が必要な場合、工夫して高速化を図る必要がある。
定義 減算(10進入力-1)-(10進入力-2)(桁数)::custom
[一時記憶 v]を((10進入力-1::custom-arg)-(10進入力-2::custom-arg)::operators)にする::variable
もし<((一時記憶)の(1)番目の文字::operators)=[-]>なら{
10進数を2進数に変換((一時記憶)の[絶対値 v]::operators)::custom
固定長に整形する(二進数出力)((桁数::custom)-(1)::operators)::custom
2の補数を求める(二進数出力)::custom
[二進数出力 v]を((1)と(二進数出力)::operators)にする::variable
}でなければ{
10進数を2進数に変換(一時記憶)::custom
固定長に整形する(二進数出力)((桁数::custom)-(1)::operators)::custom
[二進数出力 v]を((0)と(二進数出力)::operators)にする::variable
}::control
シフト演算
シフト演算とは、任意の固定長二進数列の数値を左右に指定桁ずらす演算のことである。シフト演算には、"論理シフト演算"と、"算術シフト演算"の2つの演算方法が存在する。
論理シフト演算
論理シフト演算は単純に固定長二進数列を指定桁数ずらすだけの演算である。
例1:下記の8桁の二進数を左に1桁論理シフトする場合 11001010 ↓ 10010100 例2:下記の8桁の二進数を右に3桁論理シフトする場合 11011001 ↓ 00011011
論理シフト演算では、シフトされた結果空白になった桁は0で埋められる。
算術シフト演算
算術シフト演算では、符号桁(固定長二進数列の最上位桁)が演算結果に作用するシフト演算である。
例1:下記の8桁の二進数を左に1桁算術シフトする場合 11001010 ↓ 10010100 例2:下記の8桁の二進数を右に3桁算術シフトする場合 11001010 ↓ 11111001
算術シフト演算で左にシフトする場合、最上位桁は固定され、その次の桁から下を左に指定数シフトする。シフトされた結果空白になった桁は0で埋められる。
また、右にシフトする場合も最上位桁が固定されることは同じであるが、空白になった桁は符号桁の数値で埋められると言う違いがある。
シフト演算の実装
シフト演算を実装する例を下記に提示する。
定義 論理シフト演算(二進数)(シフト数)(シフトする向き)
[一時記憶 v]を(二進数::custom-arg)にする::variable
[スタック v]を()にする::variable
もし<(シフトする向き)=[>]>なら{
(シフト数::custom-arg)回繰り返す{
[スタック v]を((スタック)と(0))にする::variable
}::control
(((二進数::custom-arg)の長さ)-(シフト数::custom-arg))回繰り返す{
[スタック v]を((スタック)と((一時記憶)の((((スタック)の長さ)-(シフト数::custom-arg))+(1)::operators)番目の文字::operators))にする::variable
}::control
[二進数出力 v]を(スタック)にする::variable
}::control//">"記号を引数に入れると右向きにシフト
もし<(シフトする向き)=[<]>なら{
(シフト数::custom-arg)回繰り返す{
[スタック v]を((スタック)と(0))にする::variable
}::control
(((二進数::custom-arg)の長さ)-(シフト数::custom-arg))回繰り返す{
[スタック v]を(((一時記憶)の(((一時記憶)の長さ)-(((スタック)の長さ)-(シフト数::custom-arg))::operators)番目の文字::operators)と(スタック)::operators)にする::variable
}::control
[二進数出力 v]を(スタック)にする::variable
}::control//"<"記号を引数に入れると左向きにシフト
定義 算術シフト演算(二進数)(シフト数)(シフトする向き)
もし<(シフトする向き::custom-arg)=[>]>なら{
[スタック v]を((一時記憶)の(1)番目の文字::operators)にする::variable
(シフト数::custom-arg)回繰り返す{
[スタック v]を((スタック)と((一時記憶)の(1)番目の文字::operators)::operators)にする::variable
}::control
((((二進数::custom-arg)の長さ)-(シフト数::custom-arg))-(1))回繰り返す{
[スタック v]を((スタック)と((一時記憶)の((((スタック)の長さ)-(シフト数::custom-arg))+(1))番目の文字::operators)::operators)にする::variable
}::control
[二進数出力 v]を(スタック)にする
}::control
もし<(シフトする数::custom-arg)=[<]>なら{
[一時記憶 v]を(二進数::custom-arg)にする::variable
[スタック v]を()にする::variable
(シフト数::custom-arg)回繰り返す{
[スタック v]を((スタック)と(0)::operators)にする::variable
}::control
(((二進数::custom-arg)の長さ)-((シフト数::custom-arg)+(1)))回繰り返す{
[スタック v]を(((一時記憶)の((((一時記憶)の長さ)-((スタック)の長さ))+(シフト数::custom-arg))番目の文字::operators)と(スタック))にする::variable
}::control
[スタック v]を(((一時記憶)の(1)番目の文字::operators)と(スタック)::operators)にする::variable
[二進数出力 v]を(スタック)にする::variable
}::control
除算
ここでは、二進数の除算の仕方と二進数における小数の表現方法を解説する。
整数以下を割り切らない場合(余りを出す場合)
整数同士の除算で整数以下を割り切らずに余りを出す場合、今までに説明してきた定義を使用し、簡単に除算を実装することができる。以下にスクリプトの例を示す。
10進数を2進数に変換(((割られる数)/(割る数))の[切り下げ v]::operators)::custom [一時記憶 v]を(二進数出力)にする::variable 10進数を2進数に変換((割られる数)を(割る数)で割った余り)::custom
上記スクリプトの場合、商は変数"二進数出力"に格納され、余りは変数"一時記憶"に格納される。
二進数における小数表現
二進数における小数表現は"固定小数点数"と"浮動小数点数"の2種類が存在する。一般的に固定小数点数は高速に計算ができるが、表現できる小数の幅は狭い。一方浮動小数点数は広域のかなり小さい数も少ない桁で表現できるが、固定小数点数に比べ、計算に時間がかかる。
固定小数点数
固定小数点数は固定長の二進数のどこかの桁より下位の桁を小数として扱う表現方法である。
10000101(2) 例えば、上の二進数の右から4番目を1の位とすると、右から3番目以下の桁が小数部分である。 小数点以下の桁は、1の位から1つ右にずれると1/2,さらに右にずれると1/4と言うように1/2ずつ桁の重みが変化する。
固定小数点数の場合、余りを出さない除算をすることは非常に簡単である。なぜなら、各桁を右に1桁シフトするとその数値を2で割ったのと同じことになるからである。これは乗算にも言えることである。
固定小数点数の実装
固定小数点数を実装するにあたって、注意すべきことがある。それは、"固定小数点数であるかどうかの区別はプログラム側が判断することである"ということである。1001010(2)を74として処理するのか、それとも18.5として処理するのか、または、2.3125として処理するのか(つまり小数点の位置もプログラム任せ)は補数と同じくプログラムが決めることである。
定義 固定小数点数を10進数に変換する(二進数)(1の位の場所)//2進数を10進数にする
2進数を10進数に変換(二進数::custom-arg)::custom
もし<<(1の位の場所::custom-arg)=(0)>ではない>なら{
[累乗記憶 v]を(1)にする::variable
((1の位の場所::custom-arg)-(1))回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする::variable
}::control
[10進数出力 v]を((10進数出力)/(累乗記憶))にする::variable
}::control
定義 固定小数点数に変換する(10進数)(桁数)//10進数を2進数にする
[カウンター v]を(0)にする::variable
<((10進数::custom-arg)の(カウンター)番目の文字::operators)=(.)>まで繰り返す{
[カウンター v]を(1)ずつ変える::variable
}::control
もし<(((10進数::custom-arg)の((カウンター)-(1))番目の文字::operators)を(2)で割った余り::operators)=(1)>なら{
[累乗記憶 v]を(1)にする::variable
(カウンター)回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする
}::control
[一時記憶 v]を((10進数::custom-arg)*(累乗記憶))にする::variable
}でなければ{
[累乗記憶 v]を(1)にする::variable
((カウンター)-(1))回繰り返す{
[累乗記憶 v]を((累乗記憶)*(2))にする
}::control
[一時記憶 v]を((10進数::custom-arg)*(累乗記憶))にする::variable
}::control
10進数を2進数に変換(一時記憶)::custom
固定長に整形する(二進数出力)(桁数::custom-arg)::custom
浮動小数点数(書きかけの項目)
浮動小数点数は、固定長の二進数を"符号部"、"指数部"、"仮数部"に分けることで小数を表現する。現代、一般的になっている浮動小数点のフォーマットは以下の通り
0 00000000 00000000000000000000000 1 8 23 符 指 仮
符号部には正か負か(+か-か)の値が入り、指数部には10を何乗するかを指定する。残りの仮数部には仮数の絶対値が入る。
二進数の計算により発生する誤差
コンピュータープログラムでの演算は、数列表現に限界があるため誤差が発生する場合がある。今節ではプログラム中で二進数を扱う際の誤差について解説する。
丸め誤差
丸め誤差は、限られた桁において四捨五入や切り上げ、切り下げなどの操作を行うことにより発生する誤差である。例えば、10進数の"0.1"を2進数で表現しようとすると"0.000110011..."となり、固定長の幅に収めることができない。そこで、ある桁で切り下げまたは切り上げの処理を行うことで発生する切り下げまたは切り上げした桁より下位の桁との差が丸め誤差である。
桁落ち
桁落ちとは、絶対値が非常に小さい小数同士などの演算において、有効桁数が減少することで発生する誤差である。浮動小数点数では、上位の桁がゼロになると、正規化によってそれを詰め、以下の桁を "0" で強制的に詰めるので、下位の桁が信頼できないものになる。
情報落ち
情報落ちとは、絶対値の大きい数値と小さい数値の差が著しい演算を行った際に有効桁が増えすぎるために演算結果に下位の桁の情報が反映されない現象である。
桁あふれ
演算結果がプログラムにおけるデータ型の扱うことができる桁を超えた場合にそれ以上大きい桁または小さい桁を表現しきれなくなることで起こる誤差である。指定桁より多いとオーバーフロー、小さい場合はアンダーフローと呼ぶ場合がある。
