ビット演算で循環する加算
出典: 平成31年度 春期 応用情報技術者試験 午前 問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
正解と解説を見る
正解: ア
- ア: 255 との AND で下位 8 ビットだけが残り、256 のときだけ 0 になるので正しい答えです。
- イ: 256 (1 0000 0000) との AND は第 8 ビットしか残さないので、n＜255 では 0 になってしまいます。
- ウ: 255 との OR は下位 8 ビットを全て 1 にするので、ほとんどの n で 255 以上になります。
- エ: 256 との OR は第 8 ビットを 1 にするので、n＋1 に 256 を足した値になってしまいます。
ポイント
- 255 は 2 進数で 1111 1111 (下位 8 ビットが全て 1) です。これとの AND は 下位 8 ビットだけを残す 操作になります。
- n ＜ 255 なら n＋1 ≦ 255 なので、(n＋1) AND 255 ＝ n＋1 のままです。
- n ＝ 255 なら n＋1 ＝ 256 ＝ 1 0000 0000 なので、下位 8 ビットは全て 0 になり、0 になります。
- よって (n＋1) AND 255 が next(n) と等しくなります。