離散数学 (全52問中43問目)

No.43

0以上255以下の整数nに対して,
03.gif/image-size:197×39
と定義する。next(n)と恒等的に等しい式はどれか。ここで,x AND y 及び x OR y は,それぞれxとyを2進数表現にして,けたごとの論理積及び論理和をとったものとする。
  • (n+1) AND 255
  • (n+1) AND 256
  • (n+1) OR 255
  • (n+1) OR 256

分類

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

正解

解説

next(n)のとる値を考えてみると、0→1→2→3→・・・→255→0→1 というように、引数の値に1を加算した値を返し255になると0に戻る関数であると言えます。

この問題で考えなければいけないポイントは、
  • 1ずつの加算がおこなわれるか。
  • next(255)のときに結果が 0となるか。
の2点です。

まず論理和(OR)演算である「ウ」と「エ」は、常に結果が同じ値(「ウ」は 255、「エ」は 256)となってしまうので正しくないことがわかります。
残った論理積(AND)演算である「ア」と「イ」ですが、「イ」を2進数で表すと 1 0000 0000となり、下位8ビットの演算結果は常に0になることがわかります。

つまり「イ」は間違いで、正しく結果が返されるのは「ア」だけということになります。下は「ア」の式のビット演算図です。
03a.gif/image-size:468×114
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop