C++で文字列同士の乗算を実装する方法

文字列として与えられた2つの数値があるとします。この2つを掛け合わせ、その結果も文字列として返すことを考えます。例えば、「26」と「12」が入力された場合、出力は「312」になります。

数値をそのまま int や long long に変換して掛けることも可能ですが、非常に大きな数を扱う場合はオーバーフローが発生する恐れがあります。そこで、文字列のまま筆算をシミュレートする方法が有効です。

解決の手順

• 2つの数値文字列 num1 と num2 を引数として受け取ります。
• m桁 × n桁の積は最大でも m+n 桁に収まるため、長さが「num1の桁数 + num2の桁数」である文字列 ans を用意し、すべて '0' で初期化します。
• num1 と num2 の各桁を最下位桁から順に取り出し、互いに掛け合わせます。
• 掛け算の結果に、ans の対応する位置（i + j + 1）に既に格納されている値を加えます。
• その値の下位1桁（p % 10）を現在の位置に書き込み、商（p / 10）は一つ上の位（i + j）へ繰り上がりとして加算します。
• すべての桁の計算が完了したら、先頭の余分な '0' をスキップし、残りの部分文字列を返します。
• 結果がすべて '0' の場合（入力のどちらかが "0" の場合など）は "0" を返します。

C++での実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string multiply(string num1, string num2);
};
string Solution::multiply(string nums1, string nums2) {
    int n = nums1.size();
    int m = nums2.size();
    string ans(n + m, '0');
    for(int i = n - 1; i>=0; i--){
        for(int j = m - 1; j >= 0; j--){
            int p = (nums1[i] - '0') * (nums2[j] - '0') + (ans[i + j + 1] - '0');
            ans[i+j+1] = p % 10 + '0';
            ans[i+j] += p / 10 ;
        }
    }
    for(int i = 0; i < m + n; i++){
        if(ans[i] !='0')return ans.substr(i);
    }
    return "0";
}
main(){
    Solution ob;
    cout << ob.multiply("28", "25");
}

入力

"26"
"12"

出力

"312"

まとめ

この手法では、各桁の掛け算と繰り上がり処理を文字列操作だけで行うため、標準の整数型では表現できないような巨大な数同士の乗算にも対応できます。計算量は O(n×m) であり、桁数が大きくなっても安定して動作する点が大きな利点です。