2つの符号付き数値の乗算のためのブースの乗算アルゴリズムを実装するC++プログラム

ブースのアルゴリズムは、2つの符号付き2進数を2の補数表記で乗算する乗算アルゴリズムです。ブースでは、追加するよりもシフトが速い卓上計算機を使用し、速度を上げるためのアルゴリズムを作成しました。

アルゴリズム

Begin
   Put multiplicand in BR and multiplier in QR
      and then the algorithm works as per the following conditions:
   1. If Qn and Qn+1 are same i.e. 00 or 11 perform arithmetic shift by 1 bit.
   2. If Qn Qn+1 = 10 do A= A + BR and perform arithmetic shift by 1 bit.
   3. If Qn Qn+1 = 01 do A= A – BR and perform arithmetic shift by 1 bit.
End

サンプルコード

#include<iostream>
using namespace std;
void add(int a[], int x[], int q);
void complement(int a[], int n) {
   int i;
   int x[8] = { NULL };
   x[0] = 1;
   for (i = 0; i < n; i++) {
      a[i] = (a[i] + 1) % 2;
   }
   add(a, x, n);
}
void add(int ac[], int x[], int q) {
   int i, c = 0;
   for (i = 0; i < q; i++) {
      ac[i] = ac[i] + x[i] + c;
      if (ac[i] > 1) {
         ac[i] = ac[i] % 2;
         c = 1;
      }else
         c = 0;
      }
   }
   void ashr(int ac[], int qr[], int &qn, int q) {
      int temp, i;
      temp = ac[0];
      qn = qr[0];
      cout << "\t\tashr\t\t";
      for (i = 0; i < q - 1; i++) {
         ac[i] = ac[i + 1];
         qr[i] = qr[i + 1];
      }
      qr[q - 1] = temp;
   }
   void display(int ac[], int qr[], int qrn) {
      int i;
      for (i = qrn - 1; i >= 0; i--)
         cout << ac[i];
      cout << " ";
      for (i = qrn - 1; i >= 0; i--)
         cout << qr[i];
   }
   int main(int argc, char **argv) {
      int mt[10], br[10], qr[10], sc, ac[10] = { 0 };
      int brn, qrn, i, qn, temp;
      cout << "\n--Enter the multiplicand and multipier in signed 2's
      complement form if negative--";
      cout << "\n Number of multiplicand bit=";
      cin >> brn;
      cout << "\nmultiplicand=";
      for (i = brn - 1; i >= 0; i--)
         cin >> br[i]; //multiplicand
      for (i = brn - 1; i >= 0; i--)
         mt[i] = br[i];
      complement(mt, brn);
      cout << "\nNo. of multiplier bit=";
      cin >> qrn;
      sc = qrn;
      cout << "Multiplier=";
      for (i = qrn - 1; i >= 0; i--)
         cin >> qr[i];
         qn = 0;
         temp = 0;
         cout << "qn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n";
         cout << "\t\t\tinitial\t\t";
         display(ac, qr, qrn);
         cout << "\t\t" << sc << "\n";
         while (sc != 0) {
            cout << qr[0] << "\t" << qn;
            if ((qn + qr[0]) == 1) {
               if (temp == 0) {
                  add(ac, mt, qrn);
                  cout << "\t\tsubtracting BR\t";
                  for (i = qrn - 1; i >= 0; i--)
                     cout << ac[i];
                  temp = 1;
               }
            else if (temp == 1) {
               add(ac, br, qrn);
               cout << "\t\tadding BR\t";
               for (i = qrn - 1; i >= 0; i--)
                  cout << ac[i];
                  temp = 0;
            }
            cout << "\n\t";
            ashr(ac, qr, qn, qrn);
         }
         else if (qn - qr[0] == 0)
            ashr(ac, qr, qn, qrn);
            display(ac, qr, qrn);
            cout << "\t";
            sc--;
            cout << "\t" << sc << "\n";
   }
   cout << "Result=";
   display(ac, qr, qrn);
}

出力

--Enter the multiplicand and multipier in signed 2's complement form if
negative--
Number of multiplicand bit=5
multiplicand=0 1 1 1 1
No. of multiplier bit=5
Multiplier=1 0 1 1 1
qn q[n+1] BR AC QR sc
initial 00000 10111 5
1 0 subtracting BR 10001
ashr 11000 11011 4
1 1 ashr 11100 01101 3
1 1 ashr 11110 00110 2
0 1 adding BR 01101
ashr 00110 10011 1
1 0 subtracting BR 10111
ashr 11011 11001 0
Result=11011 11001