平成22年春期試験問題 午前Ⅰ 問2

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

正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
流れ図を見ると、被乗数がX、乗数がY、結果としてZを出力するので「X × Y = Z」が成立すれば良いことがわかります。

細かな説明がない流れ図の穴埋めでは論理的に答えを導くのは難しいので、XおよびYにトレースが簡単な数値を設定して、出力Zが適切な値かどうかで正しい組合せを探すのが確実な解法です。ここではX=3,Y=3を使います(16ビット表記だと「0000 0000 0000 0011)。また、あるビット列を左に1ビットシフトすると2倍、右に1ビットシフトすると1/2したのと同じになります(ビットあふれは無視します)。
    1. Yの0ビット目は1なので、Z←(0+3) //Z=3
    2. Xを1ビット左シフト //X=6
    3. Yを1ビット右シフト //Y=1
    4. i←(1+1) //i=2
    5. Yの第0ビットは1なので、Z←(3+6) //Z=9
    6. Xを1ビット左シフト //X=12
    7. Yを1ビット右シフト //Y=0
    8. 以後、Yの第0ビットはi>16になるまで0なので、加算は行われずにループ終了
    9. Zを出力する //Z=9
    1. Yの第0ビットは1なので、Z←(0+3) //Z=3
    2. Xを1ビット右シフト //X=1
    3. Yを1ビット左シフト //Y=6
    4. i←(1+1) //i=2
    5. Yを左にシフトすると第0ビットに0が挿入される。以後、Yの第0ビットはi>16になるまで常に0なので、加算は行われずにループ終了
    6. Zを出力する //Z=3
    1. Yの第15ビットは0なので加算はなし
    2. Xを1ビット左シフト //X=6
    3. Yを1ビット右シフト //Y=1
    4. i←(1+1) //i=2
    5. Yを右にシフトすると第15ビットには0が挿入される。以後、Yの第15ビットはi>16になるまで常に0なので、加算は行われずにループ終了
    6. Zを出力する //Z=0
    1. Yの第15ビットは0なので加算はなし
    2. Xを1ビット右シフト //X=1
    3. Yを1ビット左シフト //Y=6
    4. i←(1+1) //i=2
    5. Yの第15ビットは0なので加算はなし
    6. Xを1ビット右シフト //X=0
    7. Yを1ビット左シフト //Y=12
    8. Xが0になったので、加算処理が行われたとしてもZは0のままでループ終了
    9. Zを出力する //Z=0
唯一"3×3"の正しい結果である"9"を出力する「ア」の組合せが適切とわかります。

このアルゴリズムを一言で言うならば、Yの第nビットが1であれば、ZにX×2nを加算する処理を繰り返すものということになります。

おまけとしてこのアルゴリズムをJavaScriptで実装したソースプログラムを掲載します。実行環境で数値やシフト部分を変えてお試しください。

Pagetop