基本情報技術者 2017年 春期 午前（科目A） 問05

シフト加算による二進乗算【午前解説】

正解の理由

• 初期化で被乗数をX、乗数をY、結果をZ=0、反復カウンタi=1とする。
• 判定部で「a」を使ってYの該当ビットを調べるため、反復ごとに取り出すのはYの最下位ビット（第0ビット）。
• ビットが1なら「(Z + X) → Z」となり、さらにbでXとYをシフトする。乗算の桁合わせのためXは1ビット左シフト（桁上げ）、Yは1ビット右シフト（次のビットをLSBに移す）が必要。
• これを16回（16ビット分）繰り返せば、32ビットのZに正しい積が得られる。以上より、a は「Yの第0ビット」、b は「Xを1ビット左シフト，Yを1ビット右シフト」であるアが正解です。

解法ステップ

1. フローチャート全体を把握：初期代入、判定、加算、シフト、カウンタ増加、終了条件の流れを追う。
2. 判定部「a」が何を調べるかを特定：乗数Yのどのビットを見ているか（反復で変化するのはどのビットか）。
3. 加算の直後に行われる「b」の処理を確認：XとYをどちらの方向に何ビットシフトするかを読む。
4. ループ回数からビット方向を検証：16回で全ビットを処理するならLSB→MSBの順（右シフトで次ビットをLSBに持ってくる）。
5. 各選択肢と照合して整合する組合せを選ぶ。

選択肢別の誤答解説

• ア: ア — 正解
  Yの第0ビットを判定し、1ならZにXを加える。加算後にXを左シフト（桁上げ）しYを右シフト（次のビットをLSBへ）する処理は標準的な累算乗算に合致します。レジスタが32ビットで桁あふれにも対応します。
• イ — 誤り
  aはYの第0ビットで合っているが、bでXを右シフトしYを左シフトするのは桁合わせの方向が逆です。これではXの桁位置が下がり、正しい積になりません。
• ウ — 誤り
  aでYの第15ビット（MSB）を見るのは誤りです。MSBから処理する設計ならその後のシフト方針やループ制御が異なりますが、図はXを左、Yを右にシフトする挙動を示しておりLSB逐次処理です。
• エ — 誤り
  aが第15ビットなのと、bでX右シフト・Y左シフトという両方が盤石に間違っています。図の流れと一致しません。

よくある誤解

• 第0ビットではなく第15ビットを判断すれば良いと誤解する：一般的な下位ビットから順に処理する累算法ではLSBをチェックします。
• XとYのシフト方向を逆に理解する：Xを右シフト、Yを左シフトすると桁位置が合わず誤った結果になります。
• 符号付きと混同する：符号なし問題かつ図は論理シフトを明示しているため、符号ビットの扱い（算術シフト）は不要です。

補足コラム

• 実装イメージ（擬似コード）:

# 符号なし16ビット乗算（Zは32ビット）
X = multiplicand  # 16bit -> 32bit格納可
Y = multiplier    # 16bit
Z = 0
for i in range(16):
    if (Y & 1) == 1:   # Yの第0ビットを判定
        Z = Z + X
    X = (X << 1) & 0xFFFFFFFF  # 論理左シフト（32ビット）
    Y = (Y >> 1) & 0xFFFFFFFF  # 論理右シフト
# Zが積

• このアルゴリズムは単純で理解しやすく、ハードウェアではシフトレジスタと加算器だけで実装できます。ブースト法（Booth）などは符号付きや効率向上の別手法です。
• レジスタ幅に注意：被乗数・乗数が16ビットでも積は最大32ビットになるためZは32ビットが必要。

FAQ