Shift【Turing Complete編】
はじめに
いつもブログをご覧いただきありがとうございます。
FIRE生活中のIPUSIRONです😀
ビットシフト操作
後日追加予定。
Shiftステージ
Shiftステージのゴールは、8ビット用のシフト回路を組むことです。
最初に入力したビット列に対して、2番目の入力で指定した値だけ左シフトします。
・8ビットの枠から外れた分は切り捨て。
・シフト後に空く桁はOFF（0）で埋める。
| 入力 | ・左上のInput端子（VALUE端子）：シフト対象のビット列。8ビット。 ・右上のInput端子（SHIFT BY端子）：シフトする回数。8ビット。ただし、最大値は7とする。 |
| 出力 | ・Output端子：左シフトした結果。8ビット。 |
シフト演算には論理シフトと算術シフトがありますが、今回は論理シフトになります。
Shiftステージを解く
1回左シフトすると算術的には2倍になるという事実を使ってみます。
1：ナンバーフォーマットを16進数に切り替える
ステージのクリアには直接影響しませんが、テスト時に流れるデータがわかりやすいようにナンバーフォーマットを切り替えます。「FF」となっていれば、流れるデータが2桁の16進数になります。
2：回路の設計方針を検討する
乗算回路はまだないので、加算回路で2倍を実現します。
「計算対象を2倍すること」と「計算対象の数同士を足し合わせること」では同じ結果が得られます。
・0回左シフト（何もしない）⇒「Valueのまま」
・1回左シフト（1ビット分左シフト）⇒「Valueの2倍（＝Value’）」⇒「Value＋Value」
・2回左シフト（2ビット分左シフト）⇒「Valueの2倍の2倍」⇒「Valueの22倍」⇒「Value’の2倍（＝Value"）」⇒「Value’＋Value’」
・3回左シフト（3ビット分左シフト）⇒「Valueの2倍の2倍の2倍」⇒「Valueの23倍」⇒「Value"の2倍（＝Value"’）」⇒「Value"＋Value"」
･･･
・7回左シフト（7ビット分左シフト）⇒「Valueの27倍」
以上でビット操作する処理は大丈夫そうです。
次にそれをどうやって取り出すのかという点について考えます。
これまでたくさんの回路を組んできた中で自然と採用していたテクニックがあります。「全パターンを計算して、どの計算結果を流すのかをスイッチで制御する」というテクニックです。パターン数が10未満といった少数の場合に有効といえます。全パターンを計算するのは効率が悪いですが、回路がすっきりします。
スイッチの制御については、「8 Bit Splitter＋3 Bit decoder」のペアで得られたワイヤー群を活用します。このワイヤー群のうち1本だけにON信号が流れます。つまり、ワイヤーにスイッチをつなげておけば、全パターンのスイッチの1つだけがONになり、1つの計算結果だけを取り出せるというわけです。
3：回路を実装する
8ビット用のAddコンポーネントを使います。このステージ以降、コンポーネントの右上に数字が振ってある赤丸があります。これは対象データのビット数を意味します。
桁上げなどを気にする必要がないので、Input 1ピン、Input 2ピン、Resultピンだけを使います。
4：テストする
テストにパスすると、ステージクリアになります。
次の4つのコンポーネントがアンロックします。
| コンポーネント名 | コンポーネントの刻印 | 動作 |
|---|---|---|
| 8 Bit Shift left | SHL | 左シフト演算 |
| 8 Bit Shift right | SHR | 右シフト演算 |
| 8 Bit Rotate left | ROL | 左ローテート演算 |
| 8 Bit Rotate right | ROR | 右ローテート演算 |
8 Bit Splitterと8 Bit Maker間のワイヤーをずらして倍々を実現する【別解】
この別解でも、1回左シフトすると算術的には2倍になるという事実を使います。
ただし、バイトデータ用のAddコンポーネントを使用しません。
代わりに、バイトデータを8ビットに分離し、ワイヤーを1つずらした状態でバイトデータに戻すのです。以前Double the Numberステージで使ったテクニックの応用になります。
https://akademeia.info/?p=28782まずは1ビット左シフトする回路を考えます。
・8 Bit Splitterコンポーネントの最下位ビットは、8 Bit Makerの2番ピン（2の位のピン）につながる。1ビット左シフトした結果、1桁目が2桁目に移動するため。
･･･
・8 Bit Splitterコンポーネントの7番ピンは、8 Bit Makerの8番ピン（最上位桁のピン）につながる。1ビット左シフトした結果、7桁目が8桁目に移動するため。
・8 Bit Splitterコンポーネントの最上位桁のピンは不使用。なぜなら1ビット左シフトすると最上位ビットは切り捨てられるから。
次に、2ビット左シフトする回路を考えます。さらに1本ずらします。
同様にして、7ビットシフトまでサポートする回路にします。
0ビットシフトは変化なしなので、8 Bit Splitterと8 Bit Makerを通しても意味がありません。処理的には問題になりません。しかし、回路のスペースを圧迫し、不要な回路が増えるので、今回は避けました。
後は、スイッチで計算結果を1つだけ取り出すようにします。
