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


2022-11-28 更新
info2022 年 11 月

科目 B 問題の新しい擬似言語に合わせて、プログラムを変更しました。
なお、本記事では過去問題を一部改変しています。

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

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

そのために、旧制度の午後試験のアルゴリズム過去問題の一部をアレンジした練習問題を作りました。 とても短い問題ですので、気軽に取り組んでください。

練習問題

問 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		/* 返却値 */

  if ( a )
    RC ← 2		/* 返却値は 2 */
  elseif ( b )
    RC ← 0		/* 返却値は 0 */
  else
    RC ← 1		/* 返却値は 1 */
  endif

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

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

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

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

 

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

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

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

◯整数型: BitTest( 8 ビット論理型: Data, 8 ビット論理型: Mask)
  整数型: RC		/* 返却値 */

  if ( a )
    RC ← 2		/* 返却値は 2 */
  elseif ( b )
    RC ← 0		/* 返却値は 0 */
  else
    RC ← 1		/* 返却値は 1 */
  endif

/* 返却値 */ というコメントから、 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試験は、
免除できます。
独習ゼミで科目A試験を1年間免除して、科目B試験だけに集中しましょう。
免除試験を受けた 74.9% の方が、
科目A免除資格を得ています。
科目A免除試験 最大 2 回の
受験チャンス !
info_outline
科目A免除試験 最大 2 回の
受験チャンス !
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズムとプログラミング問題を解くコツ』の連載一覧 label 著者