基本情報技術者試験 - 平成24年春期(科目B) - 問8
問題
次のプログラムの説明及びプログラムを読んで,設問1~3に答えよ。
整数型関数BitTestは,8ビットのデータ中の指定したビット位置にあるビットの値を検査して,結果を返す。整数型関数BitCountは,8ビットのデータ中にある1のビットの個数を返す。
なお,本問において,演算子“&”,“|”は,二つの8ビット論理型データの対応するビット位置のビット同士について,それぞれ論理積,論理和を求め,8ビット論理型で結果を得るものとする。また,“~”Bという表記は,8ビット論理型定数を表す。
〔プログラム1の説明〕
整数型関数BitTestを,次のとおりに宣言する。
○整数型関数: BitTest(8ビット論理型: Data,8ビット論理型: Mask)
検査される8ビットのデータは入力用の引数Dataに,検査をするビット位置の情報は入力用の引数Maskに,それぞれ格納されている。Mask中のビットの値が1であるビット位置に対応したData中のビットを検査して,次の返却値を返す。ここで,Mask中には1のビットが1個以上あるものとする。
返却値 0:検査した全てのビットが0
1:検査したビット中に0と1が混在
2:検査した全てのビットが1
例えば,図1の例1では,Maskのビット番号7~5の3ビットが1であるので,Dataのビット番号7~5の3ビットの値を検査し,0と1が混在しているので返却値1を返す。例2では,Maskのビット番号4と0の2ビットが1であるので,Dataのビット番号4と0の2ビットの値を検査し,どちらも1であるので返却値2を返す。


〔プログラム2,3の説明〕
整数型関数BitCountを,次のとおりに宣言する。
○整数型関数: BitCount(8ビット論理型: Data)
検査される8ビットのデータは入力用の引数Dataに格納されている。
このためのプログラムとして,基本的なアルゴリズムを用いたプログラム2と,処理効率を重視したプログラム3を作成した。
プログラム2,3中の各行には,ある処理系を想定して,プログラムの各行を1回実行するときの処理量(1,2,…)を示してある。選択処理と繰返し処理の終端行の処理量は,それぞれの開始行の処理量に含まれるものとする。
なお,演算子“-”は,両オペランドを8ビット符号なし整数とみなして,減算を行うものとする。

設問1 プログラム1中の[ ]に入れる正しい答えを,解答群の中から選べ。
a,bに関する解答群
設問2 次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。
プログラム1は,Mask中に1のビットが1個以上あることを前提としている。ここで,この前提を取り除いて,Mask中の1のビットが0個の場合は返却値0を返すようにしたい。そのために,プログラム1の処理部分について,次の修正案①~③を考えた。ここで,修正案①は,プログラム1のままで何も変更しない。また,[ a ]と[ b ]には,設問1の正しい答えが入っているものとする。

これらの修正案のうち,正しく動作するのは[ c ]である。
cに関する解答群
設問3 次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。
プログラム2,3の処理効率について考えてみる。表1にプログラム2,3の処理量の比較結果を示す。
プログラム3では,αの行での変数Workの更新において効率の良いアルゴリズムが使われている。例えば,プログラム3で引数Dataの内容が"01101010"Bであったとき,繰返し処理においてαの行の2回目の実行が終了した時点で変数Workの内容は,"[ f ]"Bになっている。このようなビット変換の処理によって,繰返し処理の繰返し回数は,検査されるデータ中の1のビットの個数と同じになる。
dに関する解答群
eに関する解答群
fに関する解答群
整数型関数BitTestは,8ビットのデータ中の指定したビット位置にあるビットの値を検査して,結果を返す。整数型関数BitCountは,8ビットのデータ中にある1のビットの個数を返す。
なお,本問において,演算子“&”,“|”は,二つの8ビット論理型データの対応するビット位置のビット同士について,それぞれ論理積,論理和を求め,8ビット論理型で結果を得るものとする。また,“~”Bという表記は,8ビット論理型定数を表す。
〔プログラム1の説明〕
整数型関数BitTestを,次のとおりに宣言する。
○整数型関数: BitTest(8ビット論理型: Data,8ビット論理型: Mask)
検査される8ビットのデータは入力用の引数Dataに,検査をするビット位置の情報は入力用の引数Maskに,それぞれ格納されている。Mask中のビットの値が1であるビット位置に対応したData中のビットを検査して,次の返却値を返す。ここで,Mask中には1のビットが1個以上あるものとする。
返却値 0:検査した全てのビットが0
1:検査したビット中に0と1が混在
2:検査した全てのビットが1
例えば,図1の例1では,Maskのビット番号7~5の3ビットが1であるので,Dataのビット番号7~5の3ビットの値を検査し,0と1が混在しているので返却値1を返す。例2では,Maskのビット番号4と0の2ビットが1であるので,Dataのビット番号4と0の2ビットの値を検査し,どちらも1であるので返却値2を返す。


〔プログラム2,3の説明〕
整数型関数BitCountを,次のとおりに宣言する。
○整数型関数: BitCount(8ビット論理型: Data)
検査される8ビットのデータは入力用の引数Dataに格納されている。
このためのプログラムとして,基本的なアルゴリズムを用いたプログラム2と,処理効率を重視したプログラム3を作成した。
プログラム2,3中の各行には,ある処理系を想定して,プログラムの各行を1回実行するときの処理量(1,2,…)を示してある。選択処理と繰返し処理の終端行の処理量は,それぞれの開始行の処理量に含まれるものとする。
なお,演算子“-”は,両オペランドを8ビット符号なし整数とみなして,減算を行うものとする。


