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

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

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

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

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

Equal to ZeroとLess than Zero【NandGame編】

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回路は不一致回路といえます。

ABZ(=XOR (A,B))
000
011
101
110
XOR回路の真理値表

定数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端子に接続すればよいのです。