基本情報技術者試験のサンプル問題を解こう！（10）（科目B）「ビットの並びを逆にした値を返す関数」

基本情報技術者試験のサンプル問題（科目B）を解いてみよう。

今回のテーマは、「ビットの並びを逆にした値を返す関数」である。

関数 rev は 8 ビット型の引数 byte を受け取り，ビットの並びを逆にした値を返す。
例えば，関数 rev を rev(01001011) として呼び出すと，戻り値は 11010010 となる。
なお，演算子 ∧ はビット単位の論理積，演算子 ∨ はビット単位の論理和，演算子 >> は論理右シフト，演算子 << は論理左シフトを表す。例えば，value >> n はvalue の値を n ビットだけ右に論理シフトし，value << n は value の値を n ビットだけ左に論理シフトする。

解答群
ア r ← (r << 1) ∨ (rbyte ∧ 00000001)
rbyte ← rbyte >> 1
イ r ← (r << 7) ∨ (rbyte ∧ 00000001)
rbyte ← rbyte >> 7
ウ r ← (rbyte << 1) ∨ (rbyte >> 7)
rbyte ← r
エ r ← (rbyte >> 1) ∨ (rbyte << 7)
rbyte ← r

r ← (r << 1) ∨ (rbyte ∧ 00000001)
rbyte ← rbyte >> 1

「∨」は、論理和（logical disjunction）を表す記号で、「または」と読む。
「A ∨ B 」は、A または B のどちらか一方、あるいは両方が真の場合に真となる。

「∧」は、論理積（logical conjunction）を表す記号で、「かつ」と読む。
「A ∧ B」は「AかつB」と読み、AとBの両方が真の場合にのみ真となる。

問題のポイントと処理の流れ

1. 目的
   8ビットの引数 byte を１ビットずつ右から左へ逆順に並び替え、結果を r に格納して返す。
2. 処理の仕組み
   • (rbyte ∧ 00000001) によって、rbyte の最下位ビット（LSB）を取り出す。
   • r << 1 で r を1ビット左シフトし、空いた最下位ビットにLSBを OR 演算で追加する。
   • そのあと rbyte を右に1ビットシフトし、次のLSBを取り出せるようにする。
3. 8回繰り返すことで
   • rbyte の LSB → r の左端へ
   • 次のビットも同様に → r に積み上げる。
   • 最終的に r に逆順のビット列が完成する。

他の選択肢なぜ間違い？

• 選択肢 イ：
  7ビット右に一度にシフトすると、必要なビット情報が失われ処理できなくなる。
• 選択肢 ウ／エ：
  これはビットを回転するコードで、右→左や左→右に一ビットずらすだけの処理。
  8回繰り返しても元に戻るだけで、ビットの逆順にはならない。

まとめ

• なぜ逆順になるのか？
  rbyte のLSBを逐次取り出し、r のMSB（最上位ビット）に詰め込むことで逆転が実現。
• このビットマニピュレーションは、ビット演算を駆使して高速に逆順を実装する典型的なパターンである。