基本情報技術者 2009年 秋期 午後 問12

a：ウ、b：エ、c：イ、d：ウ

この問題では、行番号8の実行直後にGR2とGR4がいくつになるかを求めます。その後、行番号17の実行直後にGR0とGR5がどのようなビット列になっているかを確認します。

GRは、計算途中の値を一時的に保存する汎用レジスタです。ここでは各レジスタが16ビットの値を扱います。

主プログラムから渡される値は、$p=55$、$q=12$です。

行番号3で、GR2に入っている$p$がGR4にコピーされます。続く行番号4のSRLは、ビット列を右にずらす命令です。4ビット右にずらすと、GR4は$55÷16=3$になります。

行番号6では、GR2と=#000FとのビットごとのANDを取ります。ビットごとのANDは、同じ位置のビットが両方とも1のときだけ、結果を1にする処理です。=#000Fは下位4ビットだけが1なので、この処理でGR2の下位4ビットが残ります。55を16で割った余りは7なので、GR2は7になります。

行番号7でGR4に16を設定し、行番号8でGR2を引きます。したがって、GR4は$16-7=9$です。

よって、行番号8の直後はGR2が7、GR4が9です。解答群では、GR2の7はウ、GR4の9はエです。

問題文には「ビット列BはGR0に左詰めで設定され、GR0の残りの部分は0で埋められて」とあります。今回のGR0は1011000111010000です。

行番号9で、GR0の内容がGR5にコピーされます。この時点では、GR5も1011000111010000です。

行番号14では、GR0を行番号6で求めたGR2の値、つまり7ビット分、右にずらします。SRLは、右にずらした分だけ左側に0を入れる論理右シフトです。

1011000111010000を7ビット右にずらすと、GR0は0000000101100011になります。その後、GR0を変更する処理はないため、行番号17の実行直後もこの値のままです。

次に、行番号8で求めたGR4の値は9です。行番号16では、GR5を9ビット左にずらします。SLLは、左にずらした分だけ右側に0を入れる命令です。16ビットから左にはみ出したビットは捨てられます。

1011000111010000を9ビット左にずらすと、GR5は1010000000000000になります。行番号17でシフトされるのはGR7なので、GR5は変わりません。

したがって、行番号17の実行直後はGR0が0000000101100011、GR5が1010000000000000です。解答群では、GR0の値はイ、GR5の値はウです。

Q: なぜ行番号6の実行後、GR2は7になるのですか？
A: $p=55$を16で割ると、商は3、余りは7です。行番号4では右に4ビットずらして商に当たる部分を得て、行番号6では下位4ビットを残して余りに当たる部分を得ています。

Q: 行番号17ではGR7をシフトしているのに、GR5の値も変わりますか？
A: 変わりません。行番号17が変更するのはGR7です。GR5は行番号16でシフトされた後、そのままです。

Q: 左シフトで左にはみ出したビットはどうなりますか？
A: レジスタに保存できるのは16ビットなので、左にはみ出したビットは捨てられます。右側には、シフトした数だけ0が入ります。

関連キーワード: 論理シフト、算術シフト、ビット演算、汎用レジスタ、2進数

e：イ、f：キ（順不同）

この設問では、プログラム中の e と f に入る命令を考えます。該当する行には「ビット列Bを入れる部分を0にする」とあります。まず置換え先のビットを0にし、そのあとでビット列Bを重ねる処理だと分かります。

ビット列Aは16ビットずつの語に分かれています。行4と行5では、置換え位置を含む第i語に、ビット列Aの先頭アドレスが入ったGR1を移動します。GRは汎用レジスタ（General Register：値を一時的に保存する場所）です。

行6では、$p$の下位4ビットを取り出します。これは、置換え位置が第i語の先頭から何ビット進んだ位置にあるかを示します。その位置を$r$とすると、$r$は0〜15です。

次に、置換え対象のビットを示すマスクを作ります。マスクとは、処理したい位置を1、それ以外を0にしたビット列です。行10でGR6に設定する「=#8000」は、最上位のビットだけが1の値です。行11でGR3を$q-1$にしてから、行12のSRAでGR6を右にシフトします。SRAは算術右シフトで、符号を表す最上位ビットを保ちながら右にずらす命令です。最上位ビットが1の値を右にずらすため、上位の$q$ビットが1のマスクになります。

行14と行15では、ビット列Bとマスクを$r$ビット右にずらし、第i語の置換え位置に合わせます。一方、行16と行17では、ずらす前にGR5とGR7にコピーしておいたビット列Bとマスクを、$16-r$ビット左にずらします。これにより、置換え対象が第i語からはみ出した部分も、第(i+1)語で処理できます。

ここで、行19と行20の処理を、置換え対象の1ビットについて考えます。元のビットを$x$、その位置のマスクを$M$とします。

行19のANDは論理積です。2つのビットが両方とも1のときだけ、結果が1になります。行19で「AND GR6,GR2」を実行すると、マスクと元の語の両方が1であるビットだけがGR6に残ります。

続いて行20のXORは排他的論理和です。2つのビットが異なるとき、結果が1になります。行20で「XOR GR2,GR6」を実行すると、元の語のうち置換え対象の範囲にある1だけが0になります。

つまり、マスクが1の範囲は元の値に関係なく0になり、マスクが0の範囲は元の値がそのまま残ります。これで、ビット列Bを入れる場所だけを空けられます。

行21ではORを使って、GR0にあるビット列BをGR2に加えます。ORは、どちらか一方でも1なら結果が1になる演算です。置換え先は先に0にしてあるため、ビット列Bの1は1として入り、0は0のままです。第(i+1)語についても、行24と行25で同じように置換え先を0にしてから、行26でビット列Bを加えます。

以上から、置換え先のビットを取り出す行19と行24にはANDが入り、そのビットを元の語から0にする行20と行25にはXORが入ります。

Q: 先に置換え先を0にするのはなぜですか？
A: 元の値が残ったままビット列BをORすると、元の1が残り、ビット列Bの0を正しく反映できないためです。置換え先を先に0にすれば、ビット列Bの値をそのまま入れられます。

Q: 行19と行20の順番を逆にしてもよいですか？
A: できません。ANDで元の語のうち置換え対象範囲にある1を取り出してから、XORでその1を消す必要があります。

Q: 置換え対象が第i語の中だけにある場合も、第(i+1)語の値は変わりますか？
A: 変わりません。置換え対象外の位置ではマスクが0なので、行24と行25の処理で元の値がそのまま残ります。

関連キーワード: ビット演算、論理積、排他的論理和、ビットマスク、ビットシフト