基本情報処理試験H22年秋期午後について

質問

基本情報処理試験の過去問について質問です。

H22年度秋期の午後試験〔問8〕の設問２の空欄ｇが
今日一日やったのですが、理解できません。

〔問8〕の空欄ｇ
N＝7は2進数で0111です。

Rの下位５ビット　01110

１回目　ビット：10　なので　減算
２回目　ビット：11　なので　何もせず
３回目　ビット：11　なので　何もせず
４回目　ビット：01　なので　加算

ここまでは、プログラム２をトレースしてわかります。

解説書によると、以下ですが、何が「つまり」なのか？
計算式がどうして導き出せるのかがわかりませんでした。

----------------------------------------

　つまり次のように計算しています。

M×7＝M×（－1＋8）＝M×（－2＾0＋2＾3）

　以上のことから、正解はアです。

--------------------------------------
過去問URL
http://情報処理試験.jp/FE22b-pm/t08.html

よろしくお願い致します。

回答No.1

jjon-com · ベストアンサー

［プログラム２］は，
(4) Rのビット番号1のビットが0 かつ Rのビット番号0のビットが1
(6) Rのビット番号1のビットが1 かつ Rのビット番号0のビットが0
と，ビット列が01または10のときだけ加算または減算している。
つまり，Rのビット列として0が連続したり1が連続したりするときには加減算しないことで，加減算の回数を少なくするアルゴリズムだということ。

----------------
ビット1が連続している例として，
Ｎ＝ +7 ＝ 0111 を挙げると，
(2)(3)において Rの下位5ビットに設定されるビット列は 01110
（ちなみにRの上位5ビットにはＭを格納して乗算結果を求めるために用いる）

減算するタイミングは 011[10] の一箇所だけであり，
右シフトはまったく行われていない（０回）なので，この減算は－(２の0乗)Ｍ すなわち －Ｍを表す。

加算するタイミングは [01]110 の一箇所だけであり，
右シフトは３回行われているので，この加算は＋(２の3乗)Ｍ すなわち ＋８Ｍを表す。

> 　つまり次のように計算しています。
> M×7＝M×（－1＋8）＝M×（－2＾0＋2＾3）

----------------
念のため，ビット1が連続している別の例として，
Ｎ＝ -2 ＝ 1110 を挙げると，
(2)(3)において Rの下位5ビットに設定されるビット列は 11100

減算するタイミングは 11[10]0 の一箇所だけであり，
右シフトは１回行われているので，この減算は－(２の1乗)Ｍ すなわち －２Ｍを表す。

加算するタイミングは無い。

よって，この例でも Ｎ＝ -2 の場合の Ｍ×Ｎ が正しく計算できている。

お礼

早速のご回答ありがとうございます。
また、別例も提示いただき感謝致します。

（７）の減算のタイミングでは、まだ右シフトはまったく行われていない（０回）でしたね。
なので、
この減算は－(２の0乗)Ｍ すなわち －Ｍを表している。

何故「－」なのか？　「2^0」？が疑問でした。
LOOP毎のビットトレースに気を取られおりましたが、
そもそも「加減算」するプログラムでしたね。