応用情報技術者試験令和5年春午前問1 解説付き過去問

問題

0以上255以下の整数nに対して、

と定義する。 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

この問題は、0〜255の範囲にある整数 n に対して定義された関数 next(n) を、ビット演算の式で表したときに正しくなるものを選ぶ問題です。以下の手順で解説します。

next(n) は、n に 1 を加算し、その結果が256以上になった場合でも、下位8ビットだけを取り出す処理です。
これは、(n + 1) を 256 で割った余り、すなわち (n + 1) % 256 と等価です。

この処理をビット演算で行うには、(n + 1) AND 255 という式が該当します。

255 は 2進数で 11111111 であり、この値との AND 演算を行うと、(n + 1) の下位8ビットのみを取り出すことができます。

例えば、n = 255 の場合、n + 1 = 256、2進数で 100000000（9ビット）となりますが、

256 AND 255 = 100000000 AND 11111111 = 00000000

となり、結果は 0 になります。これは next(255) = 0 の定義とも一致します。

それぞれの式が next(n) の動作と一致しない理由を確認します。

(1) (n + 1) AND 256：

256 は 2進数で 100000000（9ビット）なので、AND を取っても下位8ビットはすべて0になり、結果は常に 0 または 256 になります。

(2) (n + 1) OR 255：

OR 演算では下位8ビットが常に 11111111（255）になります。たとえば、n = 0 のとき、n + 1 = 1、1 OR 255 = 255、
n = 255 のときは 256 OR 255 = 511 となり、定義と一致しません。

(3) (n + 1) OR 256：

この演算は、(n + 1) に常に 100000000（256）を加えることになり、結果が必ず 256 以上になります。next(n) の定義とは合いません。

したがって、next(n) と等しい式は (n + 1) AND 255 です。