2進数の知識が必要なプログラム|アルゴリズム問題を解くコツ


2021-01-08 更新

この連載では、基本情報技術者試験で、多くの受験者が苦手意識を持っている午後試験の「アルゴリズム穴埋め問題」に的を絞って、正解を見出すポイントを詳しく説明します。

苦手を克服するには、短いプログラムを何度も練習して、穴埋めに慣れることが重要です。

そのために、実際の試験問題の一部をアレンジした練習問題を作りました。 とても短い問題ですので、気軽に取り組んでください。

info編集部注: 本記事では過去問題を一部改変しています。

練習問題

問 8 (平成 24 年度 春期 午後)を一部改変

関数 BitTest は、 8 ビットのデータ中の指定したビット位置の値を検査し、その結果を返す。 検査される 8 ビットのデータは引数 Data に、検査するビット位置は引数 Mask に、それぞれ格納される。 Mask 中のビットの値が 1 であるビット位置に対応した Data 中のビットを検査し、返却値として、検査した全てのビットが 0 なら 0 を、検査したビット中に 0 と 1 が混在しているなら 1 を、検査した全てのビットが 1 なら 2 を、それぞれ返す。

swipeアルゴリズムや表は横スクロールできます

例 1

ビット番号 7 6 5 4 3 2 1 0
Data 0 1 0 1 0 1 0 1
Mask 1 1 1 0 0 0 0 0
返却値 1
例 2

ビット番号 7 6 5 4 3 2 1 0
Data 0 0 1 1 0 0 1 1
Mask 0 0 0 1 0 0 0 1
返却値 2

プログラム中のabに入る正しい答えを、解答群の中から選べ。 なお、本問において、演算子 "&""|" は、AND および OR のビット演算を求めるもとのし、 "~"B という表記は、 8 ビット論理型定数( 8 ビットの 2 進数)を表す。 Mask 中には、 1 のビットが 1 個以上あるものとする。

[プログラム]

○整数型:BitTest( 8 ビット論理型:Data, 8 ビット論理型:Mask)
○整数型:RC		/* 返却値 */
▲ a
|・RC ← 2		/* 返却値は2 */
+---
|▲ b
||・RC ← 0		/* 返却値は0 */
|+---
||・RC ← 1		/* 返却値は1 */
|▼
▼
・return RC		/* RCを返却値として返す */

a と b の解答群

ア (Data & Mask) = "00000000"B
イ (Data & Mask) = Data
ウ (Data & Mask) = Mask
エ (Data | Mask) = "00000000"B
オ (Data | Mask) = Mask

ポイント1:問題に示された具体例から問題の意味を理解する

この問題は、問題文の説明を読んだだけでは、何をするプログラムかよくわからないでしょう。 どうやら出題者も、そう思ったようで、具体例を 2 つ示しています。

このような場合には、具体例を見れば、問題の意味を理解できるようになっているはずです。

例 1

ビット番号
7 6 5 4 3 2 1 0
Data
0 1 0 1 0 1 0 1
Mask
1 1 1 0 0 0 0 0
返却値
1
0 と 1 が混在
検査位置
例 1 では 11100000 という Mask の 1 の位置(ビット番号 7 、 6 、 5 )が検査位置です。
Data では、この検査位置が 0 、 1 、 0 なので、 0 と 1 が混在しています。
したがって、返却値は 1 になります。

つまり、 Mask 中で 1 になっている部分で検査位置を指定し、 Data 中でその位置が 0 だけなのか、 0 と 1 が混在しているのか、 1 だけなのかを返却値 0 、 1 、 2 で知らせるプログラムなのです。

もうひとつ例があるので、この解釈が合っているかどうかを確認しておきましょう。

例 2

ビット番号
7 6 5 4 3 2 1 0
Data
0 0 1 1 0 0 1 1
Mask
0 0 0 1 0 0 0 1
返却値
2
すべて 1
検査位置
例 2 では 00010001 という Mask の 1 の位置(ビット番号 4 、 0 )が検査位置です。
Data では、この検査位置が 1 、 1 なので、全てが 1 です。
したがって、返却値は 2 になります。

これで、解釈が合っていることを確認できました。

ポイント2:事前に 2 進数の知識を習得しておく

それほど頻度は多くないのですが、基本情報技術者試験の午後アルゴリズム問題には、 2 進数の知識が必要なプログラムが出ることがあります。

午後アルゴリズム問題は必須問題なのですから、 2 進数の知識も必須ということになります。

以下の知識をきちんと習得できているかどうか確認してください。 ここでは、それぞれの知識を詳しく説明しませんが、もしも習得できていないことがあれば、お手元の教材(きっと何らかの教材をお持ちでしょう!)で学習してください。

今回の練習問題では、ビット演算の知識が必要です。

  • 2 進数を 10 進数に変換する
  • 10 進数を 2 進数に変換する
  • 2 進数を 16 進数に変換する
  • 16 進数を 2 進数に変換する
  • 2 の補数表現でマイナスの数を表す
  • 論理シフトと算術シフトの違いがわかる
  • AND 、OR 、XOR のビット演算(ビットごとの論理演算)ができる

ポイント3:コメントをヒントにする

実務で作成されるプログラムでは、プログラムの保守性を高めるために、数多くのコメントが入れてあります。 コメントを読めば、誰でもプログラムの内容を理解できるようにしているのです。

ただし、もしも試験問題のプログラムに数多くのコメントを入れたら、問題がやさしくなり過ぎてしまいます。
とはいえ、まったくコメントを入れなければ、制限時間内に問題を解けなくなってしまうでしょう。

 

