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

ブース(Booth)の乗算アルゴリズムは、2の補数表現で表された2つの符号付き2進数を乗算するためのアルゴリズムです。考案者のブース氏は、当時のデスクトップ電卓が加算よりもシフト演算の方が高速に処理できることに着目し、計算速度を向上させるためにこの手法を編み出しました。本記事では、このアルゴリズムの考え方と、C++による実装例をわかりやすく解説します。

アルゴリズムの流れ

被乗数をBRレジスタに、乗数をQRレジスタに格納し、乗数の最下位ビットQnとその隣のビットQn+1の組み合わせに応じて、以下の操作を繰り返します。

Begin
    被乗数をBRへ、乗数をQRへ格納する
    以下の条件に従って処理を行う:
    1. Qn と Qn+1 が同じ値(00 または 11)の場合 → 1ビットの算術右シフトのみ実行
    2. Qn Qn+1 = 10 の場合 → A = A + BR を実行し、1ビットの算術右シフト
    3. Qn Qn+1 = 01 の場合 → A = A − BR を実行し、1ビットの算術右シフト
End

ポイントは、減算「A − BR」を直接行うのではなく、被乗数の2の補数(mt)をあらかじめ求めておき、加算に置き換えて処理する点です。これにより、ハードウェア上でも少ない演算回路で乗算が実現できます。

C++サンプルコード

以下のプログラムでは、アキュムレータ(AC)、乗数(QR)、被乗数(BR)を配列で模擬し、補数計算・加算・算術右シフトを関数として分離しています。各ステップでのレジスタの状態も順次表示されるため、アルゴリズムの動きを追いやすくなっています。

#include<iostream>
using namespace std;

void add(int a[], int x[], int q);

// 2の補数を求める関数
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);                // 1を加算して完成
}

// 2進加算を行う関数
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];            // 被乗数の入力
    for (i = brn - 1; i >= 0; i--)
        mt[i] = br[i];
    complement(mt, brn);         // 減算用に2の補数を作成
    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) {          // 01 または 10 の場合
            if (temp == 0) {
                add(ac, mt, qrn);          // BRを減算(2の補数を加算)
                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);          // BRを加算
                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) {      // 00 または 11 の場合
            ashr(ac, qr, qn, qrn);         // シフトのみ
        }
        display(ac, qr, qrn);
        cout << "\t";
        sc--;
        cout << "\t" << sc << "\n";
    }
    cout << "Result=";
    display(ac, qr, qrn);
}

コードの構成

• complement():ビット反転後に1を加算し、2の補数を生成します。
• add():桁上がり(carry)を管理しながら2進加算を行います。
• ashr():符号ビットを保持したまま、ACとQRを連結して1ビット右へ算術シフトします。
• main():入力を受け付け、ステップカウンタ(sc)が0になるまで加減算とシフトを繰り返します。

実行例

5ビットの被乗数「01111」(+15)と、5ビットの乗数「10111」(−9)を入力した場合の実行結果です。

--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

最終的な結果「11011 11001」(AC+QRの連結で10ビット)は、2の補数表現で−135を表します。これは 15 × (−9) = −135 と一致しており、符号付きの乗算が正しく行えたことが確認できます。