基本情報技術者 2012年 春期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問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中のに入れる正しい答えを、解答群の中から選べ。
解答群
ア：(Data & Mask) = "00000000"B
イ：(Data & Mask) = Data
ウ：(Data & Mask) = Mask
エ：(Data | Mask) = "00000000"B
オ：(Data | Mask) = Mask
模範解答
a：ウ、b：ア
解説
解答の導き方
まず、BitTestが何を判定する関数なのかを確認します。Maskで1になっている位置だけを検査し、その位置のDataがすべて1なら返却値は2、すべて0なら0、0と1が混在していれば1です。
ここで使う「&」は、対応するビット同士の論理積です。結果が1になるのは、両方のビットが1の場合だけです。そのため、Data & Maskを計算すると、Maskが1の位置ではDataの値が残り、Maskが0の位置は結果も0になります。
この結果を使って、aとbに入る条件を考えます。
- 検査するビットがすべて1なら、Data & Maskの結果はMaskと同じになります。したがってaは「(Data & Mask) = Mask」となり、解答群ではウです。この条件が成立したときに、プログラムはRCに2を設定します。
- aが成立しない場合、次に検査するビットがすべて0かどうかを調べます。すべて0なら、Data & Maskの結果は8ビットすべて0です。したがってbは「(Data & Mask) = "00000000"B」となり、解答群ではアです。この条件が成立したときに、プログラムはRCに0を設定します。
- どちらの条件も成立しなければ、検査したビットには0と1が混在しています。このとき、プログラムはRCに1を設定します。
図1の例1では、検査するビットのDataは「0、1、0」です。Data & MaskはMaskと同じではなく、すべて0でもないため、返却値は1になります。例2では、検査するビットのDataがどちらも1なので、Data & MaskはMaskと同じになり、返却値は2になります。
誤りやすいポイント
- Maskの0の位置は検査対象ではありません。Data & Maskでは、その位置の結果が0になるため、検査対象のビットだけを取り出せます。
- 「(Data & Mask) = Data」は、検査対象のビットがすべて1であることを表しません。検査対象ではない位置にDataの1があると、そのビットはData & Maskでは0になるため、比較結果に影響します。
- 「(Data | Mask) = Mask」は、検査対象のビットがすべて1であることを表しません。「|」は論理和なので、Maskが1の位置ではDataが0でも結果が1になります。
- 問題文には「Mask中には1のビットが1個以上ある」とあります。この条件により、検査対象が空になることはありません。検査対象が空だと、Data & Maskは0にもMaskにもなり、全0か全1かを区別できなくなります。
FAQ
Q: なぜ「&」を使うのですか？
A: Maskの1の位置ではDataのビットを残し、Maskの0の位置では結果を0にできるからです。これにより、検査対象のビットだけを取り出せます。
A: Maskの1の位置ではDataのビットを残し、Maskの0の位置では結果を0にできるからです。これにより、検査対象のビットだけを取り出せます。
Q: Data & Maskが0でもMaskでもない場合、なぜ返却値は1なのですか？
A: Data & Maskが0なら検査対象はすべて0で、Maskと同じなら検査対象はすべて1です。そのどちらでもない場合は、検査対象に0と1が混在しています。
A: Data & Maskが0なら検査対象はすべて0で、Maskと同じなら検査対象はすべて1です。そのどちらでもない場合は、検査対象に0と1が混在しています。
Q: 「|」を使う選択肢では判定できないのですか？
A: この問題の判定には適しません。たとえば「(Data | Mask) = Mask」は、Maskが1の位置でDataが0か1かを区別できません。
A: この問題の判定には適しません。たとえば「(Data | Mask) = Mask」は、Maskが1の位置でDataが0か1かを区別できません。
関連キーワード: ビット演算、論理積、論理和、マスク処理、ビット判定
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プログラム1は、Mask中に1のビットが1個以上あることを前提としている。ここで、この前提を取り除いて、Mask中の1のビットが0個の場合は返却値0を返すようにしたい。そのために、プログラム1の処理部分について、次の修正案①〜③を考えた。ここで、修正案①は、プログラム1のままで何も変更しない。また、aとbには、設問1の正しい答えが入っているものとする。
これらの修正案のうち、正しく動作するのはcである。
解答群
ア：修正案①
イ：修正案②
ウ：修正案③
エ：修正案①及び②
オ：修正案①及び③
カ：修正案②及び③
模範解答
c：イ
解説
解答の導き方
この設問では、Mask中の1のビットが0個、つまりMaskの全ビットが0のときに、BitTestが返却値0を返すようにできる修正案を選びます。
プログラム1では、まずaを判定し、成立すれば返却値2を設定します。成立しない場合にbを判定し、検査したビットがすべて0なら返却値0、0と1が混在していれば返却値1を設定します。
aは、検査対象のビットがすべて1かを調べる判定です。これは、DataとMaskの論理積がMaskと等しいかどうかで確かめられます。
Mask中に1のビットがある場合、この式が成り立つのは、Dataの対応するビットもすべて1のときです。
ところが、Maskがすべて0の場合も、この式は成り立ちます。Maskが0なら、Dataの値にかかわらず、DataとMaskの論理積は0になるからです。
そのため、修正案①のままでは、Maskが0のときにaが成立し、返却値2になってしまいます。求める返却値0にはなりません。
そこで、返却値2を設定する条件に「Maskが0ではない」という条件を加えます。これが修正案②です。Maskが0なら返却値2の条件は成立しません。次にbが判定され、DataとMaskの論理積は0なので、返却値0になります。
修正案③のようにb側だけを変更しても、Maskが0のときにaが先に成立して返却値2になる問題は解消されません。後の判定を変更しても、そこまで処理が進まないためです。
したがって、正しく動作するのは修正案②です。
誤りやすいポイント
- Maskが0なら検査するビットがないので返却値0になる、とだけ考えてしまうことです。プログラムでは判定の順番も確認します。
- Data & Mask = Maskは、Maskに1のビットがある場合だけ成立すると思い込むことです。Maskが0の場合も、左右がともに0となって成立します。
- 返却値0側の判定だけを変更すればよいと考えることです。返却値2側の判定が先に成立すると、返却値0側の判定には進みません。
FAQ
Q: Maskが0のとき、なぜDataとMaskの論理積も0になるのですか？
A: 論理積は、対応するビットが両方とも1の場合だけ、結果が1になります。Maskの全ビットが0なら、結果の全ビットも0です。
A: 論理積は、対応するビットが両方とも1の場合だけ、結果が1になります。Maskの全ビットが0なら、結果の全ビットも0です。
Q: Dataが0であることを調べれば、検査対象のビットがすべて0だと分かりますか？
A: いいえ。検査するのはMaskで指定された位置だけです。Maskで指定されていない位置にDataの1があっても、検査結果には影響しません。
A: いいえ。検査するのはMaskで指定された位置だけです。Maskで指定されていない位置にDataの1があっても、検査結果には影響しません。
Q: 返却値0側の判定を変更するだけでは、なぜ不十分なのですか？
A: Maskが0のときは、返却値2側の判定が先に成立するためです。処理が返却値2側で決まると、返却値0側の判定には進みません。
A: Maskが0のときは、返却値2側の判定が先に成立するためです。処理が返却値2側で決まると、返却値0側の判定には進みません。
関連キーワード: ビットマスク、ビット演算、論理積、条件分岐、論理式
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プログラム2、3の処理効率について考えてみる。表1にプログラム2、3の処理量の比較結果を示す。
プログラム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
模範解答
d：ア、e：ア、f：オ
解説
解答の導き方
この問題では、プログラム2とプログラム3の処理量と、プログラム3のビット変換を順に考えます。
d：プログラム2の最大処理量
プログラム2は、Dataの1ビットずつを8回調べます。調べたビットが1かどうかに関係なく、繰返し処理は8回実行されます。
Loopの処理量は1回につき4です。Loopは0から7までの8回に加え、終了を確認する回もあるので、処理量は次のとおりです。
また、Workへの代入とCountへの初期値設定にそれぞれ1、returnに2がかかります。各回で行う選択処理の処理量は3、Workの右シフトの処理量は1です。これらは、調べるビットがすべて0の場合にも必要です。
ここに、検査したビットが1のときだけCountを増やす処理が加わります。最大の処理量になるのは、8ビットすべてが1で、Countを増やす処理が8回行われる場合です。この処理は1回につき1なので、最大処理量は次のとおりです。
e：プログラム3の最小処理量
プログラム3では、Workに1のビットがある間だけ繰返し処理を行います。Workに含まれる1のビットをすべて取り除くため、1のビットが0個なら繰返し処理は行われません。
繰返し処理に入るかを調べる条件は、処理量2です。1のビットが0個の場合も、繰返しを始める前に条件を1回確認します。
WorkとCountの初期設定には合計2、条件確認には2、returnには2がかかります。したがって、最小処理量は次のとおりです。
f：αの行で2回実行した後のWork
αの行では、Workから1を引いた値と、元のWorkとの論理積を取ります。論理積（対応するビットが両方とも1のときだけ1にする演算）によって、Workの最も右にある1のビットが1個消えます。
問題文では、引数Dataが「01101010」Bです。最初のWorkは「01101010」Bです。
したがって、αの行を2回実行した後のWorkは「01100000」Bです。選択肢ではオに当たります。
この変換で、Workに残っている1のビットが実行のたびに1個ずつ減ります。そのため、繰返し回数は、最初のDataに含まれる1のビットの個数と同じになります。
プログラム3の最大処理量も確認します。
Dataの1のビットが個あるとします。条件確認は繰返しの各回に加えて、終了を確認する回もあるので、回です。初期設定とreturnの処理量は合計4、条件確認の処理量は、繰返し1回分の処理量はCountの更新とWorkの更新を合わせてです。
Dataの1のビットが個あるとします。条件確認は繰返しの各回に加えて、終了を確認する回もあるので、回です。初期設定とreturnの処理量は合計4、条件確認の処理量は、繰返し1回分の処理量はCountの更新とWorkの更新を合わせてです。
8ビットすべてが1ならなので、最大処理量は次のとおりです。
誤りやすいポイント
- プログラム2の繰返し回数は、Dataに含まれる1の個数ではなく、常に8回です。1のビットが0個でも、8ビットを順に確認します。
- プログラム2の最大処理量を求めるときは、固定でかかる処理量に加え、Countを増やす処理が何回実行されるかも考えます。
- プログラム3の条件確認は、繰返し本体の回数と同じとは限りません。繰返しを終了するための最後の確認も必要です。
- Workから単純に1を引くだけではなく、引いた値と元のWorkとの論理積まで行います。この組合せで、最も右にある1のビットが消えます。
FAQ
Q: プログラム3は、なぜDataの1のビット数だけ繰り返すのですか？
A: αの行を実行するたびに、Workに残っている1のビットが1個ずつ消えるからです。Workに1がなくなると、繰返し条件が成り立たなくなります。
A: αの行を実行するたびに、Workに残っている1のビットが1個ずつ消えるからです。Workに1がなくなると、繰返し条件が成り立たなくなります。
Q: プログラム2とプログラム3では、繰返しの考え方がどう違いますか？
A: プログラム2は8ビットをすべて順番に調べます。プログラム3は、Workに残る1のビットを1個ずつ消すため、1のビットの個数だけ繰り返します。
A: プログラム2は8ビットをすべて順番に調べます。プログラム3は、Workに残る1のビットを1個ずつ消すため、1のビットの個数だけ繰り返します。
Q: 8ビット符号なし整数として減算するのは、なぜ重要ですか？
A: 扱うビット数を8ビットに固定するためです。ビットを使った計算では、減算結果も8ビットとして扱うことで、Workとの論理積の結果を正しく決められます。
A: 扱うビット数を8ビットに固定するためです。ビットを使った計算では、減算結果も8ビットとして扱うことで、Workとの論理積の結果を正しく決められます。
関連キーワード: ビット演算、論理積、論理シフト、ビットカウント、繰返し処理
