【CASLⅡ】シフト演算と加算の繰り返しで行う2進数の乗算

CASLⅡで2進数の掛け算をシフト演算と加算で行う プログラミング

こんにちは、コンスキです。

2進数の乗算をやる方法は複数あります。

その中でも今回は、シフト演算と加算を使うやり方をご紹介します。

フローチャート

計算の手順をフローチャートにすると次のようになります。

応用情報技術者平成22年春期午前問5で使われた画像を編集したもの

プログラム

次のようなプログラムで29✖️43の計算をすることができます。

MAIN      START   
               LD          GR1,  X      
               LD          GR2,  Y
               LD          GR4,  i     
               CALL      MUL       
               ST          GR0,  Z    
               RET     
                  
MUL        LAD       GR0,  0             ;積を入れるためにGR0を初期化
LOOP      LD         GR3,  GR2         ;計算用にかける数をGR3に転送
               AND       GR3,  =#0001 ;GR3の0ビット目が1か0か判定
               CPA       GR3,   =#0001  ;GR3の0ビット目が1か0か判定 
               JNZ        SHIFT                ;GR3数の0ビット目が0であればSHIFTに移動
               ADDA    GR0,  GR1        
SHIFT 
               SLL        GR1,  1     
               SRL        GR2,  1     
               LAD       GR4,  1, GR4    ;iに1を加算 
               CPA       GR4,   =16        ;iと16を比較
               JZE         LOOP               ;GR4が16と等しければLOOPへ移動
               JMI         LOOP                ;GR4が16より小さければLOOPへ移動
               RET     
                  
X             DC         29                     ;かけられる数
Y             DC         43                     ;かける数
Z             DC         0                        ;積
i             DC         1                        ;ビット数を数えるためのもの
               END

上のプログラムには最終的な積を出力する部分がありません。

CASLⅡのシミュレーターだと出力するためのOUT命令が使えなかったためです。

説明

簡単にですが初めの部分だけ説明します。

まずは値を用意している部分を見てみましょう。プログラムの一番下から5行目までです。

X             DC         29                     ;かけられる数
Y             DC         43                     ;かける数
Z             DC         0                        ;積
i             DC         1                        ;ビット数を数えるためのもの
               END

この部分では計算で必要になる値をメモリに用意しています。

かける数X、かけられる数Y、計算途中の積が入るZ、そしてループを抜ける時の条件となるiです。

フローチャートにもこれらの変数がありましたね。

次は最初から4行目までのプログラムを見てみます。

MAIN      START   
               LD          GR1,  X      
               LD          GR2,  Y
               LD          GR4,  i     

この部分は、先ほどメモリに用意した値を汎用レジスタというものに読み込んでくる部分です。

Xに用意した値29はGR1に読み込まれます。

同じように、Yに用意した値43はGR2に読み込まれます。

iも同じ感じで読み込まれます。

続いて下の行ではサブルーチンを読んでいます。

               CALL      MUL

サブルーチンはJAVAやC言語でいうメソッドや関数になると思います。

この場合だと、MULというラベルがついた部分まで移動します。

その後一通り命令を実行した後、RETという命令が使われたらもとの位置に戻ります。

ということで、MULというラベルがついた部分を見ていきます。

MUL        LAD       GR0,  0             ;積を入れるためにGR0を初期化

この行がMULというサブルーチンの最初の行になっています。

GR0も汎用レジスタです。

汎用レジスタには初め値が入っていないので、0という値を入れて初期化しています。

そして、次の行を見てください。

LOOP      LD         GR3,  GR2         ;計算用にかける数をGR3に転送

この行ではGR2からGR3に値を読み込んでいます。

Yにはかける数が入っていました。

それを先ほどGR2に読み込んでいたので、GR3にもかける数が読み込まれたことになります。

GR3に読み込んでいるのはなぜかというと、かける数を計算に使うためです。

GR2にはかける数をそのまま残しておきたいため、GR3にわざわざ読み込んできています。

次の部分は、かける数の0ビット目(最下位ビット)が1どうかによって分岐する部分です。

               AND       GR3,  =#0001 ;GR3の0ビット目が1か0か判定
               CPA       GR3,   =#0001  ;GR3の0ビット目が1か0か判定 
               JNZ        SHIFT                ;GR3数の0ビット目が0であればSHIFTに移動

フローチャートだとこの部分になります。

AND命令で論理演算をしている理由を疑問に思うかもしれません。

実は、2つの2進数の論理積を求めることで特定のビットが1かどうかを判断することができます。

そのためAND命令を使っています。

まず、調べたい2進数を用意します。

ここでは「1001」としておきます。

次に、特定のビットだけを1にした2進数を用意します。

ここでは「1001」の最下位ビットが1かどうか調べたいので「0001」を用意します。

この2つの論理積を求めます。

論理積は「0001」になりました。

これが先ほど用意した特定のビットだけを1にした値と一致していれば、特定のビットが1であることを意味します。

この作業をやっているのがこの部分になります。

               AND       GR3,  =#0001 ;GR3の0ビット目が1か0か判定
               CPA       GR3,   =#0001  ;GR3の0ビット目が1か0か判定 
               JNZ        SHIFT                ;GR3数の0ビット目が0であればSHIFTに移動

コメント

タイトルとURLをコピーしました