アルゴリズム問題 2進数がわかれば 50 ％以上正解できる「符号付き2進数の乗算」

矢沢久雄
2022-05-06 更新

この記事は基本情報技術者試験の旧制度（ 2022 年以前）の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。ご注意くださいませ。

基本情報技術者試験の受験者の多くは、午後試験のアルゴリズム問題を苦手としています。しかし、その苦手なアルゴリズム問題で、 50 % 以上の正解が得られないと、合格は望めないでしょう。

この連載では、これまでに実施された基本情報技術者試験の過去問題を例にして、最低でも 50 % 正解できる解き方を紹介します。

今回は、平成 22 年度秋期「符号付き 2 進数の乗算」を取り上げます。

1 2 進数の取り扱いを習得しておく
2 説明の番号と対応付ける（設問 1 の空欄 a 、 b 、 c ）
3 選択肢を見て常識的に判断する（設問 2 の空欄 g ）

2 進数の取り扱いを習得しておく

平成 22 年度秋期「符号付き 2 進数の乗算」の問題を見てみましょう。以下に、問題と解答へのリンクがありますので、問題にざっと目を通してください。

平成 22 年度秋期午後	問題	解答

基本情報技術者試験のアルゴリズム問題には、 2 進数の知識が必要になる問題が出ることがよくあります。この問題は、その好例です。

問題には、プログラム 1 とプログラム 2 という 2 つのプログラムが示されていますが、どちらにも「拡張（符号拡張とも呼びます）」や「算術シフト」など、 2 進数の取り扱いに関する言葉があります。

プログラムは横スクロールできます

〔プログラム 1 〕

○プログラム1 (M, N)
○符号付き 2 進整数型： M, N, R
○整数型： L
・M を 5 ビットの符号付き 2 進数に拡張
・N を 8 ビットの符号付き 2 進数に拡張
・R のビット番号 7 ～ 0 に N を複写
・R のビット番号 12 ～ 8 を 0 で初期化
■ L: 1, L ≦ 8, 1
| ▲  R のビット番号 0 のビットが 1
| |・ R のビット番号 12 ～ 8 の内容に M の値を加算
| ▼
|・ R の全 13 ビットを右に 1 ビット算術シフト    /* 空いたビット位置には */
■						/* 符号と同じものが入る */
・return ( R のビット番号 7 ～ 0 の内容)      /* 返却値（括弧内）を返す */❶❷❸❹❺❻❼❽

〔プログラム 2 〕

○プログラム2 (M, N)
○符号付き 2 進整数型: M, N, R
○整数型: L
・M を 5 ビットの符号付き 2 進整数に拡張
・R のビット番号 4 ～ 1 に N を複写
・R のビット番号 9 ～ 5 及び 0 を 0 で初期化
■ L: 1, L ≦ 4, 1
| ▲ R のビット番号 1 のビットが 0 かつ R のビット番号 0 のビットが 1
| | ・R のビット番号 9 ～ 5 の内容に M の値を加算
| ▼
| ▲ R のビット番号 1 のビットが 1 かつ R のビット番号 0 のビットが 0
| | ・R のビット番号 9 ～ 5 の内容から M の値を減算
| ▼
| ・R の全 10 ビットを右に 1 ビット算術シフト /* 空いたビット位置には */
■                                         /* 符号と同じものが入る */
・return( R のビット番号 8 ～ 1 の内容 ) /* 返却値(括弧内)を返す */❶❷❸❹❺❻❼❽❾

午前試験と午後試験を含めて、基本情報技術者試験の問題を解くために必要とされる2進数の知識には、以下に示したものがあります。ここでは、それぞれの説明をしませんが、もしも知らないものがあれば、教材を参照して習得しておきましょう。

基本情報技術者試験に必要な 2 進数の知識

10 進数と 2 進数の変換
2 進数と 16 進数の変換
2 の補数表現
拡張（符号拡張）
論理シフトと算術シフト
マスク演算
固定小数点数と浮動小数点数

