左シフトと加算を組み合わせて正の整数を10倍にする手順の確かめ方
基本情報技術者試験 平成29年度秋期 午前 問1 ／ 基礎理論 › 離散数学
過去問にチャレンジ
数値を2進数で表すレジスタがある。このレジスタに格納されている正の整数xを10倍にする操作はどれか。ここで，桁あふれは起こらないものとする。
- ア
xを2ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。
- イ
xを2ビット左にシフトした値にxを加算し，更に2ビット左にシフトする。
- ウ
xを3ビット左にシフトした値と，xを2ビット左にシフトした値を加算する。
- エ
xを3ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。
会話形式の解説
講師今回は、左シフトと加算を組み合わせて、レジスタの値を10倍にする手順を選ぶ問題です。注目点は「何ビット左にシフトすると何倍になるか」です。桁あふれは起こらないという条件もあるので、シフトを素直に掛け算として読み替えられます。
受験者1ビット左にシフトすると2倍になる、というのは覚えています。2ビットなら、2を足して4倍でしょうか。それとも2×2で4倍ですか。いつも計算の筋道があいまいになります。
講師結果はどちらも4倍ですが、考え方は掛け算です。1ビットごとに2倍されるので、nビットの左シフトは2のn乗倍になります。3ビットなら2×2×2で8倍です。では、2ビット左シフトしてxを足し、さらに1ビット左シフトする手順は何倍になるでしょうか。
受験者2ビット左シフトで4x、xを足して5x、最後に1ビット左シフトで2倍なので10xです。これが10倍になりますね。
講師そのとおりです。式にすると(4＋1)×2＝10です。ほかの選択肢も同じ方法で確かめましょう。前半は同じで、最後だけ2ビット左シフトする手順はどうですか。
受験者5xまでは同じで、最後が4倍なので20xです。最後のシフト量が違うだけで倍率が2倍ずれるんですね。
講師はい。次に、3ビット左シフトした値と2ビット左シフトした値を足す手順はどうでしょう。
受験者8x＋4xで12xです。x自体を足していないので、10xより2x多くなります。
講師正確です。最後に、3ビット左シフトしてxを足し、さらに1ビット左シフトする手順です。
受験者8xにxを足して9x、それを2倍して18xです。最初のシフトを3ビットにすると、10倍を通り越してしまいます。
講師これで、ちょうど10倍になるのは「2ビット左シフト、xを加算、1ビット左シフト」の手順だけだと確かめられました。ポイントは、操作の順に倍率を掛けたり足したりして、最終的な倍率を出すことです。
受験者目的の10を、10＝(4＋1)×2のように2の累乗の和と積に分けて考えればよいのですね。
講師はい。補足すると、10倍は8x＋2x、つまり3ビット左シフトした値と1ビット左シフトした値の和でも作れます。手順は1通りとは限らないので、見覚えのある形を探すより、選択肢ごとに倍率を計算するのが確実です。なお、nビットの右シフトは2のn乗で割ることに当たる点もあわせて押さえておきましょう。
まとめ
2進数では、nビットの左シフトで値が2のn乗倍になります。そのため、シフトと加算を組み合わせれば、2の累乗ではない10倍のような定数倍も作れます。xを2ビット左シフトして4x、xを足して5x、さらに1ビット左シフトすると10xになります。ほかの手順は、それぞれ20x、12x、18xになり、10倍にはなりません。操作の順に倍率を計算していけば、選択肢を確実に見分けられます。
解答・解説
正解はアです
この問題のテーマ
左シフトが値を何倍にするかを使い、加算と組み合わせて正の整数xを10倍にする手順を選ぶ問題です。
解き方の考え方
2進数では、1ビット左にシフトするたびに値が2倍になります。そのため、nビット左にシフトすると2のn乗倍です。桁あふれは起こらないという条件があるので、各選択肢を「シフト＝2の累乗を掛ける」と読み替えて、最終的な倍率を計算します。倍率がちょうど10になる選択肢が正解です。
選択肢ごとの解説
- ○ア xを2ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。アの「2ビット左シフト→xを加算→1ビット左シフト」を順に計算します。xを2ビット左にシフトすると4x、これにxを足すと5x、最後に1ビット左にシフトすると5x×2＝10xです。検算として、(4＋1)×2＝10となり、10倍の操作になっていることが確かめられます。
- ×イ xを2ビット左にシフトした値にxを加算し，更に2ビット左にシフトする。イは、アと同じく5xまでは作れます。しかし最後のシフトが2ビットなので4倍になり、5x×4＝20xです。10倍にはなりません。
- ×ウ xを3ビット左にシフトした値と，xを2ビット左にシフトした値を加算する。ウの「3ビット左シフトの値と2ビット左シフトの値の加算」は、8x＋4x＝12xです。xそのものを足していないので、10倍とは2x分ずれた結果になります。
- ×エ xを3ビット左にシフトした値にxを加算し，更に1ビット左にシフトする。エは、xを3ビット左にシフトした8xにxを足して9xとし、さらに1ビット左にシフトするので9x×2＝18xです。10倍にはなりません。
補足
10倍は8x＋2x、つまり「3ビット左シフトした値と1ビット左シフトした値の和」としても作れます。同じ倍率でも手順は1通りとは限らないので、選択肢ごとに倍率を計算して確かめるのが確実です。
POINT
- nビットの左シフトは値を2のn乗倍にし、nビットの右シフトは2のn乗で割ることに当たります。
- シフトと加算を組み合わせると、2の累乗ではない定数倍も作れます。
- 10＝(4＋1)×2のように、目的の倍率を2の累乗の和と積に分けて考えると、手順を組み立てやすくなります。
- 選択肢は操作の順に倍率を掛けたり足したりして、最終的な倍率を確かめます。