過去問解きまくり研究所

平成29年度 春期 午前 問5

アルゴリズム

論理シフトに関する問題

次の流れ図は，シフト演算と加算の繰返しによって2進整数の乗算を行う手順を表したものである。この流れ図中の a，b の組合せとして，適切なものはどれか。ここで，乗数と被乗数は符号なしの16ビットで表される。X，Y，Z は32ビットのレジスタであり，桁送りには論理シフトを用いる。最下位ビットを第0ビットと記す。

流れ図:

開始
 ↓
被乗数 → X ／ 乗数 → Y ／ 0 → Z ／ 1 → i
 ↓
（合流点）◀────────────────────┐
 ↓                              │
判定  ［ a ］ : 1                │
 ├─ ≠ のとき ──────┐           │
 │ ＝ のとき        │           │
 ↓                  │           │
(Z＋X) → Z          │           │
 ↓◀─────────────────┘           │
［ b ］                          │
 ↓                              │
(i＋1) → i                       │
 ↓                              │
判定  i : 16                     │
 ├─ ≦ のとき ────────────────────┘
 └─ ＞ のとき ↓
Z を出力する
 ↓
終了

選択肢は原典では a・b の2列の表。

答えと解説を見る

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

解説

乗数の最下位を見て足し、被乗数を左へ、乗数を右へ送ります。

筆算の掛け算を、そのまま二進の桁で行う手順です。乗数の下から一桁ずつ見て、立っていれば被乗数を足します。立っていなければ足さずに、次の桁へ進みました。一桁進むごとに、被乗数を論理シフトで左へ一つ送ります。位が一つ上がるので、足す重みが二倍になるからです。同時に乗数を右へ一つ送り、次に見る桁を最下位へ持ってきます。こうすれば、いつも第〇ビットだけを見れば足ります。だから判定はYの第〇ビット、送りは左と右の組が当たりました。送る向きを入れ替えると、重みの付き方が逆になります。被乗数を右へ送れば、位が上がるどころか下がってしまいました。判定を第十五ビットに置く形も、見る桁が上から下へ逆に進みます。乗数を左へ送ってもYは三十二ビットなので桁は落ちませんが、被乗数を右へ送れば重みが下がる向きになり、足し合わせが合いません。どちらへ送るかは、足す重みが増える向きで決まります。

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

出典：平成29年度 春期 基本情報技術者試験 午前 問5

この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）