C++ 高精度乘法运算的实现

时间:2023-02-03 CairBin 人气:0

思想

首先确定乘积的位数。

假设两个非负整数a和b，n1为a的长度（位数），n2为b的位数，记n为c=a*b的位数，则有：

计算两个乘数每位数字的乘积，其中a[i]乘b[j]累加到c[i+j]上去

在最后对累加结果数组c作一次性进位（判断是否大于等于10）

代码

知道上述原理，很容易就写出代码

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>

using namespace std;
int main()
{
    //输入时处理，包含置0、逆置、转换成真实数字等步骤
    string s;
    cin >> s;
    int n1 = s.length();    //长度
    char str1[10];
    memset(str1, 0, sizeof(str1));
    for (int i = 0; i < n1;i++)
        str1[i] = s[n1 - i - 1]-'0';
    
    string s2;
    cin >> s2;
    int n2 = s2.length();
    char str2[10];
    memset(str2, 0, sizeof(str2));
    for (int i = 0; i < n2;i++)
        str2[i] = s2[n2 - i - 1]-'0';


    char res[20];
    memset(res, 0, sizeof(res));

    //核心代码
    int i, j;
    for (i = 0; i < n1;i++)
        for (j = 0; j < n2;j++)
            res[i + j] += str1[i] * str2[j];

    for (i = 0; i < n1 + n2;i++)
    {
        if(res[i]>=10)
        {
            res[i + 1] += res[i] / 10;
            res[i] %= 10;
        }

    }

    //从不为0的那一位开始输出（删除前导0），如果全部为0，则输出0
    int k;
    for (k = n1 + n2 - 1; !res[k]&&k>0; k--)
        ;   //注意这个分号

    for (int i = k; i >= 0; i--)
        cout << int(res[i]);
    cout << endl;


    return 0;
}

加载全部内容