C++でビット演算子を使って2つの数値を乗算する方法

このチュートリアルでは、ビット演算子のみを使って、与えられた2つの数値の乗算を行うプログラムをC++で作成します。

乗算には左シフト（<<）演算子を、除算には右シフト（>>）演算子を使用します。

2つの数値 x と y の積は、yが偶数の場合 x * y = (x * 2) * (y / 2) と書き換えられます。yが奇数の場合は x * y = (x * 2) * (y / 2) + x となります。

つまり、第2の数値が奇数になるたびに、その時点の第1の数値を結果に加算していけばよいことになります。それでは、問題を解くための手順を見ていきましょう。

アルゴリズム

• 2つの数値を初期化します。
• 第2の数値が0になるまで繰り返すループを作成します。
  • 第2の数値が奇数の場合、第1の数値を結果に加算します。
  • 第1の数値を1ビット左シフトします。
  • 第2の数値を1ビット右シフトします。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include 
using namespace std;
int multiplyTwoNumbers(int a, int b) {
    int result = 0;
    while (b > 0) {
        if (b & 1) {
            result += a;
        }
        a = a << 1;
        b = b >> 1;
    }
    return result;
}
int main() {
    cout << multiplyTwoNumbers(75, 4) << endl;
    cout << multiplyTwoNumbers(90, 9) << endl;
    cout << multiplyTwoNumbers(83, 66) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

300
810
5478

処理の流れの解説

このアルゴリズムは、乗算を2進数の考え方に基づいて分解しています。例えば 90 × 9 の場合、9は2進数で 1001 と表されるため、結果は 90 × 8 + 90 × 1 = 720 + 90 = 810 として計算されます。ループの各ステップで第2の数値を右シフトしながら最下位ビットを確認し、ビットが立っている（奇数の）タイミングで左シフトされた第1の数値を加算することで、通常の乗算演算子（*）を使わずに積を求めることができます。

この手法は「ロシア農民乗算法」としても知られており、乗算命令が利用できない環境や、組み込みシステムなどでの低レベルな最適化において活用されてきました。