アルゴリズム問題 具体化すれば 50 ％ 以上正解できる「ビットの検査」
2022-05-06 更新
error
この記事は基本情報技術者試験の旧制度（ 2022 年以前）の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。 ご注意くださいませ。
基本情報技術者試験の受験者の多くは、午後試験のアルゴリズム問題を苦手としています。しかし、その苦手なアルゴリズム問題で、 50 % 以上の正解が得られないと、合格は望めないでしょう。
この連載では、これまでに実施された基本情報技術者試験の過去問題を例にして、最低でも 50 % 正解できる解き方を紹介します。
今回は、平成 24 年度 春期 問 8 「ビットの検査」を取り上げます。
問題に示された具体例を見てプログラムの機能を理解する
平成 24 年度 春期「ビットの検査」の問題を見てみましょう。 以下に、問題と解答へのリンクがありますので、問題にざっと目を通してください。
| 平成 24 年度 春期 午後 | 問題 | 解答 |
|---|
この問題の内容は、前半部（設問 1 、設問 2 ）と後半部（設問 3 ）の 2 部構成になっています。
前半部は、 8 ビットの引数 Data の中で、 8 ビットの引数 Mask で指定したビット位置にあるビットの値を検査した結果を返す BitTest 関数です。
後半部は、 8 ビットの引数 Data の中にある 1 の個数を返す BitCount 関数です。
前半部の BitTest 関数のプログラムは、以下に示したように、とてもシンプルであり、プログラムの機能を理解できれば、問題を解けるでしょう。 この前半部で、 50 % の正解を目指すことにします。
○整数型関数 : BitTest (8 ビット論理型: Data, 8 ビット論理型: Mask) ○整数型: RC /* 返却値 */ ▲ a | • RC ← 2 /* 返却値は 2 */ +――― | ▲ b | | • RC ← 0 /* 返却値は 0 */ | +――― | | • RC ← 1 /* 返却値は 1 */ | ▼ ▼ • return RC /* RC を返却値として返す */
以下は、問題に示された BitTest 関数の説明です。この説明を読んだだけでは、プログラムの機能がよくわかりませんね。
整数型関数 BitTest を，次のとおりに宣言する。
〇整数型関数 : BitTest (8 ビット論理型: Data, 8 ビット論理型: Mask)
検査される 8 ビットのデータは入力用の引数 Data に，検査をするビット位置の情報は入力用の引数 Mask に，それぞれ格納されている。 Mask 中のビットの値が 1 で あるビット位置に対応した Data 中のビットを検査して，次の返却値を返す。ここで， Mask 中には 1 のビットが 1 個以上あるものとする。
- 返却値 0:
- 検査した全てのビットが 0
- 1:
- 検査したビット中に 0 と 1 が混在
- 2:
- 検査した全てのビットが 1
おそらく出題者も「説明だけではわからないだろう」と思ったのでしょう。 そこで、説明の後に、以下の具体例を示しています。
この具体例を見れば、プログラムの機能がわかるはずです。
BitTest 関数は、引数 Mask の中にある 1 の位置で、引数 Data をチェックする桁を指定します。 BitTest 関数は、返却値として、チェックする桁が全て 0 なら 0 を返し、 0 と 1 が混在していれば 1 を返し、全て 1 なら 2 を返します。
このように、問題に具体例が示されているときは、それを見れば、短い時間にプログラムの機能を理解できるようになっています。 問題に具体例があったら「ヒントだ！」と思ってください。
選択肢に示された変数に具体的なデータを想定して考える（設問 1 ）
プログラムの機能を理解できたので、設問を解いてみましょう。 設問 1 は、 BitTest 関数のプログラムの穴埋めです。 以下に、再度プログラムを掲載します。
空欄 a が真なら返却値を 2 にしています。 したがって、空欄 a は、チェックする桁が全て 1 であることの条件です。
空欄 b が真なら返却値を 0 にしています。 したがって、空欄 b は、チェックする桁が全て 0 であることの条件です。
○整数型関数 : BitTest (8 ビット論理型: Data, 8 ビット論理型: Mask) ○整数型: RC /* 返却値 */ ▲ a | • RC ← 2 /* 返却値は 2 */ +――― | ▲ b | | • RC ← 0 /* 返却値は 0 */ | +――― | | • RC ← 1 /* 返却値は 1 */ | ▼ ▼ • return RC /* RC を返却値として返す */
以下は、空欄 a と空欄 b の選択肢です。
“&” は AND 演算（論理積）を意味し、 “|” は OR 演算（論理和）を意味しています。 これらは、条件を結ぶ論理演算ではなく、 2 つの 2 進数の対応する桁同士で論理演算をするものです。
それでは、これらの論理演算を使って、チェックする桁が全て 1 であることと、チェックする桁が全て 0 であることは、どうすれば判断できるのでしょうか？
ア (Data & Mask) = "00000000" B イ (Data & Mask) = Data ウ (Data & Mask) = Mask エ (Data | Mask) = "00000000" B オ (Data | Mask) = Mask
こういうことを頭の中だけで考えていると、どんどん時間が経過してしまいます。 選択肢があるのですから、それらをよく見てください。
どの選択肢でも、行っている論理演算は、 Data & Mask（ AND 演算）と Data | Mask （ OR 演算）のいずれかなのですから、 Data と Mask に具体的なデータを想定して考えましょう。 そうすれば、短い時間に正解を選ぶことができます。
返却値が 2 （チェックする桁が全て 1 である）になる具体例として、問題に示されていた
Data = 00110011
および
Mask = 00010001
を想定してみましょう。
00110011 Data
AND 00010001 Mask
――――――――――――――――――
00010001
00110011 Data
OR 00010001 Mask
――――――――――――――――――
00110011
以上のように、 AND 演算の結果は 00010001 になり（これは、 Mask と同じであり選択肢ウです）、 OR 演算の結果は 00110011 になります（これは、 Data と同じであり選択肢にありません）。
したがって、選択肢ウが正解です。
返却値が 0 （チェックする桁が全て 0 である）になる具体例は、問題に示されていないので、先ほどの具体例をアレンジして
Data = 00110011
および
Mask = 10001000
を想定してみましょう。
00110011 Data
AND 10001000 Mask
――――――――――――――――――
00000000
00110011 Data
OR 10001000 Mask
――――――――――――――――――
10111011
以上のように、 AND 演算の結果は 00000000 になり（これは、選択肢アです）、 OR 演算の結果は 10111011 になります（これは、選択肢にありません）。
したがって、選択肢アが正解です。
具体例を想定してプログラムをトレースする（設問 2 ）
設問 2 は、 BitTest 関数で引数 Mask を 00000000 （チェックする桁の指定なし）としたときに、返却値として 0 を返すようにするには、プログラムをどのように修正すればよいかという内容です。 変更なしも含めて、以下の 3 つの修正案が示されています。
問題に
空欄 a と空欄 b には、設問 1 の正しい答えが入っているものとする
とあるので、ここでは、それぞれの空欄にプログラムを入れてあります。
▲ (Data & Mask) = Mask | • RC ← 2 +――― | ▲ (Data & Mask) = "00000000" B | | • RC ← 0 | +――― | | • RC ← 1 | ▼ ▼ • return RC
▲ (Data & Mask) = "00000000" B | • RC ← 0 +――― | ▲ (Data & Mask) = Mask | | • RC ← 2 | +――― | | • RC ← 1 | ▼ ▼ • return RC
• RC ← 2 ▲ (Data & Mask) = "00000000" B | • RC ← 2 ▼ ▲ (Data & Mask) = Mask | • RC ← 1 ▼ ▼ • return RC
解答群
ア 修正案 looks_one イ 修正案 looks_two
ウ 修正案 looks_3 エ 修正案 looks_one 及び looks_two
オ 修正案 looks_one 及び looks_3 カ 修正案 looks_two及び looks_3
この設問は、具体例を想定してプログラムをトレースすることで、解くことができます。
Data = 00110011
および
Mask = 00000000
を想定してみましょう。
〔修正案 looks_one (変更なし) 〕
▲ (Data & Mask) = Mask | • RC ← 2 +――― | ▲ (Data & Mask) = "00000000" B | | • RC ← 0 | +――― | | • RC ← 1 | ▼ ▼ • return RC(Data & Mask) = Mask となり、
変数 RC に 2 が格納される。返却値として 2 が返される
〔修正案 looks_two 〕
▲ (Data & Mask) = "00000000" B | • RC ← 0 +――― | ▲ (Data & Mask) = Mask | | • RC ← 2 | +――― | | • RC ← 1 | ▼ ▼ • return RC(Data & Mask) = 00000000 となり、
変数 RC に 0 が格納される。返却値として 0 が返される
〔修正案 looks_3 〕
• RC ← 2 ▲ (Data & Mask) = "00000000" B | • RC ← 2 ▼ ▲ (Data & Mask) = Mask | • RC ← 1 ▼ ▼ • return RC(Data & Mask) = 00000000 となり、
いったん変数 RC に 0 が格納される。(Data & Mask) = Mask ともなるので、
変数 RC が 2 で上書きされる。返却値として 2 が返される
以上のように、修正案 looks_one では、
Data & Mask = Mask
となるので、返却値として 2 が返されます。
修正案 looks_two では、
Data & Mask = 00000000
となるので、返却値として 0 が返されます。
修正案 looks_3 では、
Data & Mask = 00000000
となるので返却値を格納する変数 RC にいったん 0 が格納されますが、
Data & Mask = Mask
も成り立つので変数 RC が 2 で上書きされて、返却値として 2 が返されます。
したがって、修正案 looks_two だけが正しく動作し、選択肢イが正解です。
今回は、
- 「問題に示された具体例を見てプログラムの機能を理解する」
- 「選択肢に示された変数に具体的なデータを想定して考える」
- 「具体例を想定してプログラムをトレースする」
という解き方を紹介しました。
どの解き方にも「具体例」や「具体的」という言葉があります。 これは、他人（出題者）が作ったプログラムを短い時間で読み取るには、とにかく具体例を想定することが重要だからです。
今後も、この連載では、アルゴリズム問題で最低でも 50 % 正解できる解き方を、あれこれと紹介していきます。少しでも、皆様の参考になれば幸いです。
それでは、またお会いしましょう！
label 関連タグ免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
