HOME»情報セキュリティスペシャリスト平成22年春期»午前T 問2
情報セキュリティスペシャリスト平成22年春期 午前T 問2
午前T 問2
流れ図は,シフト演算と加算の繰り返しによって,2進整数の乗算を行う手順を表したものである。この流れ図中のa,bの組合せとして,適切なものはどれか。ここで,乗数と被乗数は符号なしの16ビットで表される。X,Y,Zは32ビットのレジスタであり,けた送りは論理シフトを用いる。最下位ビットを第0ビットと記す。

- [この問題の出題歴]
- 応用情報技術者
平成22年春期 問5と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
XおよびYにトレースが簡単な数値を設定して、出力Zが適切な値かどうかで正しい組合せを導きます。ここではX=3,Y=3とすることにします。X,Yともにビット表記では011です。またあるビット列を左に1ビットシフトすると2倍、右に1ビットシフトすると1/2したのと同じになります。(ビットあふれは無視します)
このアルゴリズムを一言で言うならば、Yの第nビットが1であれば、ZにX×2nを加算する処理を繰り返すものということになります。
おまけとしてこのアルゴリズムをJavaScriptで実装したソースプログラムを掲載します。実行環境で数値やシフト部分を変えてお試しください。
- Yの0ビット目は1なので、Z←(Z+X) //Z=3
- Xを1ビット左シフト //X=6
- Yを1ビット右シフト //Y=1
- i←(i+1) //i=1
- Yの第0ビットは1なので、Z←(Z+X) //Z=9
- Xを1ビット左シフト //X=12
- Yを1ビット右シフト //Y=0
- 以後、Yの第0ビットはi>16になるまで0なので、加算は行われずにループ終了
- Zを出力する //Z=9
- Yの第0ビットは1なので、Z←(Z+X) //Z=3
- Xを1ビット右シフト //X=1
- Yを1ビット左シフト //Y=6
- i←(i+1) //i=1
- Yを左にシフトすると第0ビットに0が挿入される。以後、Yの第0ビットはi>16になるまで常に0なので、加算は行われずにループ終了
- Zを出力する //Z=3
- Yの第15ビットは0なので加算はなし
- Xを1ビット左シフト //X=6
- Yを1ビット右シフト //Y=1
- i←(i+1) //i=1
- Yを右にシフトすると第15ビットには0が挿入される。以後、Yの第15ビットはi>16になるまで常に0なので、加算は行われずにループ終了
- Zを出力する //Z=0
- Yの第15ビットは0なので加算はなし
- Xを1ビット右シフト //X=1
- Yを1ビット左シフト //Y=6
- i←(i+1) //i=1
- Yの第15ビットは0なので加算はなし
- Xを1ビット右シフト //X=0
- Yを1ビット左シフト //Y=12
- Xが0になったので、加算処理が行われたとしてもZは0のままでループ終了
- Zを出力する //Z=0
このアルゴリズムを一言で言うならば、Yの第nビットが1であれば、ZにX×2nを加算する処理を繰り返すものということになります。
おまけとしてこのアルゴリズムをJavaScriptで実装したソースプログラムを掲載します。実行環境で数値やシフト部分を変えてお試しください。