このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

マスクと論理積を取る方法

 AND演算(論理積演算)で特定のビットを取り出すことができる。

例:2進数の「10101010」と「00001111」をAND演算すると、下位4ビット分を取り出せる。

 この取り出すために用意するデータのことをマスク(データ)と呼ぶ。そして、指定ビット以外を0にすることを「マスクをかける」と呼ぶ。

マスクを固定し、データをシフトするアプローチ

 常に最下位ビットを取り出し、1があるかどうかを調べる。

 なお、ここでは右シフトする例で考えるが、もちろん左シフトでも問題ない。

CASL兇両豺

例:M(DATA)に格納されているデータ「#A5F3」(=「1010 0101 1111 0011」)に含まれている1のビット数をカウントしてM(ANS)に格納するプログラムである。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
SMP0411   START     
          LD        GR1,DATA
          LAD       GR3,0
LOOP      LD        GR0,GR1
          AND       GR0,MASK
          JZE       SKIP
          ADDA      GR3,=1
SKIP      SRL       GR1,1
          JNZ       LOOP
          ST        GR3,ANS
          RET       
DATA      DC        #A5F3
MASK      DC        #0001
ANS       DS        1
          END       

 4〜6行目で最下位ビットに1があるかどうかを調べる。もし1であれば、7行目でGR3をインクリメントする。もし1でなければ、SKIPへ飛んでインクリメントする行を飛ばす。
 8行目でデータを右シフト(論理)して、9行目でデータが0になるまで繰り返すようにループさせる。
 最終的にST命令でGR3からM(ANS)へデータをコピーする。

マスクをシフトし、データを固定するアプローチ

 第15ビットから第0ビットまでを順に取り出し、1があるかどうか調べる。

 なお、ここでは右シフトする例で考えるが、もちろん左シフトでも問題ない。

CASL兇両豺

例:M(DATA)に格納されているデータ「#A5F3」(=「1010 0101 1111 0011」)に含まれている1のビット数をカウントしてM(ANS)に格納するプログラムである。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
SMP0412   START
          LD        GR1,DATA
          LD        GR2,MASK
          LAD       GR3,0
LOOP      LD        GR0,GR2
          AND       GR0,GR1
          JZE       SKIP
          ADDA      GR3,=1
SKIP      SRL       GR2,1
          JNZ       LOOP
          ST        GR3,ANS
          RET       
DATA      DC        #A5F3
MASK      DC        #8000
ANS       DS        1
          END

 GR1にデータ、GR2にマスクをセットする。そして一旦GR2のデータをGR0にコピーして、GR0とGR1をAND演算して結果をGR0にセットする。そのとき8行目でERがゼロならばSKIPに移動。ゼロでなければ、GR3にインクリメントする。
 9行目でGR2をひとつ分論理右シフトする。その結果10行目でERがゼロでなければLOOPへ戻る。つまり、16桁あるデータを調べるので、15回(最後の一回は戻らなくてよいため)必ずLOOPへ戻るわけである。
 すべての桁のビット判定をチェックしたら、GR3にその数がセットされているはずである。11行目でST命令でGR3からM(ANS)にコピーする。

マスクを用いない方法

符号ビット利用によるアプローチ

 まず、データをGR1にセットする。LD命令なので、このときFRも設定される。そこで、一旦FRのSF(サインフラグ)をチェックする。
 その後、データを左シフトして、FRのSF(サインフラグ)をチェックする。これを何度(実質15回のチェック)も繰り返して、ビット1の総数を知ることができる。

CASL兇両豺

例:M(DATA)に格納されているデータ「#A5F3」(=「1010 0101 1111 0011」)に含まれている1のビット数をカウントしてM(ANS)に格納するプログラムである。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
SMP0421   START     
          LAD       GR3,0
          LD        GR1,DATA
LOOP      JPL       SKIP
          JZE       SKIP
          ADDA      GR3,=1
SKIP      SLL       GR1,1
          JNZ       LOOP
          ST        GR3,ANS
          RET       
DATA      DC        #A5F3
ANS       DS        1
          END       

オーバーフローフラグ利用によるアプローチ

 データを右にシフトして、FRのOF(オーバーフローフラグ)をチェックしてビット1の総数を知ることができる。

CASL兇両豺

例:M(DATA)に格納されているデータ「#A5F3」(=「1010 0101 1111 0011」)に含まれている1のビット数をカウントしてM(ANS)に格納するプログラムである。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
SMP0422   START     
          LAD       GR3,0
          LD        GR1,DATA
LOOP      SRL       GR1,1
          JOV       STEP
          JNZ       LOOP
          ST        GR3,ANS
          RET       
STEP      ADDA      GR3,=1
          JUMP      LOOP
DATA      DC        #A5F3
ANS       DS        1
          END       

 FRのOFが1ならGR3をインクリメントし、0なら何もしない。OF=0のときに分岐する命令があれば便利だが、CASL兇OFに関連する分岐はJOV命令*1しかない。そこでJOV命令でSTEPにジャンプして、そこでGR3をインクリメントさせてLOOPへ戻ってこさせるように処理させている。

参考文献

  • 『情報処理試験 CASLII 〜CASLIIの講義と実習〜 [第2版]』


*1 F=1のときに分岐