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


2020-09-08 更新

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

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

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

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

練習問題

info編集部注: スマートフォンでご覧の際は、アルゴリズムや表を横スクロールすると全文をご覧になれます
問 8 (平成 24 年度 春期 午後)を一部改変

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

プログラム中の a  b に入る正しい答えを、解答群の中から選べ。なお、本問において、演算子 "&""|" は、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 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 86% の方が、
午前試験を免除しています。
2021 年度 春期試験 向け
最大 20 % OFF!
info_outline
2021年度 春期試験向け
最大 20 % OFF!
詳しく見てみるplay_circle_filled
label これまでの『アルゴリズム問題を解くコツ』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数

grade IPA認定
午前免除制度対応
eラーニング

人気記事

人気のタグ