基本情報技術者試験科目bサンプル問6｜2022年12月26日掲載

今回はサンプル問題の問6を解いてみたいと思います。アルゴリズムの問題は基本的にトレースをすることになりますが、今回の問題はその中でも時間がかかる部類になると思います。この辺りの見極めはカンに頼らざるを得ない部分もありますが、問題にたくさん触れることで精度も上がるでしょう。

今回はこういった前提も踏まえなるべく早く解くという方向で書いてみます。

※本番では5分以上かかりそうなら飛ばして最後にやるようにしましょう。

問題

次のプログラム中の〇〇に入れる正しい答えを，解答群の中から選べ。

関数 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 ずつ増やす)
　　〇〇
endfor
return r

解答群
ア 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

解き方

基本はトレースになるのですがプログラムや問題の問われている部分の意味などを確認すると早く答えにたどり着けると思います。

関数revのやりたいこと

revというのはおそらくreverseで逆行という意味になります。問題文内にも「関数 rev を rev(01001011) として呼び出すと，戻り値は 11010010 となる。」とありますので引数に渡した２進数を逆順にして出力するという動きになりそうですね。

最終的に出力（答え）になる変数を確認

プログラム中をみると次の一行が見つかります。

return r

これはrという変数を返しますという意味で最終的に出力されるのはこのrという変数ということがわかります。ここも早く答えにたどり着くためにあらかじめ押さえておいた方が良いポイントになります。

解答群のあたりをつける

これはかなりカンも入ってきますが個人的には次の箇所が気になりました。
(rbyte ∧ 00000001)
この論理積ですが１と１が入力されたときだけ１を返すというものでrbyteの最下位ビットが1の時だけ1になるというものです。つまりrbyteの最下位ビットが1ならばそれを取り出すという動きになるわけですね。

プログラムトレース

とりあえず気になるアからトレースしてみます。問題文のビット（01001011）を使って進めます。

rbyte=01001011
r=00000000
i=1

(r << 1) ∨ (rbyte ∧ 00000001)
はまず分解して考えます。後半のカッコから当てはめてみます。

01001011 ∧ 00000001 = 00000001

00000000 ∨ 00000001 = 00000001
r = 00000001
rbyte = 00100101

これでfor文の１周目が完了しました。

２周目

00100101 ∧ 00000001 = 00000001
00000010 ∨ 00000001 = 00000011
r = 00000011
rbyte = 00010010

3周目

00010010 ∧ 00000001 = 00000000
00000110 ∨ 00000000 = 00000110
r = 00000110
rbyte = 00001001

ここまでの動きを見てみる

この時点で一度r（出力）とrbyte（入力）の変化を見てみましょう。

rbyte（入力）の動き
01001011（初期値）
↓
00100101（for文1回目）
↓
00010010（for文2回目）
↓
00001001（for文3回目）

---

r（出力）の動き
00000000（初期値）
↓
00000001 （for文1回目）
↓
00000011（for文2回目）
↓
00000110（for文3回目）

rbyte（入力）が右にずれていって、r（出力）が左にずれているのがわかりますね。これを後5回繰り返す動きになりますが、完了した時に入力が逆順になって出力されることがこれでわかると思います。