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

問題文

0以上255以下の整数

n

に対して、

next (n) = {n + 1 0 (0 \leq n < 255) (n = 255)

と定義する。

n e x t (n)

と等しい式はどれか。ここで、

x

AND

y

及び

x

y

は、それぞれ

x

と

y

を2進数表現にして、桁ごとの論理積及び論理和をとったものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：(n+1) AND 255（正解）

イ：(n+1) AND 256

ウ：(n+1) OR 255

エ：(n+1) OR 256

🔒 解説は解答すると表示されます

8ビット循環インクリメント【午前2解説】

正解の理由

next(n) は0〜255の範囲で「1増やすが255の次は0に戻る」動作をする、すなわち256で剰余を取る加算（

n + 1 (mod 256)

）です。ビット演算でこれを実現するには下位8ビットだけを残すマスクが必要であり、255（2進で11111111）とのビットANDが対応します。したがって選択肢アの

(n + 1) AND 255

は各ケースでnext(n) と一致します。

例：

n = 255

のとき

n + 1 = 256

だが

(256) AND 255 = 0

となり、定義どおり0に戻ります。一般に

(n + 1) AND 255 = (n + 1) mod 256

が成り立ちます。

解法ステップ

next(n) の動作を「 $n + 1$ をとって0〜255に収める（剰余256）」と理解する。すなわち $n + 1 (mod 256)$ 。
ビット演算の性質から、下位8ビットだけを取り出すにはマスク255（ $2^{8} - 1$ ）との AND を用いると考える。
各選択肢をビット操作として評価し、 $(n + 1)$ の下位8ビットを残すものが一致するか確認する。

選択肢別の誤答解説

ア: (n+1) AND 255
正しい。255は2進で11111111（下位8ビットが1）なので、下位8ビットだけを残す。 $n = 255$ のとき $n + 1 = 256$ が256 & 255 = 0となり定義と一致する。
イ: (n+1) AND 256
誤り。256は2進で1 0000 0000（9ビット目のみ1）であり、これは「9ビット目だけを抽出する」操作になる。すなわち $(n + 1) AND 256$ は通常0を返すが、 $n + 1 = 256$ のときだけ256を返す（0または256のどちらか）。したがってnext(n)（常に0〜255）とは一致しない。過去の誤記述「常に0になる」は誤りで、正しくは「0または256を返すため範囲が0〜255に限定されない」と説明すべきです。
ウ: (n+1) OR 255
誤り。OR 255は下位8ビットを全て1にするため、ほとんどの場合255を返す。例えば $n = 0$ のとき $n + 1 = 1$ でも $1 OR 255 = 255$ となり、next(0)=1と一致しない。
エ: (n+1) OR 256
誤り。OR 256は常に9ビット目を1にするため、 $n + 1$ の値が小さくても結果は $\geq 256$ になり、next(n) の取りうる範囲（0〜255）と異なる。例えば $n = 0$ なら $1 OR 256 = 257$ で不適。

よくある誤解

「AND 256は常に0になる」と考える誤り：実際には9ビット目（重み256）を抽出する操作で、 $n + 1 = 256$ のときだけ256を返します。したがって値域は0または256になります。
OR と AND を混同する：OR はビットを1に固定するため値が大きくなりがちで、循環（モジュロ）動作には向きません。循環は下位ビットを取り出す AND（マスク）が基本です。
マスク値の選び方の誤り： $2^{k} - 1$ （例：255）は「下位kビットを残す」マスクで、剰余 $2^{k}$ と同値になる点を覚えておくと良いです。

補足コラム

ビットマスクによる剰余操作は高速な循環カウンタやリングバッファの実装でよく使われます。一般に

(x) AND (2^{k} - 1) = x mod 2^{k}

が成り立つため、

k = 8

のときは255がマスクになります。CPUでは除算よりビット演算の方が高速なケースがあり、2の冪に対する剰余は特に頻出です。

簡単な実装例（Python）：

def next_n(n):
    # nは0 <= n <= 255を仮定
    return (n + 1) & 0xFF  # 0xFF は 255

FAQ

Q: なぜ255を使うと「剰余256」になるのですか？
A: 255は2進で下位8ビットが全て1なので、AND することで下位8ビットだけを残します。これが

x mod 256

と同値です。

Q: 負の値や範囲外の入力でも同様ですか？
A: 上の等式はビット表現と幅（符号なし）に依存します。問題は

0 \leq n \leq 255

と定義されているため上記で正確に動作します。符号付き表現などでは別途注意が必要です。

Q: OR で代用できないのはなぜですか？
A: OR はビットを1にする操作で、値を「上げる」方向に作用します。循環させるためには下位ビットを取り出す AND（マスク）が適切です。

関連キーワード: ビット演算, マスク, 循環インクリメント, モジュロ256, 下位ビット抽出

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！