そこで、試験問題のプログラムには、少しだけコメントが入れてあります。

このコメントは、コメントというよりも制限時間内に問題を解くためのヒントです。 プログラムの中にコメントを見たら「ヒントだ!」と思って、大いに注目してください。

この問題でも、ヒントとしてコメントが入っています。 以下の /* */ で囲まれた文字列がコメントです。

○整数型:BitTest( 8 ビット論理型:Data, 8 ビット論理型:Mask)
○整数型:RC	/* 返却値 */a
|・RC ← 2	/* 返却値は2 */
+---
|▲ b
||・RC ← 0	/* 返却値は0 */
|+---
||・RC ← 1	/* 返却値は1 */
|▼
▼
・return RC	/* RCを返却値として返す */

/* 返却値 */ というコメントから、 RC という変数が返却値を入れるものであることがわかります。

/* 返却値は2 */ というコメントから、aには返却値を 2 にする条件、つまり Mask で指定した Data のビット位置が全て 1 である条件が入ることがわかります。

/* 返却値は0 */ というコメントから、bには返却値を 0 にする条件、つまり Mask で指定した Data のビット位置が全て 0 である条件が入ることがわかります。

 

/* RCを返却値として返す */ というコメントから、 return という命令が、返却値を返すものであることがわかります。

C 言語、Java 、Python などのプログラミング言語の経験があれば、この return の意味がわかると思いますが、擬似言語仕様書には return が示されていません。 このプログラムでは、仕様書にない表現を使っているので、それをコメントで説明しているのです。 このようなコメントもよくあります。

ポイント4:選択肢の変数に具体的な数値を設定してみる

それでは、プログラムの穴埋めをやってみましょう。

これまでの記事でも何度かポイントとして取り上げてきましたが、基本情報技術者試験の問題は、すべて選択問題なのですから、選択肢を見て答えを選んでください。

aには、 Mask で指定した Data のビット位置が全て 1 である条件が入ります。 これは、選択肢ア~オのどれでしょう。

ア (Data & Mask) = "00000000"B
イ (Data & Mask) = Data
ウ (Data & Mask) = Mask
エ (Data | Mask) = "00000000"B
オ (Data | Mask) = Mask

もしも、「う~む?」と悩んでしまったら、選択肢の変数に具体的な数値を設定してみましょう。

「具体例!」そうです。 問題にも具体例が示されていました。 返却値が 2 になる具体例は、例 2 です。

例 2

ビット番号 7 6 5 4 3 2 1 0
Data 0 0 1 1 0 0 1 1
Mask 0 0 0 1 0 0 0 1
返却値 2

それでは、例 2 の具体例を想定すると、どの選択肢が適切でしょう。

選択肢は、どれも左辺で Data と Mask の AND 演算( & )か OR 演算( | )を行っています。

これも、「う~む?」と悩んでしまったら、実際に AND 演算と OR 演算をやってみればよいのです( AND と OR のビット演算の知識が不安に感じた方は 論理回路 のタグがついた記事で練習してみましょう! )。

    0 0 1 1 0 0 1 1  Data
AND 0 0 0 1 0 0 0 1  Mask
--------------------
    0 0 0 1 0 0 0 1 演算結果・・・ Mask と同じ
    0 0 1 1 0 0 1 1  Data
OR  0 0 0 1 0 0 0 1  Mask
--------------------
    0 0 1 1 0 0 1 1 演算結果・・・ Data と同じ

以上のように、 AND 演算の結果は Mask と同じになります。 これは、選択肢ウです。 OR 演算の結果は Data と同じになります。 これは、選択肢にはありません。

したがって、選択肢にあるウが正解です。 できましたね!

 

bには、 Mask で指定した Data のビット位置が全て 0 である条件が入ります。

この具体例は、問題にありませんでしたが、例 1 と例 2 を参考にして、自分で作ってみましょう。

ここでは、 Data を 00110011 に、 Mask を 11001100 にしてみます。

    0 0 1 1 0 0 1 1  Data
AND 1 1 0 0 1 1 0 0  Mask
--------------------
    0 0 0 0 0 0 0 0 演算結果・・・ "00000000"B
    0 0 1 1 0 0 1 1  Data
OR  1 1 0 0 1 1 0 0  Mask
--------------------
    1 1 1 1 1 1 1 1 演算結果・・・ "11111111"B

以上のように、 AND 演算の結果は "00000000"B になります。 これは、選択肢アです。

OR 演算の結果は "11111111"B になります。 これは、選択肢にはありません。

したがって、選択肢にあるアが正解です。 できましたね!

 

解答a - ウ, b - ア

「習うより慣れろ」ということわざがあります。 アルゴリズム穴埋め問題の克服に関しては、正にその通りでしょう。

この連載では、これからも短い練習問題を掲載していきますので、穴埋めに慣れることを目指してください。

正解を見出すポイントとして、同じことが示されることもあると思いますが、それは、多くの問題に共通したポイントがあるからです。

それでは、またお会いしましょう!

label 関連タグ
新制度でも、
午前免除できます。
独習ゼミで科目 A 試験を免除しましょう。
免除試験を受けた 86% の方が、
1 年間の午前免除資格を得ています。
2023 年 春 向けコース
最大 10 % OFF !
info_outline
2023 年 春 向けコース
最大 10 % OFF !
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズム問題を解くコツ』の連載一覧 label 著者