当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

Negative NumbersとSigned Negator【Turing Complete編】

Negative Numbersステージ

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

最上位ビットを-128(=27)とすることで、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)とは、減算をする回路です。ただし、桁借りを意味する入力はありません。

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

真理値表

MSDBorrow
0000
0111
1010
1100
半減算器の真理値表

回路

全減算器

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

真理値表

Bin
(S’)
MSD1
(M’)
B1DB2Bout
00000000
00111101
01000000
01100000
10000111
10111001
11010000
11100111
全減算器の真理値表

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

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ビットであり、直接をつなげられます。

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

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