離散数学 (全101問中7問目)

No.7

ある整数値を,負数を2の補数で表現する2進表記法で表すと最下位2ビットは"11"であった。10進表記法の下で,その整数値を4で割ったときの余りに関する記述として,適切なものはどれか。ここで,除算の商は,絶対値の小数点以下を切り捨てるものとする。
  • その整数値が正ならば3
  • その整数値が負ならば−3
  • その整数値が負ならば3
  • その整数値の正負にかかわらず0
  • [この問題の出題歴]
  • 基本情報技術者 H13春期 問3

分類

テクノロジ系 » 基礎理論 » 離散数学

正解

解説

設問では「ある整数値を…2進数記法で表すと最下位ビットが"11"であった。」としていますが、最下位2ビットが"11"となる整数値の特徴は正負によって異なります。

[正の数の場合]
正の数に対しては2の補数を適用しないので、2進数表現 xx…x11 をそのまま10進数に直すことを考えます(xは任意のビット)。最下位2ビットが"11"となる正の数は、
  • 111(2) → 7(10)
  • 1011(2) → 11(10)
  • 10111(2) → 23(10)
  • 110011(2) → 51(10)
というように、常に「4で割った余りが3である数」になります。これは4で割るという行為が2進数のビット列を右に2つシフトさせることと同義だからです。ビット列全体を右に2つシフトさせると、"11"(=10進数で3)の部分が端数(=除算の余り)となります。

[負の数の場合]
2の補数に変換したときと逆の手順で、その負数の絶対値を示すビット列を求めます。
  1. xx…x11 から1を引く。
     xx…x10
  2. 全てのビットを反転させる。
     xx…x01 //絶対値の2進数表現
これにより、2の補数表現で最下位2ビットが"11"となる負数があるとき、その負数の絶対値の最下位2ビットは必ず"01"になることがわかります。最下位2ビットが"01"となる数は、
  • 101(2) → (絶対値)5(10) → (負数)−5(10)
  • 1001(2) → (絶対値)9(10) → (負数)−9(10)
  • 10101(2) → (絶対値)21(10) → (負数)−21(10)
  • 110001(2) → (絶対値)49(10) → (負数)−49(10)
というような数の集合になります。これらの負数を4で割ると余りは 3 または −1 になります。ここで、設問の「除算の商は,絶対値の小数点以下を切り捨てるものとする。」という条件を適用すると、
  • −5÷4=−1.25 → 絶対値の小数点以下を切り捨てると商は−1
    商が−1ならば余りは−1
  • −9÷4=−2.25 → 絶対値の小数点以下を切り捨てると商は−2
    商が−2ならば余りは−1
というように、常に「4で割った余りは−1」になります。

以上より、最下位2ビットが"11"である整数値を4で割った余りは、その整数値が正ならば3、負ならば−1になります。よって「ア」の記述のみが適切です。
2の補数
2進数で負数を表現する方法の一つです。ある負の数を2の補数で表すには、①その負の数の絶対値を2進数に直し、②すべてのビットを反転して、③その結果に1を加えます。

例えば、10進数表記の -10 は以下の手順で2の補数に変換します。
  1. -10の絶対値である10を2進数に直す。
     10(10) → 1010(2)
  2. 1010(2)の全ビットを反転させる。
     1010(2) → 0101(2)
  3. ②の結果に1を加える。
     0101(2) → 0110(2)
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop