AND/OR で表す循環する加算
出典: 令和5年度 春期 応用情報技術者試験 午前 問1 (IPA)
0 以上 255 以下の整数 n に対して，
next(n) = n+1 (0 ≦ n ＜ 255)，0 (n ＝ 255)
と定義する。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
正解と解説を見る
正解: ア
- ア: 下位 8 ビットだけを残すので、256 になったときだけ 0 に戻ります。正しい答えです。
- イ: 256 は 1 0000 0000 なので、n＋1 が 256 未満のときは結果が全て 0 になってしまいます。
- ウ: OR 255 では下位 8 ビットが全て 1 になり、結果は常に 255 以上になります。
- エ: OR 256 では 9 ビット目が常に 1 になり、結果は常に 256 以上になります。
ポイント
- 255 は 2 進数で 1111 1111 (下位 8 ビットが全て 1) です。
- n＋1 が 1〜255 のときは、(n＋1) AND 255 = n＋1 のままです。
- n = 255 のとき n＋1 = 256 = 1 0000 0000 で、下位 8 ビットは全て 0 なので、AND 255 を取ると 0 になります。
- つまり AND 255 は 256 で割った余り (下位 8 ビットだけ残す) と同じで、next(n) と一致します。