シフトと加算による2進乗算の流れ図、調べるビットとシフトの向き
基本情報技術者試験 平成29年度春期 午前 問5 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
次の流れ図は、シフト演算と加算の繰返しによって2進整数の乗算を行う手順を表したものである。この流れ図中のa, bの組合せとして、適切なものはどれか。ここで、乗数と被乗数は符号なしの16ビットで表される。X, Y, Zは32ビットのレジスタであり、桁送りには論理シフトを用いる。最下位ビットを第0ビットと記す。
- ア
a：Yの第0ビット，b：Xを1ビット左シフト，Yを1ビット右シフト
- イ
a：Yの第0ビット，b：Xを1ビット右シフト，Yを1ビット左シフト
- ウ
a：Yの第15ビット，b：Xを1ビット左シフト，Yを1ビット右シフト
- エ
a：Yの第15ビット，b：Xを1ビット右シフト，Yを1ビット左シフト
会話形式の解説
講師この問題は、シフトと加算だけで掛け算をする流れ図です。見るところは2つで、乗数Yのどのビットを毎回調べるかと、被乗数XとYをそれぞれどちらへずらすかです。iを1から16まで進めるので、ループは16回まわります。
受験者計算の流れ図は追うのに時間がかかるので苦手です。そもそも、シフトと足し算だけでどうして掛け算になるのかがよく分かっていません。
講師10進の筆算と同じ考え方です。2進数では、乗数の第nビットが1なら「被乗数×2のn乗」を積に足し、0なら何も足しません。これを全ビット分くり返して合計すると積になります。
受験者では「2のn乗倍」はどうやって作るのですか。
講師論理シフトを使います。論理シフトは、ずらして空いたビットに0を入れるシフトです。左へ1ビットずらすと値は2倍、右へ1ビットずらすと1/2（端数は切り捨て）になります。ですから、Xをループのたびに左シフトすれば、重みが2倍、4倍と上がっていきます。
受験者Xは左シフトなのですね。そうなると、Xを右シフトする組合せは外れそうです。
講師そう考えてよいです。次はYです。流れ図では毎回同じ位置のビットを調べています。同じ位置のまま乗数の全ビットを順に見るには、どうすればよいと思いますか。
受験者調べる位置へYのビットを1つずつ送り込めばよいと思います。第0ビットを調べるなら、Yを右へずらすと次の桁が第0ビットに来ます。
講師そのとおりです。下の桁から順に第0ビットへ来て、同時にXが2倍ずつになるので、Yの第nビットを調べるときのXはちょうどX×2のn乗です。「第0ビットを調べ、Xを左シフト、Yを右シフト」が正解の組合せです。X=3、Y=3（2進で11）で追ってみましょう。
受験者1回目は第0ビットが1なのでZ=3になり、そのあとXは6、Yは1になります。2回目も第0ビットが1なのでZ=3+6=9になり、Yは0です。3回目以降は足されないのでZ=9のままです。3×3=9で合っています。
講師正しく追えています。では、第15ビットを調べて、Xを左シフト、Yを右シフトする組合せはどうでしょう。シフトの向きは正解と同じです。
受験者向きが同じなら、うまくいきそうにも見えます。
講師そこが引っかけです。Yを右へずらすと、第15ビットには第16ビットの値が入ってきます。乗数は16ビットで上位側は0なので、2回目以降に調べる第15ビットは常に0です。調べられるのは最上位ビットだけで、そのとき足すXも2の15乗倍になっていません。Y=3なら第15ビットは0なので、Z=0です。
受験者調べる位置とずらす向きが合っていないと、ビットが届かないのですね。第15ビットを調べてYを左へずらす組合せは、上の桁から順に見ることになりますか。
講師はい。ただ、Xは右へずれて小さくなっていくので、上の桁ほど大きく足すという重み付けと合いません。X=3、Y=3では、Yの1が第15ビットに届くのは15回目と16回目ですが、Xは2回の右シフトで0になっているので、Z=0です。
受験者残りの、第0ビットを調べてYを左へずらす組合せは、第0ビットに0しか入ってこないので、足すかどうかが決まるのは最初の1回だけですね。X=3、Y=3ならZ=3で止まります。
講師そのとおりです。Xを右へずらす向きも逆です。まとめると、毎回同じビットを調べる流れ図では、その位置へビットを送り込む向きにシフトさせるのが要点です。迷ったら、今のように小さな値で追跡すると確実に確かめられます。
まとめ
シフトと加算による2進乗算は、乗数の第nビットが1のときに被乗数×2のn乗を積に足す、筆算と同じ仕組みです。論理シフトでは左へ1ビットずらすと2倍、右へ1ビットずらすと1/2になり、空いたビットには0が入ります。この流れ図は毎回同じ位置のビットを調べるので、Yの第0ビットを調べ、Yを右シフトして下の桁から順に送り込み、Xを左シフトして重みを2倍ずつにする組合せが適切です。X=3、Y=3で追跡するとZ=9となり、3×3と一致することを確かめられます。ほかの組合せでは、ビットが調べる位置に届かないか、重み付けが逆になります。
解答・解説
正解はアです
この問題のテーマ
シフトと加算を繰り返す符号なし2進整数の乗算で、乗数のどのビットを調べ、被乗数と乗数をどちらへシフトするかを流れ図から決める問題です。
解き方の考え方
筆算と同じく、乗数Yのビットが1のときだけ、そのビットの重みに合わせてずらした被乗数XをZに足すと積になります。流れ図ではiを1から16まで進めるので、ループは16回です。毎回同じ位置のビットを見ながら、Yの全ビットを下位から順にその位置へ送り込み、同時にXの重みを2倍にしていく組合せを探します。最後にX=3、Y=3のような小さな値で追跡して確かめます。
選択肢ごとの解説
- ○ア a：Yの第0ビット，b：Xを1ビット左シフト，Yを1ビット右シフト第0ビットを調べてからYを右へ1ビットずらすと、次のループでは1つ上の桁が第0ビットに来ます。Xを左へ1ビットずらすと値が2倍になるので、Yの第nビットを調べるときのXはX×2のn乗です。X=3、Y=3(11)で追うと、1回目にZ=3、Xは6、Yは1になり、2回目にZ=3+6=9、Yは0になります。3回目以降は足されないのでZ=9となり、3×3=9と一致します。
- ×イ a：Yの第0ビット，b：Xを1ビット右シフト，Yを1ビット左シフトYを左へずらすと第0ビットには0しか入らないので、加算されるかどうかが決まるのは最初の1回だけです。Xを右へずらす向きも、上の桁ほど重みを大きくする乗算とは逆です。X=3、Y=3で追うと、1回目にZ=3となり、その後は加算が起きないのでZ=3のままです。
- ×ウ a：Yの第15ビット，b：Xを1ビット左シフト，Yを1ビット右シフトYを右へずらすと、第15ビットには第16ビットの値が入ります。乗数は16ビットで上位側は0なので、2回目以降に調べる第15ビットは常に0です。そのため調べられるのは乗数の最上位ビットだけで、しかもそのとき足すXは2の15乗倍されていません。Y=3は第15ビットが0なので、Z=0になります。
- ×エ a：Yの第15ビット，b：Xを1ビット右シフト，Yを1ビット左シフトYを左へずらしながら第15ビットを見ると、乗数を上の桁から順に調べることになります。ところがXは右へずれて小さくなっていくので、上の桁ほど大きく足すという重み付けと合いません。X=3、Y=3では、Yの1が第15ビットに届くのは15回目と16回目ですが、Xは2回の右シフトで0になっているので、Z=0になります。
POINT
- 乗数の第nビットが1なら、被乗数×2のn乗を積に加えるのが2進乗算の基本です。
- 論理シフトでは、左へ1ビットずらすと2倍、右へ1ビットずらすと1/2(切り捨て)になり、空いたビットには0が入ります。
- 毎回同じビットを調べる流れ図では、調べる位置へビットを順に送り込む向きにシフトさせます。第0ビットを調べるなら右シフトです。
- 穴埋めの流れ図は、小さな値で実際に追跡すると確実に確かめられます。