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

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

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

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

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

Signed Less【Turing Complete編】

2023年9月16日

Signed Lessステージ

Signed Lessステージのゴールは、1番目の入力が2番目の入力より小さければONを出力する回路を組むことです。

ただし、入力バイトデータは符号あり(Signed)として解釈するものとします。

※Unsigned Lessステージでは符号なしの入力バイトデータを扱いましたが、本ステージでは符号ありを扱います。

Signed Lessステージを解く

1:ナンバーフォーマットを符号ありに切り替える

ナンバーフォーマットを切り替えるアイコンを押して「-1」にしておきます。これでテスト時に10進数が負の数が表示されるようになります。

※この設定はあくまで表示のためであり、回路が正しければステージはクリアできます。ただし、この設定をしておけば、回路の挙動を理解するための助けになります。

2:回路の設計を検討する

最上位ビットが0であれば、Unsigned Lessステージの回路のままで、本ステージのゴールを満たします。

問題は最上位ビットが1のときになります。最上位ビットが1であれば、-128から-1までのいずれかの値を取ります。

最上位ビットだけ1のビット列、すなわち1000 0000bとXOR演算するというテクニックを採用します。

天下り的ですが、次のような回路を考えます。Unsigned Less回路の前段に、2入力とも1000 0000bとXORする回路が組み込まれています。

Aは上のInput端子のビット列、Bは下のInput端子のビット列、C=1000 0000bとします。

XORの性質から、$a \, \text{XOR} \, 0 =a, \, a \, \text{XOR} \, 1 = \bar{a}$が成り立ちます。ただし、$a, \, b \in \{0, \,1\}$とします。

Cは最上位が1、それ以外の桁が0と固定であることを考慮します。

すると、X(=XOR(A, C))とZ(=XOR(C, B))は、最上位(1桁のみ)だけがビット反転し、他の桁は変化しません。

一方、Y(=NOT(X))はXのビット反転です。言い換えると、最上位だけが変化せず、他の桁はビット反転します。

ケースABXYZAdd(Y, Z)のCarry OutピンAdd(Y, Z)のResultピン
A=B0110 0110b
(=102d)
0110 0110b
(=102d)
1110 0110b0001 1001b1110 0110b01111 1111b
A=B1000 1001b
(=119d)
1000 1001b
(=119d)
0000 1001b1111 0110b0000 1001b01111 1111b
A>B0110 0110b
(=102d)
0001 1101b
(=29d)
1110 0110b0001 1001b1001 1101b01011 0110b
A>B1111 0000b
(=-16d)
1001 0101b
(=-107d)
0111 0000b1000 1111b0001 0101b01010 0100b
A<B0010 0001b
(=33d)
0101 1100b
(=92d)
1010 0001b0101 1110b1101 1100b10011 1010b
A<B1110 0011b
(=-29)
1111 0000b
(=-16)
0110 0011b1001 1100b0111 0000b10000 1100b
修正版の回路

※最上位ビットが1なら負の数であり、負の数のケースもカバーするようにしました。

確かに「A<B」のケースのみで、出力がONになっています。

※証明したわけではなく、具体的な数値からの予想であり、一般化を期待できます。より具体例をたくさん試すのは、シミュレーターのテストに任せることにします。なお、この時点で予想外であれば、テスト以前の問題であり、回路の設計が間違っていることになります。

3:回路を実装する

回路を組むと次のようになります。

ちなみに、XORコンポーネントとNOTコンポーネントのセットは、XNORコンポーネントに置き換えられます。

4:テストする

クリアすると、Signed Lessコンポーネントをアンロックします。

入力の最上位ビットに注目した回路を組み込む【別解】

Aは上のInput、Bは下のInputとします。C、Xを回路の中間状態、Yを出力値とします。

次に示す4パターンに分類します。

ケースパターン
「Aが正」かつ「Bが正」[1]ここでいう正とはゼロ以上を意味するものとします。
「Aが正」かつ「Bが負」
「Aが負」かつ「Bが正」
「Aが負」かつ「Bが負」
4ケースとそのパターン

[1]ケース①の場合

Unsigned Lessステージと同じ状況なので、「A<B」のときにXはON(=1)になります。

AとBが正ということは、A’=B’=0です。

C=XOR(A’, B’)=XOR(0, 0)=0 【確定】

XORの公式$a \, \text{XOR} \,0=a$により、Yは「A<B」のときにONになります。

よって、本ステージのゴールを満たします。

[2]ケース②の場合

必ず「A>B」であり、本ステージのゴールを満たすには出力は0でなければなりません。

Aが8 Bit NOTコンポーネントを通過した時点で、最上位ビットは1になります。Bは最初から最上位ビットが1です。これら2つのビット列をADD演算すると必ず桁上がりが発生します。つまり、Carry Outピンが1、すなわちX=1になります。

Aが正、Bが負ということは、A’=0、B’=1になります。

C=XOR(A’, B’)=XOR(0, 1)=1 【確定】

XORの公式$a \, \text{XOR} \, 1= \bar{a}$により、$Y=\bar{X}=\bar{1}=0$になります。

確かに0を出力することを確認できました。

[3]ケース③の場合

必ず「A<B」であり、本ステージのゴールを満たすには出力は1でなければなりません。

Aが8 Bit NOTコンポーネントを通過した時点で、最上位ビットは0になります。Bは最初から最上位ビットは0です。これら2つのビット列をADD演算すると必ず桁上がりが発生しません。つまり、Carry Outピンが0、すなわちX=0になります。

Aが負、Bが正ということは、A’=1、B’=0になります。

C=XOR(A’, B’)=XOR(1, 0)=1 【確定】

XORの公式$a \, \text{XOR} \, 1= \bar{a}$により、$Y=\bar{X}=\bar{0}=1$になります。

確かに1を出力することを確認できました。

[4]ケース④の場合

負の数の世界では、(最上位ビットを除いて)上位のビットがONであれば、より大きい値になります。

※正の数の世界と同じになります。

例えば、1100 0000b=-64、1010 0000b=-96

つまり、Unsigned Less回路に対して2つの負の数を入力に与えても、「A<B」のときにXはON(=1)になります。

ところで、AとBが負ということは、A’=B’=1です。

C=XOR(A’, B’)=XOR(1, 1)=0 【確定】

XORの公式$a \, \text{XOR} \,0=a$により、Yは「A<B」のときにONになります。

よって、本ステージのゴールを満たします。

ゆえに、すべてのケースにおいて、ゴールを満たすので、この回路はSigned Less回路になることがわかります。

もう少し複雑にしたバージョン【別解2】

References

References
1 ここでいう正とはゼロ以上を意味するものとします。