うごく基本情報

サンプル問題セット(2022年12月公開) 科目B 問6

ビット演算 ・ シフト演算

次のプログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。
関数 rev は 8 ビット型の引数 byte を受け取り,ビットの並びを逆にした値を返す。
例えば,関数 rev を rev(01001011) として呼び出すと,戻り値は 11010010 となる。
なお,演算子∧はビット単位の論理積,演算子[ ]∨はビット単位の論理和,演算子 >> は論理右シフト,演算子[ ]<< は論理左シフトを表す。例えば,value >> n はvalue の値を n ビットだけ右に論理シフトし,value << n は value の値を n ビットだけ左に論理シフトする。

○8ビット型: rev(8ビット型: byte)
  8ビット型: rbyte ← byte
  8ビット型: r ← 00000000
  整数型: i
  for (i を 1 から 8 まで 1 ずつ増やす)
    [ a ]
  endfor
  return r
a
ア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

出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問6

正解と解説を見る

正解:ア

ポイント:ビットの並びを逆にするには、元の値の最下位ビットを1つずつ取り出し、結果を左にずらしながら下に足していく。

8ビットの並びを左右逆にする関数です(例:11000001 → 10000011)。
アの処理を1回分見ると:
・rbyte ∧ 00000001 で、rbyte の最下位ビットだけを取り出す。
・r を1ビット左にずらし(r << 1)、空いた最下位に取り出したビットを入れる(∨)。
・rbyte を1ビット右にずらし(>> 1)、次のビットを最下位に持ってくる。
これを8回繰り返すと、元の最下位ビットが最上位まで押し上げられ、並びが逆になります(ア)。
イ:7ビットずらすと、1回でほとんどのビットが消えてしまいます。
ウ・エ:(rbyte << 1) ∨ (rbyte >> 7) は全体を1ビット回転させる処理です。8回回転すると元に戻るだけです。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

rev(0) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 30 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○8ビット型: rev(8ビット型: byte)byte = 0
22行目8ビット型: rbyte ← byterbyte = 0
33行目8ビット型: r ← 00000000r = 0
44行目整数型: i
55行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 1
66行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
77行目rbyte ← rbyte >> 1
85行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 2
96行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
107行目rbyte ← rbyte >> 1
115行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 3
126行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
137行目rbyte ← rbyte >> 1
145行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 4
156行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
167行目rbyte ← rbyte >> 1
175行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 5
186行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
197行目rbyte ← rbyte >> 1
205行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 6
216行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
227行目rbyte ← rbyte >> 1
235行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 7
246行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
257行目rbyte ← rbyte >> 1
265行目for (i を 1 から 8 まで 1 ずつ増やす)真
i = 8
276行目r ← (r << 1) ∨ (rbyte ∧ 00000001)
287行目rbyte ← rbyte >> 1
295行目for (i を 1 から 8 まで 1 ずつ増やす)偽
i = 9
309行目return r

戻り値:0

サイトで、1行ずつ予想しながら動かす →