基本情報技術者 2015年 春期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラム1、2の説明〕
非負整数nについて、階乗の値F(n)を求める副プログラムFACTである。
F(n) = 1 (n = 0, 1)
F(n) = n × (n − 1) × … × 1 (n ≧ 2)
例えば、F(3) = 3 × 2 × 1 = 6である。
(1) FACTは、nがGR1に設定されて呼ばれ、計算結果をGR0に設定して呼出し元に戻る。nは、F(n)の値が16ビット符号なし2進整数の範囲に収まるように与えられる。FACTは副プログラムMULTを利用する。
(2) MULTは、16ビット符号なし2進整数同士の乗算を行う副プログラムであり、被乗数と乗数がそれぞれGR0、GR2に設定されて呼ばれ、乗算結果をGR0に設定して呼出し元に戻る。乗算結果の桁あふれは発生しないものとする。
(3) 副プログラムから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す。
設問1：
問題文を見る プログラム1、2中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：JMI NEXT
イ：JNZ NEXT
ウ：JOV NEXT
エ：JPL NEXT
オ：JZE NEXT
bに関する解答群
ア：ADDL GR1,=1
イ：LAD GR1,1,GR1
ウ：LD GR1,GR1
エ：SRL GR1,1
オ：SUBL GR1,=1
cに関する解答群
ア：SLL GR0,0,GR3
イ：SLL GR1,0,GR3
ウ：SLL GR4,0,GR3
エ：SRL GR0,0,GR3
オ：SRL GR1,0,GR3
カ：SRL GR4,0,GR3
模範解答
a：エ、b：オ、c：ウ
解説
解答の導き方
まず、GR（General Register：汎用レジスタ。計算途中の値を置いておく場所）に、階乗の計算に必要な値をどう置いているかを追います。
FACTは、GR1に与えられた整数を使って階乗を計算します。最初にGR0へ1を設定し、GR1から1を引いています。GR0は計算結果を入れる場所です。
aは、階乗を計算するループに進む条件です。
GR1から1を引いた後、が2以上ならGR1は正の値になります。一方、ならGR1は0になり、なら引き算の結果は16ビットで表せる範囲を超えた値になります。したがって、正の値の場合だけNEXTへ進むJPLが入ります。
やの階乗はどちらも1です。すでにGR0には1が入っているので、NEXTへ進まずFINに進めば、そのまま正しい値を返せます。
NEXTへ進む場合、GR1にはが入っています。GR2を1にした後、LPでGR2を1ずつ増やし、GR0の値とGR2の値をMULTで掛けます。
例えばの場合は、次のように計算します。
MULTから戻るたびに、GR1から1を引きます。GR1が0でなければJNZでLPに戻り、0になればループを終えます。そのため、bにはGR1を1減らす処理が必要です。選択肢ではSUBL GR1,=1が該当します。
cは、MULTが乗算結果を作る方法から判断できます。
MULTは、GR0にある値とGR2にある値を掛けます。最初にGR1へ被乗数をコピーし、GR0を0にして、乗算結果を足し合わせる準備をします。GR3には15を設定し、乗数の各ビットを調べる位置として使います。ビットは、2進数の各桁を表す0または1です。
MULTは、GR2を左へ1ビットずつずらしながら、上位のビットから順に調べます。JZEは、GR2が0になったら処理を終えるための分岐です。JPLは、調べているビットが0の場合に加算を飛ばすための分岐です。JZEで0の場合を先に除いているため、JPLに進まない場合は、調べているビットが1だと分かります。
ビットが1なら、その桁の重みに合わせて被乗数を左へずらし、乗算結果に加えます。GR4には被乗数のコピーが入っているので、このGR4をGR3の値だけ左へずらします。左へのずらしは、1桁ごとに値を2倍する処理です。したがって、必要な桁数だけ左へずらすことで、そのビットに対応する値を作れます。
例えば乗数が5なら、2進数の5は、値が4になる桁と値が1になる桁に1があります。そのため、被乗数を4倍した値と、被乗数そのものを足せば、被乗数の5倍になります。この処理に当たるのはSLL GR4,0,GR3です。よって、cにはこの命令が入ります。
誤りやすいポイント
- aをJNZにすると、のときもGR1が0ではない値になるため、NEXTへ進んでしまいます。必要なのは「0でない」ことではなく、「正の値である」ことです。
- bでは、GR1を増やすのではなく、ループの残り回数を1ずつ減らします。減らした結果が0になったら、JNZでループを終えます。
- cでGR1をずらすと、次の乗算で使う被乗数そのものが変わってしまいます。GR1のコピーであるGR4をずらします。
- 乗算結果を足し合わせるGR0をずらしてはいけません。GR0は、それまでに計算した合計を保持する場所です。
- GR2の上位ビットが1の場合にJPLへ進まないのは、符号なしの値を負数として扱っているからではありません。この処理では、GR2の最上位ビットを「次に足すべきか」を判断する目印として使っています。
FAQ
Q: GR0を最初に1にするのはなぜですか？
A: 階乗の計算では、まず1から掛けていくためです。また、との階乗は1なので、ループに入らない場合の答えにもなります。
A: 階乗の計算では、まず1から掛けていくためです。また、との階乗は1なので、ループに入らない場合の答えにもなります。
Q: MULTでGR2を左へずらすのはなぜですか？
A: 毎回、GR2の上位ビットを調べてから左へずらすことで、次のビットを調べられるようにするためです。調べたビットが1なら、その桁の重みに合う値を結果に足します。
A: 毎回、GR2の上位ビットを調べてから左へずらすことで、次のビットを調べられるようにするためです。調べたビットが1なら、その桁の重みに合う値を結果に足します。
Q: MULTの内部でGR1やGR2が使われても、FACTのループを続けられるのはなぜですか？
A: 問題文では、副プログラムから戻るときにGR1〜GR7の内容を元に戻すと説明されています。そのため、FACTが使っているGR1やGR2の値は、MULTを呼び出す前の状態に戻ります。
A: 問題文では、副プログラムから戻るときにGR1〜GR7の内容を元に戻すと説明されています。そのため、FACTが使っているGR1やGR2の値は、MULTを呼び出す前の状態に戻ります。
関連キーワード: 階乗、条件分岐、2進数、論理シフト、サブルーチン
設問2：
問題文を見る プログラム1のFACTを使用してF(4)を求めるとき、行番号12のRPOP命令実行直前のGR2に設定されている値として正しい答えを、解答群の中から選べ。
解答群
ア：1
イ：2
ウ：3
エ：4
オ：5
模範解答
エ
解説
解答の導き方
求めるのは、FACTが処理を終え、行番号12のRPOPを実行する直前のGR2の値です。
まず、FACTをF(4)で呼び出すので、最初のGR1は4です。GR0には1が設定され、行番号4でGR1から1を引くため、ループに入る時点ではGR1が3になります。
ループでは、行番号8でGR2に1を加えてからMULTを呼び出します。MULTはGR0とGR2の値を掛けます。また、説明には「副プログラムから戻るとき、汎用レジスタGR1〜GR7の内容は元に戻す」とあります。汎用レジスタは、計算途中の値を一時的に置く場所です。このため、MULTの中でGR2が変化しても、戻ったときには呼び出された時点の値に戻ります。
各ループでの値の変化は次のとおりです。
GR2は最初に1となり、呼び出しのたびに1ずつ増えるため、MULTには順に2、3、4が渡されます。GR1が0になるとループを終え、行番号12に進みます。
したがって、行番号12のRPOPを実行する直前のGR2は4です。RPOPを実行すると、FACTが呼び出されたときのGR2に戻りますが、設問で尋ねているのはその実行直前の値です。
誤りやすいポイント
- MULTの中でGR2がシフトされることだけを見て、MULTから戻った後のGR2も変わっていると考えないようにします。副プログラムから戻るときにGR1〜GR7が元の値に戻るため、FACT側ではMULTを呼び出したときのGR2が保たれます。
- FACTの行番号12にあるRPOPの実行後と、実行直前を混同しないようにします。実行直前のGR2は計算に使った4ですが、RPOPの実行後はFACTを呼び出したときの値に戻ります。
- GR2は1から始まりますが、行番号8で1を加えてからMULTを呼び出します。そのため、最初の乗数は1ではなく2です。
FAQ
Q: GR2が1から始まるのに、最初に掛ける値が2なのはなぜですか？
A: 行番号7でGR2に1を設定した後、行番号8で1を加えてからMULTを呼び出すためです。
A: 行番号7でGR2に1を設定した後、行番号8で1を加えてからMULTを呼び出すためです。
Q: RPOPを実行した後のGR2も4ですか？
A: いいえ。設問が尋ねているのはRPOPの実行直前です。RPOPを実行すると、FACTを呼び出したときに保存されたGR2の値に戻ります。
A: いいえ。設問が尋ねているのはRPOPの実行直前です。RPOPを実行すると、FACTを呼び出したときに保存されたGR2の値に戻ります。
関連キーワード: アセンブリ言語、汎用レジスタ、副プログラム、レジスタ退避、階乗
設問3：
問題文を見る F(n)は次のように再帰的に表現することができる。
F(n) = 1 (n = 0, 1)
F(n) = n × F(n − 1) (n ≧ 2)
上記に基づいて、プログラム3のFACT2を作成した。ここで、FACT2はFACTと同様に呼ばれる。また、FACT2に制御が移り、行番号2のRPUSH命令を実行した直後のSPの値をBとする。
次の記述中のに入れる正しい答えを、解答群の中から選べ。
FACT2を使用してF(3)を求めるとき、行番号11の命令を初めて実行した直後のSPの値はdである。また、当該SPで示される番地に格納されている値はeである。
dに関する解答群
ア：B + 1
イ：B + 2
ウ：B
エ：B − 1
オ：B − 2
eに関する解答群
ア：1
イ：2
ウ：3
エ：行番号4の命令が置かれたアドレス
オ：行番号14の命令が置かれたアドレス
模範解答
d：オ、e：ウ
解説
解答の導き方
問われているのは、FACT2で を求めるとき、行番号11を初めて実行した直後のSPと、そのSPが示す番地に入っている値です。
SP（Stack Pointer：スタックの現在位置を示すレジスタ）は、スタックという一時的な記憶場所の先頭を示します。スタックに値を積む命令を実行すると、SPが1語分減り、新しいSPの番地に値が格納されます。
-
行番号2の実行直後を基準にする問題文では、行番号2のRPUSHを実行した直後のSPを としています。したがって、この時点から後にスタックへ値が積まれるたびに、SPがどう変わるかを数えます。RPUSHによる変化はすでに に含まれているため、ここから数え直す必要はありません。
-
行番号3のCALLで戻り先を積む行番号3のCALL RSUBは、RSUBの処理が終わった後に戻る場所をスタックに積みます。戻り先は、CALLの次の命令である行番号4です。CALLで1語分積まれるため、SPは から1減り、 になります。この時点で、番地 には行番号4の命令が置かれたアドレスが格納されています。
-
行番号8でNEXTへ分岐するを求めるため、最初のRSUBの実行時点ではGR1は3です。行番号6でGR1の値がGR4にコピーされ、行番号7でGR4から1を引くので、GR4は2になります。行番号8のJPLは、値が正のときNEXTへ分岐します。GR4は2で正なので、行番号11へ進みます。この時点ではGR1の値はまだ3のままです。GR1を1減らすのは、次の行番号12です。
-
行番号11のPUSHでGR1の値を積む行番号11のPUSH 0,GR1は、GR1の値をスタックに積みます。GR1は3なので、番地 にあった戻り先アドレスの上に、値3が積まれます。1語分積まれた結果、SPはさらに1減って になります。新しいSPが示す番地には、積まれた値である3が格納されています。
誤りやすいポイント
- 行番号2のRPUSHによるSPの変化を、 からさらに差し引かないようにします。 は、RPUSHの実行後の値です。
- 行番号3のCALLも戻り先アドレスをスタックに積むため、PUSHだけでなくCALLによるSPの変化も数えます。
- 行番号11の時点では、まだ行番号12を実行していません。そのため、GR1は2ではなく3です。
- SPが示す番地にある値は、スタック上の一番上に最後に積まれた値です。行番号11ではGR1の値3が最後に積まれています。
FAQ
Q: 行番号3のCALLで積まれるのは、なぜ行番号4のアドレスですか？
A: CALLは、呼出し先の処理が終わった後に戻る場所を保存します。行番号3のCALL RSUBの次に実行する命令が行番号4なので、そのアドレスが保存されます。
A: CALLは、呼出し先の処理が終わった後に戻る場所を保存します。行番号3のCALL RSUBの次に実行する命令が行番号4なので、そのアドレスが保存されます。
Q: 行番号11のPUSHの直後に、GR1が2になっていませんか？
A: いいえ。GR1を1減らすのは行番号12です。行番号11のPUSHは、その時点のGR1の値である3をスタックに積むだけです。
A: いいえ。GR1を1減らすのは行番号12です。行番号11のPUSHは、その時点のGR1の値である3をスタックに積むだけです。
Q: 再帰呼出しとは何ですか？
A: 副プログラムが、自分自身の処理をもう一度呼び出すことです。この問題では、RSUBが行番号13でRSUBを再び呼び出し、 を求めます。
A: 副プログラムが、自分自身の処理をもう一度呼び出すことです。この問題では、RSUBが行番号13でRSUBを再び呼び出し、 を求めます。
関連キーワード: 再帰呼出し、スタック、スタックポインタ、CALL命令、PUSH命令
