基本情報技術者 2018年 春期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラム1の説明〕
0〜65534の整数を表す数字から成る文字列（以下、数字列という）を数値に変換する副プログラムDTOBである。
(1) 文字列は、DC命令の文字定数と同じ形式で主記憶に格納される。数字列567を格納した例を、図1に示す。
(2) 主プログラムは、数字列が格納されている領域の先頭アドレスをGR1に、数字列の長さをGR2に設定して、DTOBを呼ぶ。DTOBは、数値に変換して得た値をGR0に格納して呼出し元に戻る。
(3) 副プログラムDTOBから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：ADDL GR5,GR4
イ：SLL GR4,1
ウ：SLL GR4,2
エ：SLL GR5,1
オ：SLL GR5,2
模範解答
a：オ
解説
解答の導き方
この空欄では、読み取った数字を、これまでに計算した値の次の桁として加える処理を完成させます。
まず、プログラムは数字列を1文字ずつ読み取ります。GR1は読み取る文字の位置、GR2は読み取りを終える位置を表します。「ADDL GR2, GR1」で終わりの位置を求め、「CPL GR1, GR2」と「JZE FIN」で、数字列を最後まで読み取ったかを確認します。
読み取った文字は「LD GR4, 0, GR1」でGR4に入ります。ただし、GR4に入るのは数字の文字コードです。そこで「SUBL GR4, ='0'」によって文字「0」のコードを引き、文字「5」なら数値の5にします。図1では、文字「5」は「#0035」として格納されています。
次に、GR0に入っている計算途中の値を、次の桁に合わせて10倍します。計算途中の値を 、今回読み取った数字を とすると、次に求めたい値は次のとおりです。
「SLL GR0, 1」はGR0の値を左に1ビットずらす命令です。左に1ビットずらすと値は2倍になるので、この時点でGR0は になります。続く「LD GR5, GR0」で、GR5にも を保存します。
空欄では、GR5の値をさらに4倍にする必要があります。GR5にはすでに が入っているため、2ビット左へずらすと、
となります。その後、「ADDL GR0, GR5」でGR0の にGR5の を加えると になり、さらに「ADDL GR0, GR4」で今回の数字 を加えれば、求める になります。
したがって、空欄にはGR5を2ビット左へずらす「SLL GR5, 2」が入ります。
誤りやすいポイント
- 「SLL GR0, 1」だけでは、値は2倍にしかなりません。10倍にするには、GR5に保存した値も使って を作ります。
- GR5には、空欄の処理に入る時点ですでに が入っています。そのため、GR5を2ビットずらすと になります。
- GR4には今回の数字が入っています。GR4をずらすと数字そのものが変わってしまうため、ずらすのはGR5です。
- 数字の文字コードを数値にする命令は「SUBL GR4, ='0'」です。文字コードから「0」の文字コードを引くことで、数字の値を得ます。
FAQ
Q: なぜ、読み取った数字をそのまま加えるだけではいけないのですか？
A: 例えば、すでにある値が12で、次の数字が3なら、次の値は123です。12に3を加えるのではなく、12を10倍してから3を加える必要があります。
A: 例えば、すでにある値が12で、次の数字が3なら、次の値は123です。12に3を加えるのではなく、12を10倍してから3を加える必要があります。
Q: なぜGR5を2ビットずらすのですか？
A: GR5には、先にGR0を1ビットずらした値、つまり が入っています。そこから2ビットずらすと4倍になり、結果は です。これをGR0の に加えて、10倍分の を作ります。
A: GR5には、先にGR0を1ビットずらした値、つまり が入っています。そこから2ビットずらすと4倍になり、結果は です。これをGR0の に加えて、10倍分の を作ります。
Q: 最初の数字を処理するときも、この計算で正しく値が得られますか？
A: はい。最初はGR0が0なので、 となります。以降は、これまでの値を10倍して次の数字を加える処理を繰り返します。
A: はい。最初はGR0が0なので、 となります。以降は、これまでの値を10倍して次の数字を加える処理を繰り返します。
関連キーワード: 文字コード、汎用レジスタ、論理左シフト、10進数、位取り_北京赛车pk
設問2：
問題文を見る 文字列の先頭から数字列を探索し、順に、対応する数値を管理テーブルに格納する副プログラムGETWDを、DTOBを使用して作成した。プログラム2中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム2の説明〕
(1) 文字列は、一つ以上の空白文字で区切られた任意の個数の数字列を含み、最後はピリオドで終わる。最後の数字列とピリオドの間、又は文字列の先頭に一つ以上の空白文字があってもよい。文字列の例を、図2に示す。
(2) 管理テーブルには、文字列中に数字列が現れるごとに、順に1語から成る要素を追加し、数字列を数値に変換して得た値を格納する。数字列の探索が終了したとき、管理テーブルの最後に1語から成る要素を追加し、数値の終わりを示す印として−1を格納する。図2の文字列をGETWDで処理して得た管理テーブルを、図3に示す。
(3) 主プログラムは、文字列が格納されている領域の先頭アドレスをGR1に、管理テーブルの先頭アドレスをGR2に設定して、GETWDを呼ぶ。
(4) 副プログラムGETWDから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
bに関する解答群
ア：JNZ FIN
イ：JNZ LP
ウ：JNZ NUM
エ：JZE FIN
オ：JZE LP
カ：JZE NUM
cに関する解答群
ア：JNZ FIN
イ：JNZ FIN2
ウ：JNZ NUM
エ：JZE FIN
オ：JZE FIN2
カ：JZE NUM
dに関する解答群
ア：LAD GR6,1,GR1
イ：LAD GR6,1,GR6
ウ：LAD GR7,1,GR2
エ：LAD GR7,1,GR7
オ：LD GR6,GR1
カ：LD GR7,GR2
模範解答
b：ウ、c：イ、d：エ
解説
解答の導き方
まず、プログラム2で使うレジスタの役割を整理します。レジスタは、CPUが処理中の値を一時的に置いておく場所です。
- GR6：現在読んでいる文字の位置
- GR7：管理テーブルの次の格納位置
- GR1：処理中の数字列の先頭位置
- GR3：数字列を処理中かどうかを示す状態フラグ。数字列を処理していないときは−1、処理中は0です。
- GR4：読み取った1文字
プログラムは、文字を1文字ずつ読みます。文字列の例では、数字列の間や先頭などに空白文字があり、最後はピリオドで終わっています。
b：空白文字でないときの分岐
「CPL GR4, =' '」は、GR4の文字が空白文字と等しいかを調べます。JNZは、直前の比較結果が等しくなかったときに分岐する命令です。
ピリオドの場合は、その前の「CPL GR4, ='.'」「JZE FIN」で先に処理されます。そのため、ここで空白文字でない文字は数字列の数字です。数字を見つけたらNUMへ進み、数字列の処理を始める必要があります。
したがって、bには JNZ NUM が入ります。
NUMでは、GR3が0なら数字列をすでに処理中なので、そのまま次の文字へ進みます。GR3が−1なら数字列の処理を始めるところなので、GR3を0にして、現在の位置GR6を数字列の先頭位置GR1に記録します。
c：空白文字やピリオドに来たときの処理
空白文字に来ると、プログラムはSETWDを呼びます。ピリオドに来たときも、FINからSETWDを呼びます。SETWDの役割は、処理中の数字列があれば数値に変換して管理テーブルに格納することです。
SETWDでは、最初に「LD GR3, GR3」でGR3の状態を調べます。GR3が−1なら数字列を処理していません。たとえば、先頭の空白文字や数字列の後に続く複数の空白文字では、変換する数字列がありません。この場合は、変換処理をせずにFIN2へ戻る必要があります。
−1は0ではないので、分岐命令はJNZです。よって、cには JNZ FIN2 が入ります。反対に、GR3が0なら数字列を処理中なので、変換処理を続けます。
DTOBに渡す数字列の長さ
数字列を処理中の場合、SETWDはGR2にGR6−GR1を設定します。空白文字またはピリオドに来た時点で、GR6は区切り文字の位置です。GR1は数字列の先頭位置です。その位置の差が、数字列の文字数になります。
たとえば、数字列が1234なら、先頭位置から区切り文字までの差は4です。この長さと先頭位置を使ってDTOBを呼び出し、変換後の値をGR0から管理テーブルへ格納します。
格納後は、GR3を−1に戻して「数字列を処理していない状態」にします。その後、管理テーブルの次の格納位置へ進む必要があります。
d：管理テーブルの次の格納位置への移動
管理テーブルには、数字列ごとに1語から成る要素を追加します。したがって、1つの数値を格納したら、GR7を1語分だけ進めます。
この処理に当たるのは LAD GR7,1,GR7 です。よって、dにはこの命令が入ります。
図2の文字列では、先頭の空白文字ではGR3が−1なので数字列の変換をせず、数字列が始まるとGR3を0にして先頭位置を記録します。数字列の後の空白文字で数値を変換して格納し、GR7を次の格納位置へ進めます。空白文字が続いても、GR3は−1なので余分な変換はしません。
最後の数字列は、後ろに空白文字があればその空白文字で変換されます。空白文字がない場合も、ピリオドの位置でSETWDが呼ばれて変換されます。その後、FINでGR7の位置に−1を格納し、数値の終わりを示します。図3の管理テーブルに、数字列ごとの値と最後の−1が格納される流れです。
誤りやすいポイント
-
空白文字を見つけたら、必ず数字列を変換すると思い込むこと。
先頭の空白文字や、数字列の後に続く複数の空白文字では、変換対象の数字列がありません。GR3が−1ならFIN2へ戻ります。 -
JNZとJZEの意味を取り違えること。
JNZは直前の結果が0でないとき、JZEは0のときに分岐します。GR3が−1ならJNZで分岐し、GR3が0なら分岐しません。 -
GR7を数字列の長さだけ進めると思い込むこと。
GR7は管理テーブルの位置を表します。数字列の長さではなく、数値を1つ格納するたびに1語分進めます。 -
最後の数字列の処理を見落とすこと。
最後の数字列は、後ろの空白文字またはピリオドでSETWDが呼ばれたときに変換されます。変換の後に、数値の終わりを示す−1が格納されます。
FAQ
Q: 先頭の空白文字でSETWDを呼んでも、問題はありませんか？
A: 問題ありません。GR3は−1なので、SETWD内のJNZ FIN2で変換処理をせずに戻ります。
A: 問題ありません。GR3は−1なので、SETWD内のJNZ FIN2で変換処理をせずに戻ります。
Q: 数字列の後に空白文字が複数ある場合、同じ数字列を何度も格納しませんか？
A: 格納しません。最初の空白文字で数字列を変換した後、GR3が−1に戻ります。続く空白文字では、変換せずにFIN2へ戻ります。
A: 格納しません。最初の空白文字で数字列を変換した後、GR3が−1に戻ります。続く空白文字では、変換せずにFIN2へ戻ります。
Q: ピリオドの前に空白文字がある場合、最後の数字列はどう処理されますか？
A: 数字列の後の空白文字で変換されます。ピリオドでSETWDが呼ばれたときはGR3が−1なので変換を行わず、FINで−1を格納します。
A: 数字列の後の空白文字で変換されます。ピリオドでSETWDが呼ばれたときはGR3が−1なので変換を行わず、FINで−1を格納します。
関連キーワード: 状態フラグ、条件分岐、文字列処理、アドレス、番兵値
設問3：
問題文を見る GETWDを使用して、二つの整数の積を求める副プログラムMULTを作成した。プログラム3中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム3の説明〕
(1) MULTは、数字列を二つだけ含む、〔プログラム2の説明〕の(1)で示した形式の文字列について、最初の数字列に対応する数値を被乗数とし、2番目の数字列に対応する数値を乗数として乗算を行う。乗算においてあふれは発生しないものとする。
(2) 主プログラムは、文字列が格納されている領域の先頭アドレスをGR1に設定して、MULTを呼ぶ。MULTは、演算結果をGR0に格納して呼出し元に戻る。
(3) 副プログラムMULTから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
eに関する解答群
ア：JMI FIN
イ：JMI NEXT
ウ：JPL FIN
エ：JPL NEXT
オ：JZE FIN
カ：JZE NEXT
fに関する解答群
ア：ADDL GR0,GR5
イ：ADDL GR5,GR4
ウ：LD GR5,GR4
エ：SLL GR5,1
オ：SRL GR5,1
模範解答
e：オ、f：オ
解説
解答の導き方
この問題では、文字列から取り出した二つの数を掛ける処理を完成させます。プログラムはアセンブリ言語（CPUへの命令を短い記号で表す言語）で書かれています。
まず、GETWDを呼び出した後、プログラムは管理テーブルの先頭の値をGR4に、次の値をGR5に読み込みます。汎用レジスタ（計算中の値を一時的に置く場所）の役割は、ここでは次のとおりです。
- GR4：被乗数
- GR5：乗数
- GR0：計算結果
GR0は最初に0に設定されます。以降、GR5の値を使って、GR4の値をGR0に加えるかどうかを決めます。
ポイントは、乗数を2進数の桁ごとに調べることです。GR5の最下位ビット（2進数で最も右にある桁）が1なら、GR4をGR0に加えます。プログラムの AND GR3, =#0001 は、GR5の最下位ビットを調べる処理です。結果が0なら JZE NEXT で加算を飛ばし、1なら ADDL GR0, GR4 で加算します。
その後、SLL GR4, 1 でGR4を左に1ビットずらします。論理シフト（ビットをずらし、空いた位置を0で埋める操作）を左に行うと、値は2倍になります。一方、GR5は右に1ビットずらして、次の桁を調べられるようにする必要があります。
例えば、GR4が3、GR5が5の場合を追うと、次のようになります。
このように、乗数の各桁に応じて被乗数を加えることで、 を求められます。
次に、繰返しをいつ終えるかを考えます。GR5が0になったら、調べる桁がなくなるので終了です。LD GR5, GR5 はGR5の値を変えず、条件フラグ（直前の命令の結果が0かどうかなどを示す状態）をGR5の値に合わせます。最初の繰返しではこのフラグを使います。その後は SRL GR5, 1 がフラグを更新し、JUMP LP はフラグを変えずに繰返しの先頭へ戻ります。
したがって、繰返しの先頭でGR5が0なら終了するため、eには JZE FIN が入ります。JZEは、直前の結果が0だったときに指定先へ移る命令です。
また、GR5を次の桁へ進めるには、右へ1ビットずらす SRL GR5, 1 が必要です。これにより、現在の最下位ビットを調べた後、次のビットが最下位に移ります。よって、fも SRL GR5, 1 です。
誤りやすいポイント
- GR4とGR5のシフト方向を逆にしないこと
GR4は桁の重みを2倍にするため左シフトします。GR5は次のビットを調べるため右シフトします。 - 最下位ビットが0でも加算すると思わないこと
AND GR3, =#0001 の結果が0なら、JZE NEXT によって加算を飛ばします。 - 終了条件を「GR5が正かどうか」と混同しないこと
必要なのは、残りのビットがあるかどうかです。GR5が0になったときに終了するため、JZEを使います。 - 右シフトと単なる加算を取り違えないこと
乗数のビットを順番に調べるには、GR5を右にずらす必要があります。GR5に別の値を加えても、次のビットを確認できません。
FAQ
Q: LD GR5, GR5 は値を変えないのに、なぜ書かれているのですか？
A: GR5の値をそのまま保ちつつ、条件フラグをGR5の値に合わせるためです。これにより、最初の繰返しの先頭でJZEを使って終了判定できます。
A: GR5の値をそのまま保ちつつ、条件フラグをGR5の値に合わせるためです。これにより、最初の繰返しの先頭でJZEを使って終了判定できます。
Q: GR5の最下位ビットが1のときだけGR4を加えるのはなぜですか？
A: 2進数では、各桁が1のときだけ、その桁に対応する値を足します。GR4を繰返し左シフトして2倍にすることで、次の桁に対応する値を作っています。
A: 2進数では、各桁が1のときだけ、その桁に対応する値を足します。GR4を繰返し左シフトして2倍にすることで、次の桁に対応する値を作っています。
Q: GR5が0になった後、なぜ計算を続ける必要がないのですか？
A: GR5が0なら、調べるビットが残っていません。以降、GR0に加える値がなくなるため、計算を終了できます。
A: GR5が0なら、調べるビットが残っていません。以降、GR0に加える値がなくなるため、計算を終了できます。
関連キーワード: 2進数、論理シフト、ビット演算、条件分岐、汎用レジスタ