説明の番号と対応付ける（設問 1 の空欄 a 、 b 、 c ）

基本情報技術者試験のアルゴリズム問題には、アルゴリズムの説明に番号が示されていて、それとプログラムを対応付ければ解けるという問題が出ることがよくあります。この問題は、その好例でもあります。

ただし、この問題は、ちょっと変わっています。擬似言語で示されたプログラムがアルゴリズムの説明になっていて、図に示された手順（具体的なデータを処理する手順）の穴埋めをします。この穴埋めでは、説明の番号と図に示された番号を対応付けることで、容易に答えを得られます。

以下は、設問 1 の空欄 a と b の答えを得る手順です。プログラム全体の内容を理解できなくても、手順にしたがってデータを処理すれば、穴埋めができます。

| |・ R のビット番号 12 ～ 8 の内容に M の値を加算
| ▼
|・ R の全 13 ビットを右に 1 ビット算術シフト	/* 空いたビット位置には */
■						/* 符号と同じものが入る */❻❼

以下は、設問 1 の空欄 c の答えを得る手順です。ここでも、プログラム全体の内容を理解できなくても、手順にしたがってデータを処理すれば、穴埋めができます。

| | ・R のビット番号 9 ～ 5 の内容から M の値を減算
| ▼
| ・R の全 10 ビットを右に 1 ビット算術シフト /* 空いたビット位置には */
■                                         /* 符号と同じものが入る */
・return( R のビット番号 8 ～ 1 の内容 ) /* 返却値(括弧内)を返す */❼❽

選択肢を見て常識的に判断する（設問 2 の空欄 g ）

基本情報技術者試験の設問の中には、解答群の選択肢を見て常識的に判断できるものが時々あります。「えっ！こんな簡単でいいの？」と言いたくなるような設問です。この問題の設問 2 の空欄 g は、正にその好例です。

おそらく、空欄 d 、 e 、 f が、かなり難しいので、空欄 g を簡単にしたのでしょう。以下は、問題と解答群です。

プログラム 1 では， N のビットが 1 の位置で加算をするので，例えば N = 7 ( 2 進数で 0111 ) なら、加算が3回必要である。一方，プログラム 2 では， N の各ビットを最下位から順に調べ， 1 が現れたけた位置では減算をし、次に 1 の並びが途切れて 0 が現れたけた位置では加算をする，という処理を繰り返す。例えば N = 7 ( 2 進数で 0111 ) の場合， M × 7 を M x ( g ) として計算をするので， 2 進数での加減算の回数が 2 回で済む。

g に関する解答群

ア　-2⁰ + 2³
イ　-2⁰ + 2⁴
ウ　-2¹ + 2³
エ　-2¹ + 2⁴

問題をすべて読む必要はありません。

M × 7 を M x ( g )として計算

の部分だけに注目してください。

M × 7 という計算をするのですから、

M x ( g )

の空欄 g には 7 になるものが入るはずです。　その考えで、解答群を見てみましょう。

実際の数値を使った式が示されています。　それぞれを計算すると、以下のように選択肢アだけが　7　になるので、選択肢アが正解です。「えっ！こんな簡単でいいの？」ですね。

ア　-2⁰ + 2³ = -1 + 8 = 7 正解
イ　-2⁰ + 2⁴ = -1 + 16 = 15
ウ　-2¹ + 2³ = -2 + 8 = 6
エ　-2¹ + 2⁴ = -2 + 16 = 14

この問題には、設問 1 に空欄 a 、 b 、 c 、設問 2 に空欄 d 、 e 、 f 、 g があり、全部で 7 項目です。ここまでで、 a 、 b 、 c 、 g の 4 項目に正解できたので、それぞれの配点はわかりませんが（午後試験の設問ごとの配点は公開されていません）、きっと 50 % に達したでしょう。

今回は、