設問1 プログラム1中の[ ]に入れる正しい答えを,解答群の中から選べ。
a,bに関する解答群
| ア | (Data & Mask) = "00000000"B |
|---|---|
| イ | (Data & Mask) = Data |
| ウ | (Data & Mask) = Mask |
| エ | (Data | Mask) = "00000000"B |
| オ | (Data | Mask) = Mask |
設問2 次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。
プログラム1は,Mask中に1のビットが1個以上あることを前提としている。ここで,この前提を取り除いて,Mask中の1のビットが0個の場合は返却値0を返すようにしたい。そのために,プログラム1の処理部分について,次の修正案①~③を考えた。ここで,修正案①は,プログラム1のままで何も変更しない。また,[ a ]と[ b ]には,設問1の正しい答えが入っているものとする。

これらの修正案のうち,正しく動作するのは[ c ]である。
cに関する解答群
| ア | 修正案① |
|---|---|
| イ | 修正案② |
| ウ | 修正案③ |
| エ | 修正案①及び② |
| オ | 修正案①及び③ |
| カ | 修正案②及び③ |
設問3 次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。
プログラム2,3の処理効率について考えてみる。表1にプログラム2,3の処理量の比較結果を示す。
| 最小 | 最大 | |
| プログラム2 | 72 | [ d ] |
| プログラム3 | [ e ] | 54 |
プログラム3では,αの行での変数Workの更新において効率の良いアルゴリズムが使われている。例えば,プログラム3で引数Dataの内容が"01101010"Bであったとき,繰返し処理においてαの行の2回目の実行が終了した時点で変数Workの内容は,"[ f ]"Bになっている。このようなビット変換の処理によって,繰返し処理の繰返し回数は,検査されるデータ中の1のビットの個数と同じになる。
dに関する解答群
| ア | 80 |
|---|---|
| イ | 88 |
| ウ | 104 |
| エ | 112 |
eに関する解答群
| ア | 6 |
|---|---|
| イ | 10 |
| ウ | 20 |
| エ | 22 |
fに関する解答群
| ア | 00000011 |
|---|---|
| イ | 00000110 |
| ウ | 00001010 |
| エ | 01010000 |
| オ | 01100000 |
| カ | 10100000 |
正解と解説
正解設問1 (a)ウ (b)ア 設問2 (c)イ 設問3 (d)ア (e)ア (f)オ
分野テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム
解説
0と1が並んだビット列を,論理演算で調べるアルゴリズムの問題です。まず,問題で使う演算を確認しておきましょう。- 「&」(論理積):両方のビットが1のときだけ1になる
- 「|」(論理和):どちらかのビットが1なら1になる
「&」には,Maskが1の位置のビットだけを取り出し,それ以外を0にする働きがあります。これを「マスク」といいます。■ 設問1
Data & Mask を計算すると,Maskで1になっている位置だけ,Dataのビットがそのまま残ります。【空欄a】
直後で RC ← 2(検査した全てのビットが1)としているので,ここは「全て1か」を判定する条件です。検査した位置が全て1なら,Data & Mask の結果はMaskと全く同じになります。
例えば図1の例2では,Data & Mask=00010001 で,Mask(00010001)と一致します。正解は「ウ」です。
【空欄b】
直後で RC ← 0(検査した全てのビットが0)としているので,「全て0か」を判定する条件です。検査した位置が全て0なら,Data & Mask の結果は00000000になります。正解は「ア」です。
どちらにも当てはまらなければ,0と1が混在しているので RC ← 1 になります。
■ 設問2
【空欄c】
Maskが00000000(1のビットが0個)のとき,Data & Mask は常に00000000です。つまり,条件a(結果=Mask)と条件b(結果=00000000)が両方とも成り立ちます。このとき返却値0になる修正案を探します。
- 修正案①:先にaを判定するので,RC ← 2 となり誤り
- 修正案②:先にbを判定するので,RC ← 0 となり正しい
- 修正案③:bが成り立ちRC ← 0 となった後,続けてaも判定され,RC ← 2 で上書きされるので誤り
修正案②は,Maskに1のビットがある通常の場合も,判定の順番が変わるだけで,元のプログラムと同じ結果になります(全て1と全て0が同時に成り立つのはMaskが0の場合だけだからです)。正解は「イ」です。■ 設問3
処理量は,各行の処理量に実行回数を掛けて合計します。繰返しの開始行(条件の判定)は,最後に条件が偽になって終了するときにも1回実行されることに注意しましょう。【空欄d】
プログラム2は,ビットを1つずつ8回調べます。
- 最初の2行:1+1=2
- 繰返しの開始行:8回の繰返し+終了判定1回で9回。4×9=36
- 最下位ビットの判定:3×8=24
- 右シフト:1×8=8
- return:2
ここまでの合計は72で,これがCountの加算を1回もしない場合(Dataが全て0)の最小値です。最大はDataが全て1のときで,Countの加算(処理量1)が8回加わるので,72+8=80です。正解は「ア」です。【空欄e】
プログラム3の最小は,Dataが全て0で,繰返しが1回も行われないときです。
- 最初の2行:1+1=2
- 繰返しの開始行:終了判定の1回だけで2×1=2
- return:2
合計は6です(最大の54はDataが全て1で8回繰り返す場合で,2+2×9+(1+3)×8+2=54となります)。正解は「ア」です。【空欄f】
αの行「Work ← Work & (Work - 1)」の動きを,実際に計算してみます。ある数から1を引くと,一番右にある1が0になり,それより右の0は全て1になります。これと元の値の「&」を取ると,一番右の1だけが消えます。
1回目の実行:
2回目の実行:
2回目の実行が終了した時点のWorkは01100000です。正解は「オ」です。
このように,1回の繰返しで1のビットが1個ずつ消えていくので,繰返しの回数は1のビットの個数と同じになります。0のビットを調べる無駄がない分,プログラム2より効率が良いわけです。