Negative NumbersとSigned Negator【Turing Complete編】

2023年9月12日

Negative Numbersステージ

当ステージでは負の数が登場します。

最上位ビットを-128（＝2⁷）とすることで、8ビットが-128～127の整数値を扱えるようになります。

問題が次々に出題され、下のON・OFFを操作して、レベル3以上を達成すればクリアになります。

全部ONにすると-1（＝-128＋127）になることです。ポイントはこれを基点にして、1をOFFにすれば-2になり、2をOFFにすれば-3になります。つまり、最上位ビットがONであれば、残りのビットにてOFFになる数が増えていけば、マイナス側に大きくなっていきます。

クリアするとLevel mapから次の問題（Signed Negatorの問題）が解放されます。

補数を理解しよう

補数とは、ある数を別の数に足すことで、特定の基数（基準となる数）になる数のことを指します。一般的には、10進数と2進数（バイナリ）の補数がよく使われます。

10進数の場合の補数

・1の補数：各桁の数字を9から引いた数。例えば、10進数「1234」の1の補数は「8765」。

・9の補数：各桁の数字を10から引いた数になりますが、その後で1を足す。例えば、10進数「1234」の9の補数は、「8765」（9の補数）に1を足して「8766」になる。

2進数の場合の補数

・1の補数：各桁の数字を1から引いた数。例えば、2進数「1010」の1の補数は「0101」。各桁をビット反転（NOT演算）するだけ。

・2の補数：各桁の数字を2から引いた数になるが、その後に1を足す。例えば、2進数「1010」の2の補数は、「0101」（1の補数）に1を足して「0110」になる。ビット反転して最後に1を足したものとして考えられる。

補数は負の数の表現や減算で役立つ

補数はコンピューターサイエンスの分野で重要な概念であり、特に負の数の表現、減算において役立ちます。コンピューターの世界では2進数で数を扱うため、（2進数における）1の補数と2の補数という概念での負の数の表現について触れておきます。

例えば、1の補数の世界で-3をどう表現できるのかを調べてみます。10進数「3」の2進数「0011」です。ただし、表現範囲を4ビットとしました。これをビット反転すると1100になります。つまり、1の補数の世界では1100が-1に相当します。2の補数では、負の数を表すために、正数表現に対して、否定を取ってから1を足します。2の補数の世界で、-1は1101と表現されます。否定してから1を足したためです。同じ-1であっても、どちらの世界かによって、表現が変わってくるわけです。

補数和

「1の補数和」「2の補数和」について解説します。

2の補数和

2の補数和の方が簡単なので、こちらから説明します。2の補数和は、コンピューター内での加算や減算を行う際に使用される方法です。例えば、A＝6（0110）、B＝-3（2の補数表現：1101）の場合、A＋B＝3（0011）を求めたいとします。

1：加算する数の2の補数表現を求めます。

すでにAと「Bの2の補数表現」が与えられている場合、このステップはスキップできます。

先の例では、A＝6⇒0110（4ビット）、B＝-3⇒1101（これは-3の2の補数表現）になります。

2：2進数で加算します。

A（0110）とB（1101）を2進数で加算すると、10011になります。

3：桁上がりした分をカットします。

結果が5ビットになりましたが、もともと4ビットで計算していたので、最上位ビット（左端の1）を捨てて、残りの4ビットを取ります。結果は0011になります。これは10進数で「3」となります。これは期待の結果です。

1の補数和

1の補数和の計算は次のようになります。同様のAとBを使ってA＋Bを求めたいもとのします。

1：加算する数の1の補数表現を求めます。

すでにAと「Bの1の補数表現」が与えられている場合、このステップはスキップできます。

A＝6⇒0110（4ビット）、B＝-3⇒1100（これは-3の1の補数表現）になります。

2：2進数で加算します。

A（0110）とB（1100）を2進数で加算すると、10010になります。

3：桁上がりした分を足します。

