基本情報技術者 2010年 秋期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
プログラム1及びプログラム2は、いずれも二つの整数M, Nを受け取り、その積M×Nの値を返す。積は、加減算とシフト演算を使って求める。M, N及び求めた積は、いずれも符号付き2進数の整数で、負数は2の補数で表現する。
〔プログラム1の説明〕
プログラム1が受け取るM, Nは、いずれも4ビットで、各値の範囲は−8〜7である。求めた積M×Nは、8ビットで返す。ただし、プログラム1中では、Mを5ビットに、Nを8ビットに拡張して処理を行う。
Rは13ビットの作業用変数であり、最下位から順にビット番号を0, 1, …とし、最上位（符号ビット）のビット番号を12とする。Rは、指定した一部の範囲（例えば、ビット番号12〜8の上位5ビット）だけを符号付き2進数とみなして部分的な算術演算ができる。また、値の検査のために指定したビット番号の内容を取り出すこともできる。
なお、⑥の行の加算では、けたあふれが起きても無視する。
N=3とし、M=5とM=−5の場合の処理過程を、それぞれ図1，2に示す。図1，2中の記号①〜⑧は、プログラム1の①〜⑧の行の処理と対応している。
〔プログラム2の説明〕
プログラム2が受け取るM, Nは、いずれも4ビットで、各値の範囲は−8〜7である。求めた積M×Nは、8ビットで返す。ただし、プログラム2中では、Mを5ビットに拡張して処理を行う。
Rは10ビットの作業用変数であり、最下位から順にビット番号を0, 1, …とし、最上位（符号ビット）のビット番号を9とする。Rは、指定した一部の範囲（例えば、ビット番号9〜5の上位5ビット）だけを符号付き2進数とみなして部分的な算術演算ができる。また、値の検査のために指定したビット番号の内容を取り出すこともできる。
なお、⑤の行の加算及び⑦の行の減算では、けたあふれが起きても無視する。
M=−5, N=3の場合の処理過程を図3に示す。図3中の記号①〜⑨は、プログラム2の①〜⑨の行の処理と対応している。
設問1：
問題文を見る 図2及び図3中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
b, cに関する解答群
模範解答
a：エ、b：オ、c：イ
解説
解答の導き方
ビット列の基本
- ビット番号は右端から数え、右端がビット番号0です。したがって、図に左から右へ並ぶビット列は、上位のビットから下位のビットの順です。
- 問題文にある「負数は2の補数で表現する」とは、決められたビット数で負数を表す方法です。例えば、4ビットの は、符号付きの値では です。
- 「符号付き2進数に拡張」とは、負数なら左側に符号ビットの1を追加して、表すビット数を増やすことです。したがって、4ビットの を5ビットに拡張すると で、値は変わらず です。
- 「算術シフト」は、符号付きの数に合わせたシフトです。問題文には、右に1ビット算術シフトすると「符号と同じものが入る」とあります。つまり、負数を右にシフトすると、左端には1が入ります。
図2のaとb
プログラム1では、Mを5ビットに拡張して、Rの上位5ビットに加算します。図2では なので、5ビットのMは です。Rの上位5ビットと下位8ビットを分けて追います。
最初のRは、上位5ビットが 、下位8ビットが です。Rのビット番号0が1なので、1回目の繰返しでは上位5ビットにMを加えます。
加算後のRは です。問題文の「Rの全13ビットを右に1ビット算術シフト」を行うと、左端には符号ビットの1が入ります。その結果は です。
aはビット番号12〜7、つまり、この結果の左から6ビット分です。したがって、aは となり、解答群ではエです。
続く2回目の繰返しでは、シフト後のRのビット番号0が1なので、再び上位5ビットにMを加えます。現在の上位5ビット は、5ビットの符号付き数では です。よって、加算結果は になります。5ビットで を表すと です。
加算時に生じる桁あふれは無視するため、上位5ビットは になります。このRを算術右シフトすると、結果は です。
bはビット番号12〜6、つまり左から7ビット分です。したがって、bは となり、解答群ではオです。
図3のc
プログラム2では、Rの上位5ビットをMの値に応じて加算または減算し、その後R全体を算術右シフトします。判断に使うのは、Rのビット番号1と0の組合せです。
図3では なので、5ビットに拡張したMは です。また、4ビットの は です。Nをビット番号4〜1に置き、ビット番号0を0にすると、最初のRは になります。
初期状態のビット番号1・0は です。プログラム2では、この場合に上位5ビットからMを減算します。Mは なので、計算は です。その後、R全体を算術右シフトすると になります。
このRのビット番号1・0は です。プログラム2の条件は「なら加算、なら減算」なので、ではどちらも行いません。そのままもう一度算術右シフトすると、Rは です。
cはビット番号9〜3の7ビットです。 の左から7ビットを取り出すと です。したがって、cは となり、解答群ではイです。
誤りやすいポイント
- 算術右シフトの左端を0にしてしまうこと
負数では、左端に符号ビットの1を入れます。図2では、これを0にするとaやbの値が変わります。 - 加算・減算する範囲を取り違えること
プログラム1ではRの上位5ビットだけにMを加算します。下位8ビットまで一緒に加算するわけではありません。 - ビット番号1と0の順を逆に読むこと
プログラム2の条件は、ビット番号1を先、ビット番号0を後にして組み合わせを判断します。なら減算、なら加算です。 - 取り出すビット数を間違えること
aはビット番号12〜7の6ビット、bはビット番号12〜6の7ビット、cはビット番号9〜3の7ビットです。
FAQ
Q: なぜ負数を拡張するときは、左側に1を加えるのですか？
A: 負数の符号ビットを保ち、元の値を変えないためです。例えば、4ビットの は、5ビットでは と表せます。どちらも符号付きの値は です。
A: 負数の符号ビットを保ち、元の値を変えないためです。例えば、4ビットの は、5ビットでは と表せます。どちらも符号付きの値は です。
Q: プログラム2で、ビット番号1・0が のときに何もしないのはなぜですか？
A: プログラム2では、とのときだけ加算または減算します。とでは、どちらの条件も成立しないため、上位5ビットを変更せずにシフトします。
A: プログラム2では、とのときだけ加算または減算します。とでは、どちらの条件も成立しないため、上位5ビットを変更せずにシフトします。
Q: 桁あふれを無視するとは、どういうことですか？
A: 決められたビット数に収まる部分だけを使い、はみ出した桁は捨てることです。例えば、5ビットの計算で6ビット目に桁が出ても、その桁は結果に含めません。
A: 決められたビット数に収まる部分だけを使い、はみ出した桁は捨てることです。例えば、5ビットの計算で6ビット目に桁が出ても、その桁は結果に含めません。
関連キーワード: 2の補数、符号拡張、算術右シフト、Booth法
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
(1) プログラム1の③の行では、積を求めるためのRの下位8ビットにNの値を設定している。それは、効率を考えてdためである。
(2) プログラム2はプログラム1と比べて、加減算の回数が少なくて済む場合がある。特に効果があるのはN<0のときで、このとき、プログラム1では、⑥の行の加算は最低でもe回実行されるが、プログラム2では、⑤の行の加算と⑦の行の減算との合計は最高でもf回で済む。
(3) プログラム1では、Nのビットが1の位置で加算をするので、例えばN=7（2進数で0111）なら、加算が3回必要である。一方、プログラム2では、Nの各ビットを最下位から順に調べ、1が現れたけた位置では減算をし、次に1の並びが途切れて0が現れたけた位置では加算をする、という処理を繰り返す。例えばN=7（2進数で0111）の場合、M×7をM×(g)として計算をするので、2進数での加減算の回数が2回で済む。
dに関する解答群
ア：与えられたMの値が1のとき、ループ内の加算処理の実行回数を0にできる
イ：与えられたNの値が1のとき、ループ内の加算処理の実行回数を0にできる
ウ：中間結果のシフトとNのビットの順次取出しを、1回のシフトで済ませる
エ：中間結果のシフトによって、与えられたNの値の符号検査をなくせる
e, fに関する解答群
ア：1
イ：2
ウ：3
エ：4
オ：5
カ：6
gに関する解答群
ア：
イ：
ウ：
エ：
模範解答
d：ウ、e：オ、f：ウ、g：ア
解説
解答の導き方
この問題では、プログラム1とプログラム2が、ビットを見ながらどのように積を求めるかを確認します。
負数をビット列で表す方式を2の補数といいます。また、ビット数を増やすときに数の符号を保つため、符号ビットを左側に加えることを符号拡張といいます。符号付きの数を右へずらし、空いた左端に符号ビットを入れる操作が算術右シフトです。
(1) d
プログラム1では、③で「Rの下位8ビットにNの値」を入れます。その後、⑦でR全体を算術右シフトし、⑤でビット番号0を調べます。
最初はNの最下位ビットがビット番号0にあります。1回右シフトすると、Nの次のビットがビット番号0に移動します。同時に、積を求める途中の値も右へシフトされます。
つまり、Nのビットを順番に調べることと、中間結果をシフトすることを、同じ1回のシフトで行えます。したがって、③でNをRの下位8ビットに置く理由は、**「中間結果のシフトとNのビットの順次取出しを、1回のシフトで済ませる」**ためです。選択肢はウです。
(2) e と f
まず、プログラム1の加算回数を考えます。プログラム1では、Nを8ビットに符号拡張し、8回の繰返しでビットを1つずつ調べます。ビットが1なら⑥で加算します。
Nが負のとき、4ビットの最上位ビットは1です。8ビットに符号拡張すると、左側にも1が並びます。負の範囲で1の数が最も少ないNは−8で、その8ビット表現は です。1は5個あります。
負のNは−8から−1までなので、8ビット表現に含まれる1の数は最低でも5個です。したがって、プログラム1では⑥の加算が最低でも5回実行されます。選択肢はオです。
次に、プログラム2の加算と減算の回数を考えます。Nの4ビットを、最上位から とします。初期状態では、Rのビット番号4〜1にNが入り、ビット番号0は0です。
プログラム2が調べるビット番号1と0の組は、繰返しごとに次のように変わります。
組の2ビットが異なるときに、⑤の加算または⑦の減算を1回行います。同じビットが続く組では、どちらも行いません。
これは、5個のビット の隣り合う部分を、4か所調べることに相当します。隣り合うビットが変わるたびに、加算または減算が1回必要です。
Nが負のときは です。この5個のビット列は、最初が0、最後が1なので、隣り合うビットの変化回数は奇数になります。変化できる境界は4か所ありますが、4回変化すると最後は最初と同じ0に戻ってしまいます。したがって、変化回数の最大は、4以下の奇数である3回です。
よって、プログラム2の⑤の加算と⑦の減算の合計は、最高でも3回です。選択肢はウです。
(3) g
N=7の4ビット表現は0111です。ビットを下位から見ると、 、、、 です。
プログラム2が調べる組を順に確認します。
1回目の減算は位の重みが の位置で行われ、4回目の加算は の位置で行われます。そのため、
となり、
として計算できます。したがって、gはアです。
誤りやすいポイント
- プログラム1は8回繰り返しますが、毎回加算するわけではありません。調べたビットが1のときだけ⑥を実行します。
- 負のNを8ビットに符号拡張すると、左側に1が加わります。4ビットのNだけを見て、加算回数を数えないようにしてください。
- プログラム2では、1が並んでいる個数ではなく、隣り合うビットが変わる回数を数えます。同じビットが続く部分では、加算も減算も行いません。
- fでは、5個のビットの間に境界が4か所あることと、端のビットが異なるため変化回数は奇数になることの両方を使います。最大は4ではなく3です。
FAQ
Q: プログラム2では、なぜ1が続いていても毎回加算や減算をしないのですか？
A: 連続する1の区間は、区間の始まりと終わりで表せるためです。プログラム1のように1の数だけ加算するのではなく、ビットの変化する場所だけで加算または減算します。
A: 連続する1の区間は、区間の始まりと終わりで表せるためです。プログラム1のように1の数だけ加算するのではなく、ビットの変化する場所だけで加算または減算します。
Q: 負の数を右にシフトするとき、なぜ算術右シフトを使うのですか？
A: 負の値を保つためです。算術右シフトでは、空いた左端に符号ビットを入れるので、負の値の符号が維持されます。
A: 負の値を保つためです。算術右シフトでは、空いた左端に符号ビットを入れるので、負の値の符号が維持されます。
Q: プログラム2で、ビットの組が00または11のときは、なぜ処理しないのですか？
A: 隣り合うビットが同じで、ビット列に変化がないためです。加算や減算が必要なのは、01または10のようにビットが変わる組です。
A: 隣り合うビットが同じで、ビット列に変化がないためです。加算や減算が必要なのは、01または10のようにビットが変わる組です。
関連キーワード: 2の補数、符号拡張、算術シフト、ビット演算、二進乗算
