サンプル問題 科目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 ずつ増やす)
[ ]
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
出典:基本情報技術者試験 サンプル問題
具体的に考える
これは、なかなかの難問だと思います。いつものように具体的に考えます。
アの場合
回答アの1行目で行っている処理が多すぎるので、分解しています。#3, #4, #5, #6は1行目の処理です。
具体的に考えていくと徐々にこのプログラムの考え方がわかってきて、正しいことに気づきます。#50で正しい結果が出ています。
イの場合
アを考えた後でイを見ると、試すまでもなく全然ダメなことがわかります。7ビットシフトすると、必要な情報が消えていってしまいます。
ウとエの場合
ウとエの処理は、よく考えると、次の図のように1ビットずつローテートする処理です。
例えばウのように、「(rbyte << 1)」(rbyteを左に1ビット論理シフト)を行うと、rbyteの左端に元々あったビットは消えて無くなり、右端のビットは0になります。
ウの処理では、さらに「∨ (rbyte >> 7)」を行うことで、この消えて無くなる左端のビットを右に7ビット論理シフトして右端に移動させています。
つまり、ウの処理は1ビットずつ左に論理シフトして、元々左端にあったビットを右端に持ってきています。このような操作をローテートと呼んだりします。
エも同様に、右に1ビットローテートする処理です。
このような処理を8回行うとrbyteの内容は元に戻ってしまい、しかもrbyteとrの値は等しくなるので、ビットの並びを逆順にすることはできません。
ということで、答えはアです。
試験では
実際の試験では、この問題は直感でとりあえず答えを書いておいて、最後に時間が余れば取り組み直す感じではないでしょうか。時間に追われてバタバタ考える問題ではなさそうです。
おまけ
私がこういうプログラムを作成するなら、どうするか考えました。変数bitmask, bitsetを増やして、rbyteは不要なので削除しています。
1行で行う処理を減らした分、アより分かりやすくなっていれば良いのですが。
○8 ビット型: rev(8 ビット型: byte)
8 ビット型: r ← 00000000
8 ビット型: bitmask ← 00000001
8 ビット型: bitset ← 10000000
整数型: i
for (i を 1 から 8 まで 1 ずつ増やす)
if (byte ∧ bitmask ≠ 00000000)
r ← r ∨ bitset
endif
bitmask ← bitmask << 1
bitset ← bitset >> 1
endfor
return r