基本情報技術者試験 - 平成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に関する解答群
ア(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の処理量の比較結果を示す。
表1 プログラム2,3の処理量の比較
最小最大
プログラム272[ 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が並んだビット列を,論理演算で調べるアルゴリズムの問題です。まず,問題で使う演算を確認しておきましょう。 「&」には,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回目の実行:
  • Work:01101010
  • Work - 1:01101001
  • Work & (Work - 1):01101000

2回目の実行:
  • Work:01101000
  • Work - 1:01100111
  • Work & (Work - 1):01100000

 2回目の実行が終了した時点のWorkは01100000です。正解は「オ」です。

 このように,1回の繰返しで1のビットが1個ずつ消えていくので,繰返しの回数は1のビットの個数と同じになります。0のビットを調べる無駄がない分,プログラム2より効率が良いわけです。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる