基本情報技術者 2010年 秋期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
〔プログラムの説明〕
16ビット（1語）からなるビット列のビットの並びを、図1に示すように逆転する副プログラムREVRSである。
(1) ビット列を格納している語のアドレスはGR1に設定されて、主プログラムから渡される。
(2) 結果は元の領域に格納して、主プログラムに返す。
(3) 副プログラムから戻るとき、汎用レジスタGR1～GR7の内容は元に戻す。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：JMI ON
イ：JNZ ON
ウ：JOV ON
エ：JPL ON
bに関する解答群
ア：SLL GR4,-1,GR2
イ：SLL GR4,0,GR2
ウ：SRL GR4,-1,GR2
エ：SRL GR4,0,GR2
模範解答
a：ウ、b：イ
解説
解答の導き方
1. ビットを1個ずつ取り出して、逆順に組み立てます
本文には「16ビット（1語）」の並びを逆転するとあります。図1のように、元のビット列の左端と右端が入れ替わる処理です。
プログラムでは、元のビット列をGR3に、作成中の結果をGR4に置いています。汎用レジスタ（General Register：処理中の値を一時的に置く場所）です。
「SRL GR3,1」は、GR3を右に1ビットずらす命令です。右端から押し出されたビットは、OF（Overflow Flag：シフトで端から出たビットを記録する状態）に入ります。一方、「SLL GR4,1」はGR4を左に1ビットずらします。
この2つを使い、元のビット列の右端から1ビットずつ取り出し、結果の右端に順番に加えます。
- 押し出されたビットが1なら、「OR GR4,=#0001」でGR4の右端を1にします。
- 押し出されたビットが0なら、GR4を左にずらしただけにします。右端には0が入るため、そのままでよいです。
ここで、ORは対応するビットのどちらかが1なら結果を1にするビット演算です。
2. aには、押し出されたビットが1かを調べる命令を入れます
「SRL GR3,1」の直後には、右端から押し出されたビットがOFに入っています。そのビットが1なら、GR4にも1を加える必要があります。
JOV（Jump on Overflow：OFが1のときに分岐）は、OFを調べて分岐する命令です。したがって、「JOV ON」とすれば、押し出されたビットが1の場合にONへ進みます。
ほかの候補は、調べる状態が異なります。JMI（Jump on Minus：負のときに分岐）やJPL（Jump on Plus：正のときに分岐）は符号に関する状態を調べます。JNZ（Jump on Not Zero：結果が0でないときに分岐）は、押し出されたビットではなく、シフト後のGR3が0かどうかに関係します。
よって、aには「JOV ON」が入ります。
3. FIN1では、残りの0ビット分だけGR4を左にずらします
「JZE FIN1」は、シフト後のGR3が0ならFIN1へ進む命令です。JZE（Jump on Zero：結果が0のときに分岐）は、ZF（Zero Flag：結果が0かを記録する状態）を調べます。
GR3が0になったということは、元のビット列から残っているビットはすべて0です。その場合、残りのビットを1個ずつ処理しなくても、GR4を必要な数だけ左にずらせば同じ結果になります。
このシフト回数はGR2で分かります。GR2は15から始まり、各ビットの処理後に1ずつ減ります。FIN1へ進む時点では、現在のビット位置に対するGR4のシフトはすでに済んでいます。そのため、GR2は「この後に必要なシフト回数」を表します。
「SLL GR4,0,GR2」は、GR2の値をシフト回数としてGR4を左にずらします。左にずらすのは、結果の右端に残りの0ビットを加えるためです。右にずらすと、すでに作った結果のビットが失われてしまいます。
したがって、bには「SLL GR4,0,GR2」が入ります。
誤りやすいポイント
- JZEは、押し出されたビットが0かどうかを調べる命令ではありません。シフト後のGR3全体が0かどうかを調べます。押し出されたビットが1かどうかは、JOVで調べます。
- JOVより先にJZEで処理を終えると、押し出されたビットが1の場合に、その1をGR4へ加えられないことがあります。プログラムでは、まずJOVで1を処理します。
- FIN1のシフト方向は左です。未処理の0ビットを結果の右端に加えるには、GR4を左へずらす必要があります。
- GR2は15から始まりますが、処理対象は16ビットです。各回の処理後に1ずつ減らすため、16回処理するとGR2が負になり、JMIで終了します。
FAQ
Q: なぜGR3が0になったら、すぐに処理を終えずにGR4をシフトするのですか？
A: 元のビット列の残りは0ですが、その分のビット位置は結果にも必要です。GR4を左にずらして0を補うことで、16ビットの並びを正しく作れます。
A: 元のビット列の残りは0ですが、その分のビット位置は結果にも必要です。GR4を左にずらして0を補うことで、16ビットの並びを正しく作れます。
Q: 押し出されたビットが1で、その後のGR3が0になった場合はどうなりますか？
A: 先にJOVでONへ進み、GR4の右端を1にします。その後、ループカウンタを減らして次の処理へ進みます。まだビット位置が残っていれば、その位置の0も含めて処理されます。
A: 先にJOVでONへ進み、GR4の右端を1にします。その後、ループカウンタを減らして次の処理へ進みます。まだビット位置が残っていれば、その位置の0も含めて処理されます。
Q: なぜGR2は15から始まるのですか？
A: 16ビットを処理し、各回の処理後に1ずつ減らすためです。15から始めると、16回目の処理後にGR2が負になり、JMIで終了できます。
A: 16ビットを処理し、各回の処理後に1ずつ減らすためです。15から始めると、16回目の処理後にGR2が負になり、JMIで終了できます。
関連キーワード: ビットシフト、論理シフト、オーバフローフラグ、条件分岐、ビット演算
設問2：
問題文を見る 連続したn語(n≧1)を16×nビットのビット列とみなす。副プログラムREVRSを利用して、このビット列のビットの並びを、図2に示すように逆転する副プログラムLREVRSを作成した。
主プログラムから渡されるレジスタの内容は、次のとおりとする。
GR1：ビット列が格納されている領域の先頭アドレス
GR2：n
副プログラムLREVRS中のに入れる正しい答えを、解答群の中から選べ。
解答群
ア：JMI LOOP1
イ：JNZ LOOP1
ウ：JNZ LOOP2
エ：JPL LOOP1
オ：JZE FIN3
カ：JZE LOOP2
模範解答
c：ア、d：ウ
解説
解答の導き方
このプログラムでは、16×nビット全体を逆順にするために、まず「語」の並びを逆にし、その後で各語の中のビットを逆にします。ビットは0か1で表す情報の最小単位で、語はここでは16ビットのひとかたまりです。
全体のビット列を逆順にすると、語の順番が逆になるだけでなく、各語の中のビットの順番も逆になります。そこで、プログラム2では前半の処理で語を入れ替え、後半の処理でREVRSを各語に実行します。
語を入れ替える部分
レジスタ（値やアドレスを一時的に置く場所）のGR3には、入れ替え対象の先頭の語のアドレスを設定します。GR4には、最後の語のアドレスを設定します。
主プログラムから渡されるGR1は先頭アドレス、GR2は語数nです。プログラムでは、GR4にGR2の値を移し、1を引いてからGR1を加えています。そのため、GR4は先頭から語後、つまり最後の語を指します。
nが1の場合は、GR4から1を引くと0になり、JZE LOOP2で語の入れ替えを飛ばします。語が1つだけなら、入れ替える相手がいないためです。ただし、その後のREVRSは必要なので、LOOP2へ進みます。
nが2以上の場合は、LOOP1でGR3の指す語とGR4の指す語を入れ替えます。その後、GR3を次の語へ進め、GR4を一つ前の語へ戻します。つまり、外側の語から内側へ向かって処理します。
例えば、先頭アドレスをA、語数を4とすると、入れ替えとアドレス更新は次のように進みます。
CPA GR3,GR4は、GR3とGR4を比較する命令です。比較結果が負、つまりGR3がGR4より小さいときは、まだ間に未処理の語の組があります。JMIは比較結果が負のときに分岐する命令なので、cにはJMI LOOP1が入ります。選択肢ではアです。
GR3とGR4が等しい場合は、中央の語まで処理済みです。GR3がGR4より大きい場合は、処理する語の範囲が交差しており、入れ替えは終わっています。したがって、単に「等しくない」場合に分岐するのではなく、「GR3がGR4より小さい」場合に限ってLOOP1へ戻る必要があります。
各語のビットを逆にする部分
語の入れ替えが終わると、LOOP2でREVRSを呼び出します。問題文には、REVRSがGR1のアドレスにある語のビットの並びを逆転するとあります。さらに、REVRSから戻るときにGR1～GR7の内容は元に戻るため、呼び出し後もGR1は処理中の語のアドレスを保っています。
その後、LAD GR1,1,GR1でGR1を次の語のアドレスへ進め、SUBA GR2,=1で残りの語数を1減らします。残りがある間は、次の語にもREVRSを実行するため、LOOP2へ戻る必要があります。
JNZは直前の演算結果が0でないときに分岐する命令です。語数を1減らした後、GR2が0でなければ未処理の語が残っています。そのため、dにはJNZ LOOP2が入ります。選択肢ではウです。GR2が0になれば分岐せず、そのままFIN3へ進んで処理を終えます。
誤りやすいポイント
- 語の順番を入れ替えるだけでは、16×nビット全体の逆転にはなりません。各語の中のビットもREVRSで逆転します。
- cの判定は、アドレスを更新した後に行います。次の先頭側のアドレスGR3が、次の末尾側のアドレスGR4より小さい間だけ、入れ替えを続けます。
- cにJNZを選ぶと、GR3とGR4が交差した後も分岐する可能性があります。必要なのは「異なるか」ではなく「GR3がGR4より小さいか」の判定です。
- dでは、GR2を減らした後の値を見ます。0なら処理終了、0でなければ次の語を処理します。
FAQ
Q: nが1のとき、語の入れ替えを飛ばしてよいのはなぜですか？
A: 語が1つだけなので、語同士の入れ替えはありません。ただし、その1語の中のビット順は逆にする必要があるため、REVRSは実行します。
A: 語が1つだけなので、語同士の入れ替えはありません。ただし、その1語の中のビット順は逆にする必要があるため、REVRSは実行します。
Q: 語の入れ替えが終わった後、なぜすべての語にREVRSを実行するのですか？
A: 全体のビット列を逆順にするには、語の順番だけでなく、各語の中のビット順も逆にする必要があるからです。
A: 全体のビット列を逆順にするには、語の順番だけでなく、各語の中のビット順も逆にする必要があるからです。
Q: REVRSを呼び出した後に、GR1を次の語へ進められるのはなぜですか？
A: 問題文の説明で、REVRSから戻るときにGR1～GR7の内容は元に戻るとされています。そのため、呼び出し前のGR1を使って次の語へ進められます。
A: 問題文の説明で、REVRSから戻るときにGR1～GR7の内容は元に戻るとされています。そのため、呼び出し前のGR1を使って次の語へ進められます。
関連キーワード: ビット列、レジスタ、アドレス、比較命令、条件分岐、ループ処理
設問3：
問題文を見る 副プログラムREVRSを使用して、16ビット（1語）からなるビット列中の部分ビット列αのビットの並びを、図3に示すように逆転する副プログラムPREVRSを作成した。p, qは、それぞれ部分ビット列の直前までのビット数及び部分ビット列のビット数を表す。
ここで、p≧0, q>1, p+q≦16とする。
主プログラムから渡されるレジスタの内容は、次のとおりとする。
GR1：ビット列が格納されている語のアドレス
GR2：p
GR3：q
副プログラムPREVRS中のに入れる正しい答えを、解答群の中から選べ。
解答群
ア：OR GR6,GR5
イ：OR GR6,0,GR1
ウ：SLL GR5,0,GR6
エ：SLL GR5,0,GR3
模範解答
e：ウ、f：ア
解説
解答の導き方
このプログラムは、16ビットのビット列のうち、先頭からビット進んだ位置にあるビットだけを逆転し、それ以外のビットは元のままにします。
処理前と処理後を、左から並べて考えると次のようになります。
- 処理前：[先頭のビット][部分ビット列のビット][残りのビット]
- 処理後：[先頭のビット][逆転したのビット][残りのビット]
ここで、レジスタは計算途中の値を一時的に置いておく場所です。プログラムではGR4、GR5、GR6を使って、元のビット列や逆転後の部分ビット列を扱っています。
1. 元のビット列を保存してから、語全体を逆転します。
最初に「ビット列を保存」とあるとおり、LD GR4,0,GR1 で元のビット列をGR4に保存します。その後、CALL REVRS で16ビット全体の並びを逆転し、逆転後の値をGR5に読み込みます。
語全体を逆転すると、部分ビット列の中のビット順も逆になります。ただし、は元の位置から移動しています。そこで、次のシフトでを取り出し、元の位置に戻します。
2. 逆転したを、いったん語の右端に移します。
LD GR6,=16 と SUBA GR6,GR3 によって、GR6にはが入ります。
その次の SRL GR5,0,GR2 は、GR2に入っているだけGR5を右へ論理シフトする命令です。論理シフトでは、空いた位置に0が入ります。
語全体を逆転した後、逆転したの右側には元の先頭のビットがあります。そのため、ビット右へシフトすると、逆転したが語の右端に移ります。
3. 右端のを、元の位置に戻します。
右端にあるビットを、語の左端に移すにはビット左へシフトします。GR6にはが入っているので、eには SLL GR5,0,GR6 が入ります。
その後、次の SRL GR5,0,GR2 でビット右へシフトします。これで、逆転したが元の位置に置かれます。
4. 元のだけを消すマスクを作ります。
GR6を =#8000 で初期化すると、16ビットの並びは先頭が1で、残りは0になります。
次の SRA GR6,-1,GR3 は、GR3の値をとすると、ビットの算術右シフトをします。算術右シフトでは、左側の空きに先頭のビットが補われます。先頭ビットは1なので、シフト後は先頭から個のビットが1になります。
次の SRL GR6,0,GR2 で、その1の並びをビット右へ移動します。これにより、元のと同じ位置に1が並びます。
続く XOR GR6,=#FFFF は、16ビットすべてが1の値との排他的論理和です。ここでは、の位置が0、それ以外の位置が1のマスクになります。これを AND GR6,GR4 で元のビット列に適用すると、元のだけが0になり、それ以外のビットは元のまま残ります。
5. 逆転したを、空いた位置に入れます。
ここまでで、GR6には「元のを0にしたビット列」が入っています。一方、GR5には「元の位置に戻した、逆転後の」が入っており、それ以外の位置は0です。
両者をOR（論理和：どちらか一方でも1なら結果が1になる演算）で合成すると、空いていたの位置に逆転後のビット列が入ります。したがって、fには OR GR6,GR5 が入ります。
誤りやすいポイント
- eのシフト数はではなくです。語の右端にあるビットを左端へ移す距離がだからです。
- SRA GR6,-1,GR3 のシフト数はです。-1にGR3の値を加えるためです。
- 元のビット列はGR4に保存されています。逆転した語全体をそのまま使うのではなく、元のビット列からを消し、逆転後のをその位置に入れます。
- fで必要なのは、位置を合わせただけが入っているGR5とのORです。GR1が指す領域の値をそのまま使うと、変更したい部分以外のビットも影響します。
FAQ
Q: なぜ語全体を逆転してから、部分ビット列を取り出すのですか？
A: 語全体を逆転すると、部分ビット列の中のビット順も逆になります。その後、シフトによってを取り出して元の位置に戻すためです。
A: 語全体を逆転すると、部分ビット列の中のビット順も逆になります。その後、シフトによってを取り出して元の位置に戻すためです。
Q: 元のビット列をGR4に保存するのはなぜですか？
A: REVRSは語全体を逆転するため、変更箇所以外のビットを元の値に戻す必要があります。GR4に保存した元のビット列から、以外の部分を取り出します。
A: REVRSは語全体を逆転するため、変更箇所以外のビットを元の値に戻す必要があります。GR4に保存した元のビット列から、以外の部分を取り出します。
Q: マスクを作るのはなぜですか？
A: 元のビット列のうち、逆転した値に置き換える部分だけを0にするためです。そこへ逆転後のをORで重ねることで、ほかのビットを変えずに部分ビット列だけを置き換えられます。
A: 元のビット列のうち、逆転した値に置き換える部分だけを0にするためです。そこへ逆転後のをORで重ねることで、ほかのビットを変えずに部分ビット列だけを置き換えられます。
関連キーワード: ビットシフト、論理シフト、算術シフト、ビットマスク、論理演算
