応用情報技術者 2015年 秋期 午前2 問01

0以上255以下の整数のnext関数【午前2 解説】

要点まとめ

• 結論：$next(n)$は「$n+1$を256で剰余した値」であり、$(n+1)\text{ AND }255$と等しいです。
• 根拠：255は2進数で8ビットすべてが1（11111111）で、AND演算で下位8ビットを抽出します。
• 差がつくポイント：ビット演算の意味と範囲（0〜255）を理解し、256（100000000）とのANDやORの結果を正確に把握することです。

正解の理由

よくある誤解

• 256とのANDは0か256のどちらかになり、$next(n)$の連続性を保てません。
• OR演算はビットを立てるため、$next(n)$のような0に戻る動作を表現できません。

解法ステップ

1. $next(n)$の定義を確認し、$n=255$のとき0に戻ることを理解する。
2. 255を2進数で11111111（8ビットすべて1）と認識する。
3. $(n+1)\text{ AND }255$は、$n+1$の下位8ビットを抽出する操作と理解する。
4. $n=255$のとき、$n+1=256$は2進数で100000000となり、下位8ビットは0になる。
5. 他の選択肢のビット演算結果を検証し、$next(n)$の動作と合わないことを確認する。
6. よって、$(n+1)\text{ AND }255$が$next(n)$と等しいと判断する。

選択肢別の誤答解説

• イ: $(n+1)\text{ AND }256$は256のビット（9ビット目）だけを抽出し、0か256のどちらかになるため不適。
• ウ: $(n+1)\text{ OR }255$は常に下位8ビットが1になるため、$next(n)$の連続的な増加を表現できない。
• エ: $(n+1)\text{ OR }256$は9ビット目を常に1にするため、$next(n)$の範囲外の値を返す。

補足コラム

FAQ