アルゴリズムの流れ図

正解は ア (a:Yの第0ビット、b:Xを1ビット左シフト,Yを1ビット右シフト)です。 筆算と同じ考え方で、 乗数 Y の各ビットを下の桁から1つずつ調べ 、1なら被乗数 X(桁をずらしたもの)を Z に足します。X=3、Y=3(2進数 11)でたどると次のようになります。 i Yの第0ビット Z X(左シフト後) Y(右シフト後) 1 1 → Z+X 0+3=3 6 1 2 1 → Z+X 3+6=9 12 0 3〜16 0(加算なし) 9 … 0 結果は Z=9=3×3 になり、正しく掛け算できています。X を左に(2倍ずつ)ずらすのは、Y の次のビットの重みが2倍になるためです。以下は誤りの選択肢でたどった例です。 Yの第0ビットは1なので、Z←(0+3) //Z=3 Xを1ビット右シフト //X=1 Yを1ビット左シフト //Y=6 i←(1+1) //i=2 Yを左にシフトすると第0ビットに0が挿入される。以後、Yの第0ビットはi>16になるまで常に0なので、加算は行われずにループ終了 Zを出力する //Z=3 Yの第15ビットは0なので加算はなし Xを1ビット左シフト //X=6 Yを1ビット右シフト //Y=1 i←(1+1) //i=2 Yを右にシフトすると第15ビットには0が挿入される。以後、Yの第15ビットはi>16になるまで常に0なので、加算は行われずにループ終了 Zを出力する //Z=0 Yの第15ビットは0なので加算はなし Xを1ビット右シフト //X=1 Yを1ビット左シフト //Y=6 i←(1+1) //i=2 Yの第15ビットは0なので加算はなし Xを1ビット右シフト //X=0 Yを1ビット左シフト //Y=12 Xが0になったので、加算処理が行われたとしてもZは0のままでループ終了 Zを出力する //Z=0

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

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

aa

bb

ア

Yの第0ビット

Xを1ビット左シフト,Yを1ビット右シフト

イ

Yの第0ビット

Xを1ビット右シフト,Yを1ビット左シフト

ウ

Yの第15ビット

Xを1ビット左シフト,Yを1ビット右シフト

エ

Yの第15ビット

Xを1ビット右シフト,Yを1ビット左シフト