結果が5ビットになりましたが、もともと4ビットで計算していたので、最上位ビット（左端の1）を足します。結果は0011になります。

以上のように、「2の補数和」と「1の補数和」の計算方法は異なりますが、どちらも同じ答えを得られます。

2進数の符号反転は2の補数

2進数の符号を反転させた値は、（2進数の）2の補数そのものです。

ビット演算によって2の補数を求めるなら、全ビットを反転させてから1を足します。

半減算器

半減算器（half subtracter）とは、減算をする回路です。ただし、桁借りを意味する入力はありません。

※加算器には半加算器と全加算器があったように、減算器にも半減算器と全減算器があります。

真理値表

M	S	D	Borrow
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

回路

全減算器

全減算器のブロック図は次の通りです。

真理値表

Bin （S’）	M	S	D1 （M’）	B1	D	B2	Bout
0	0	0	0	0	0	0	0
0	0	1	1	1	1	0	1
0	1	0	0	0	0	0	0
0	1	1	0	0	0	0	0
1	0	0	0	0	1	1	1
1	0	1	1	1	0	0	1
1	1	0	1	0	0	0	0
1	1	1	0	0	1	1	1

半加算器で全加算器を構築する

Signed Negatorステージ

Signed Negatorステージのゴールは、入力の値（符号つきの整数）の正負を反転させた値を出力する回路を組むことです。

入力が正の数なら負の数に変換して出力し、入力が負の数なら正の数に変換して出力します。

Signed Negatorステージを解く

1：符号を反転させる回路を設計する

符号を反転させた値は、2の補数であることを解説しました。

そして、2の補数を得るには、全ビット反転してから1を足すことで実現できることも言及しました。

2：使えるコンポーネントを把握する

これまで登場したコンポーネントを思い出して、使えそうなものを考えてください。

・8ビットを全ビット反転⇒Turing Completeでいえば、8 Bit NOTコンポーネント。

・8ビットに1を足す⇒（8ビット用の）全加算器。Turing Completeでいえば、Addコンポーネント。

右上の[1BIT]と[8BIT]アイコンを押して、使えるコンポーネントを確認します。

・[8BIT]アイコン＞[MATH]アイコン＞[ADD]アイコン･･･これがAddコンポーネント。

・[1BIT]アイコン＞[N]アイコン･･･これがNOTコンポーネント。

各コンポーネントの入出力を再確認します。

※大きいピンは8ビット用、小さいピンは1ビット用です。

3：内部回路を実装する

前段では8 Bit NOTコンポーネントに通して全ビット反転させます。それを後段のAddコンポーネントのInput 1に入れます。

また、Input 2は1固定を加えます。ただし、Input 2は大きいピンであり、直接ONコンポーネントをつなげられません。ビット数が合わないからです。そこで、8 Bit Makerを通してから接続します。

後は、Addコンポーネントの出力をそのまま出力ピンにつなげるだけです。

4：テストする

テストにパスすると、Negate（Signed Negator）コンポーネントがアンロックします。

なお、左上のLevel mapの右側の数値をクリックするたびに、交互に「+255」と「-1」に切り替わります。これは8ビット値の正負の表現法になります。最上位ビットをどう扱うかの切り替えになります。

「+255」にすると、符号なしの8ビット値、すなわち正の数だけを扱います。一方、「-1」にすると、符号ありの8ビット値、すなわち正負の数として扱います。

Addコンポーネントのキャリーインを利用する【別解】

Input 2に1を加えていますが、8ビットにするためにわざわざ8 Bit Makerを用いています。

Addコンポーネントのキャリーインは桁上げようですが、これをインクリメント用に代用する方法があります。

キャリーインとONコンポーネントはどちらも1ビットであり、直接をつなげられます。

これを実現した回路は次の通りです。

※先ほどの回路と比べてすっきりしましたが、これはキャリーインの役割を無視した使い方です。あくまで先の回路が基本であることを念頭においてください。