応用情報技術者 2019年 春期 午前2 問01

0以上255以下の整数のnext関数の論理演算による表現【午前2 解説】

要点まとめ

• 結論：$next(n)$は$(n+1)$を255でビットANDした式、すなわち$(n+1)\text{ AND }255$と等しいです。
• 根拠：$n$が255のとき$(n+1)=256$ですが、255は8ビットの全ビット1（$11111111_2$）なのでAND演算で256は0に戻ります。
• 差がつくポイント：ビット演算のマスクとして255（$0xFF$）を使うことで、0〜255の範囲に自然に循環することを理解できるかが鍵です。

正解の理由

• $0\le n<255$のとき、$n+1$は255以下なのでそのまま値が返ります。
• $n=255$のとき、$n+1=256$は2進数で$100000000_2$となり、下位8ビットはすべて0なので結果は0になります。
  これが問題文の定義と完全に一致します。

よくある誤解

• 256でANDすると常に0になるため意味がありません。
• OR演算はビットを立てる操作なので、$next(n)$の循環性を表現できません。

解法ステップ

1. 問題の関数定義を理解する：$next(n)$は0〜255の範囲で1ずつ増加し、255の次は0に戻る。
2. 2進数での表現を考える：255は8ビットすべて1の数値。
3. $(n+1)$の値が256になる場合を考慮し、下位8ビットだけを取り出す方法を検討。
4. AND演算で255をマスクすることで、下位8ビットを抽出できることを確認。
5. 選択肢の中でこの条件を満たすのは$(n+1)\text{ AND }255$のみ。

選択肢別の誤答解説

• イ: $(n+1)\text{ AND }256$は256のビット位置のみを抽出するため、$n+1$が256のときだけ1、それ以外は0となり不適。
• ウ: $(n+1)\text{ OR }255$は常に255以上の値になり、$next(n)$の定義と異なる。
• エ: $(n+1)\text{ OR }256$は256のビットを常に立てるため、範囲外の値を返し誤り。

補足コラム

FAQ