Equal to ZeroとLess than Zero【NandGame編】

2023年10月20日2023年12月16日

Equal to Zeroレベル

Equal to Zeroレベルのゴールは、全ビットが0のときだけ1を出力し、そうでなければ0を出力する回路を組むことです。

本ステージでは4ビット列が与えられます。

Equal to Zeroレベルを解く

各ビットをORで使って1ビットに集約することで、次のパターンに分類できます。

• 全ビットが0のパターン→ビット値0が得られる
• その他のパターン→ビット値1が得られる。

本ステージでは全ビットが0であるときだけ1を出力させればよいので、最後にNOT（インバーター）回路を通せばよいのです。

この回路は4つのコンポーネントしか使っておらず、Nand数も10 Nandと十分に少ない値になっています。実際のところ最適化済みの回路です。

このアプローチは簡単に16ビットにも拡張できます。

XOR回路が不一致回路であることを利用する【別解】

XOR回路は真理値表を見ると、入力ビットが同一のときに0を出力し、そうでないときに1を出力します。つまり、XOR回路は不一致回路といえます。

A	B	Z（＝XOR (A,B)）
0	0	0
0	1	1
1	0	1
1	1	0

定数0と一致するということは、定数1と不一致することと同値です。

そこで、各桁のビット値と定数1のXORを取り、1を出力していれば当該ビット値は0です。

すべての桁のXORの結果を集めて、すべてが1ならすべてのビットが0となります。すべてが1かどうかはANDを使えばよいだけです。

ただし、与えられたコンポーネントに定数0や定数1のコンポーネントがないので、nandコンポーネントを代用します。入力になにもつなげなければ、常に1を出力するからです。

この回路は8コンポーネント、23 Nandです。

より少ないコンポーネントの回路が存在することがヒントとして記載されます。

Less than Zeroレベル

Less than Zeroステージのゴールは、16ビットの入力値が0以上なら0を出力し、0未満なら1を出力する回路を組むことです。

入力の正負を判定する回路そのものです。入力が正の数（ただし0を含む）なら0を出力、負の数なら1を出力するわけです。

＊正の数は本来0を含まないので、厳密にいうなら自然数を判定する回路と言い換えられます。

Less than Zeroレベルを解く

本ステージで使えるのはsplitterコンポーネントのみです。

符号ありのビット列は最上位ビットを特別扱いします。最上位ビットが0なら正の数（0を含むものとする）、1なら負の数を意味します。

このことを考慮すれば入力の16ビットをsplitterコンポーネントで各桁に分離し、最上位ビットをそのままOutput端子に接続すればよいのです。