平成22年度 春期 午前 問5

✓ これが正解アa：Y の第 0 ビット ／ b：X を 1 ビット左シフト，Y を 1 ビット右シフト

解説

見る桁は最下位、X は左へ Y は右へ送ります。

この流れ図は、2 進数の筆算をそのまま機械の手順に直したものです。筆算では乗数の桁を下から 1 本ずつ見て、その桁が 1 なら被乗数を答に足し、次の桁へ進むときに被乗数を 1 つ左へずらしました。流れ図もこの順をなぞっており、判定が乗数のどの桁を見るか、そして次の繰返しへ進む前にレジスタをどちらへ送るか、という 2 か所が空欄になっています。正解は、見る桁を乗数側の第 0 ビットとし、被乗数側の X を 1 ビット左シフト、乗数側の Y を 1 ビット右シフトする組です。Y を右へ送りながら見終わった桁を捨てていくので、見る場所はいつも最下位のままでよく、X を左へ送ることで足し込む値の桁が 1 つずつ上がります。けた送りには論理シフトを用いるため、押し出された反対側には 0 が入ってきます。被乗数 5、乗数 3 で追うと、最下位が 1 なので 5 を足し、X が 10、Y が 1 になり、また最下位が 1 なので 10 を足して合計 15 となり、5 と 3 の積に一致します。繰返しは 1 から 16 まで回るので、乗数の 16 ビットをちょうど使い切ります。

ほかの選択肢はなぜ違うのか

• イa：Y の第 0 ビット ／ b：X を…：見る桁を最下位にした点は合っていますが、二つのレジスタを送る向きが互いに逆です。足し込む値が桁を下げながら小さくなり、まだ見ていない乗数の桁は反対側へ押し出されて消えてしまいます。
• ウa：Y の第 15 ビット ／ b：X …：送る向きは合っていますが、判定する位置を最上位に置いています。右へ送ると最上位には 0 が入ってくるだけなので、最初の 1 回を除いて乗数の桁を読み取れず、正しい積は得られません。
• エa：Y の第 15 ビット ／ b：X …：判定する位置を最上位に取り、そのうえで送る向きも二つとも入れ替えた形です。位置と向きの両方が流れ図の作りと噛み合わないため、被乗数の桁も乗数の桁も正しく進みません。