応用情報技術者 2010年 春期 午前2 問05
問題文
流れ図は、シフト演算と加算の繰返しによって 2進整数の乗算を行う手順を表したものである。この流れ図中の a, bの組合せとして、適切なものはどれか。ここで、乗数と被乗数は符号なしの 16ビットで表される。X, Y, Z は32ビットのレジスタであり、けた送りには論理シフトを用いる。最下位ビットを第0ビットと記す。
選択肢
ア：（正解）
イ：
ウ：
エ：
2進整数の乗算（シフト演算と加算）【午前2 解説】
要点まとめ
- 結論：乗数の最下位ビット（第0ビット）を判定し、被乗数を左シフト、乗数を右シフトする操作が正しい。
- 根拠：2進乗算は乗数の各ビットを順にチェックし、1なら被乗数を加算、次に被乗数を左シフト、乗数を右シフトして次のビットへ進む。
- 差がつくポイント：符号なし16ビットの乗算で、論理シフトを用い、乗数のビット判定は必ず最下位ビットから行う点を理解しているか。
正解の理由
選択肢アは「a：Yの第0ビット」「b：Xを1ビット左シフト、Yを1ビット右シフト」となっており、これは典型的な2進乗算のアルゴリズムに合致します。乗数Yの最下位ビットを判定し、1なら被乗数Xを加算。次にXを左に1ビットシフトし、Yを右に1ビットシフトして次のビットを処理します。これにより、乗数のビットを順に処理しながら乗算を行う流れ図の動作と一致します。
よくある誤解
乗数の判定ビットを最上位ビット（第15ビット）と誤解しやすいですが、2進乗算は最下位ビットから順に処理します。シフト方向も逆に覚えると誤答の原因になります。
解法ステップ
- 乗数Yの最下位ビット（第0ビット）を判定する。
- 判定ビットが1なら被乗数Xを加算レジスタZに加える。
- 被乗数Xを1ビット左シフト（桁上げ）。
- 乗数Yを1ビット右シフト（次のビットへ移動）。
- カウンタiを1増やし、16回繰り返す。
- 16回繰り返したら結果Zを出力し終了。
選択肢別の誤答解説
- イ：乗数Yを左シフトし、被乗数Xを右シフトするのは乗算の流れと逆で誤り。
- ウ：乗数の判定を第15ビットにしているため、最下位ビットから順に処理するアルゴリズムと合わない。
- エ：ウと同様に判定ビットが第15ビットで、シフト方向も逆で誤り。
補足コラム
2進乗算は「加算＋シフト」の繰り返しで実装される基本的なアルゴリズムです。符号なし整数の場合、論理シフトを用いてビットをずらし、乗数のビットを順に処理します。符号付きの場合は算術シフトや符号拡張が必要になるため注意が必要です。
FAQ
Q: なぜ乗数の最下位ビットから判定するのですか？
A: 最下位ビットから順に処理することで、加算とシフトの繰り返しで正しい乗算結果が得られるためです。
A: 最下位ビットから順に処理することで、加算とシフトの繰り返しで正しい乗算結果が得られるためです。
Q: 被乗数を左シフトする理由は？
A: 被乗数を左にシフトすることで、次のビットに対応した重み（2倍、4倍…）を表現し、正しい乗算結果を作ります。
A: 被乗数を左にシフトすることで、次のビットに対応した重み（2倍、4倍…）を表現し、正しい乗算結果を作ります。
関連キーワード: 2進乗算、シフト演算、論理シフト、符号なし整数、流れ図、加算繰り返し
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！