C++高精度乘法详解

link管理

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

为什么需要高精度计算

对于 C++ 而言，最大的数据为 long long（64b，8位），对于超过 8B 的数据，C++ 没有对应的数据类型进行表示。所以我们需要知道高精度计算。更详细的解释，可以参考这个网页 https://blog.csdn.net/justidle/article/details/104414459 。

高精度乘法计算原理

在读小学时，我们做乘法都采用竖式方法，如图 1 所示。这样，我们可以写出两个整数相减的算法。

我们就可以用 C++ 语言来模拟这个竖式减法的过程。我们可以考虑利用 C++ 的数组来存储对应数据，假设用数组 A 存储被减数 856 的每一位，具体来说就是 A1 存储个位 6，A2 存储十位 5，A3存储百位 8；类似数组 A 的结构，使用数组 B 存储减数 25；类似数组 A 的结构，使用数组 C 来存储对应的乘积 21400。两数相加的结果就如图 2 所示。这样理论上来说，我们就可以计算无限大的数据。如上图 2 所示，下表表示对应的存储方式。

	数组 A	数组 B	数组 C
[0]	6	5	0
[1]	5	2	0
[2]	8		4
[3]			1
[4]			2

如上面的图 2 ，首先计算被乘数与乘数的个位数字的乘积，把结果保存到积数组中，然后再用被除数乘以乘数的十位数字，把结果退一位加到积数组中。每加一次乘积结果就进行一次进位处理，放在一个新组数里面。其方法与加法中的进位处理一样。

1 、 a[i]*b[j] 应该累加到 i+j 的位置；

2 、累加总结果为： c[i+j] = a[i]*b[j]+jw+c[i+j]；

3 、所以每次累加完后：

1 ）带入下一位累加的进位： jw = c[i+j] / 10；

2 ）本位实际数： c[i+j] %= 10 。

高精度乘法实现

1、定义存储数组。

2、读入数据处理。

3、从个位开始模拟竖式乘法的过程，完成整个乘法。

4、删除前导 0 。所谓前导零，就是出现类似这样数据 01234，这个 0 实际是不需要的。

5、输出结果。倒序输出减法的结果数组 C，因为我们的个位是存储在下标为 0 的地方。

技术细节说明

定义存储数组

根据题目的要求定义数组。这个部分代码如下：

const int MAXN = 1e5+4; //根据题目的最大值。+4为了防止A+B出现进位
char s1[MAXN] = {};//存储字符串
char s2[MAXN] = {};//存储字符串
int a[MAXN] = {};//存储加数A
int b[MAXN] = {};//存储加数B
int c[2*MAXN] = {};//存储乘积

读入数据并处理

这里我们先考虑以下几种情况，即 -3*5=-15 或者 -4*8=-32 或者 -3*(-2)=6，也就是说，需要对输入数据的正负号进行判断。这个部分代码如下：

    scanf("%s %s", s1, s2);//读入字符串
    //处理负数
    bool flaga = false;//乘数a的符号
    if ('-'==s1[0]) {
        flaga = true;
        strcpy(s1, &s1[1]);//删除负号
    bool flagb = false;//乘数b的符号
    if ('-'==s2[0]) {
        flagb = true;
        strcpy(s2, &s2[1]);//删除负号
    //处理输出的负号
    if ((true==flaga && false==flagb) || (false==flaga && true==flagb)) {
        printf("-");
    //处理乘数1
    int lena = strlen(s1);
    for (int i=0; i<lena; i++) {
        a[lena-i-1]=s1[i]-'0';
    //处理乘数2
    int lenb = strlen(s2);
    for (int i=0; i<lenb; i++) {
        b[lenb-i-1]=s2[i]-'0';
模拟竖式乘法 
这个部分代码如下： 
    //模拟竖式乘法
    int jw;//上一轮计算进位
    for (int i=0; i<lena; i++) {
        jw=0;
        for (int j=0; j<lenb; j++) {
            //交叉乘积
            c[i+j] = a[i]*b[j]+jw+c[i+j];//当前乘积+上次乘积进位+原数
            jw = c[i+j]/10;//处理进位
            c[i+j] %= 10;
        c[i+lenb]=jw;//进位设置
删除前导零 
这个部分代码如下： 
    //删除前导零
    int lenc=lena+lenb;
    for (int i=lenc-1; i>=0; i--) {
        //因为我们是从索引 0 开始，所以最高位是保存在 len-1
        if (0==c[i] && lenc>1) {
            //注意要有 lenc>1 这个条件。考虑特殊情况，加法结果为 00，我们实际要输出 0。
            lenc--;
        } else {
            //第一个不是零的最高位，结束删除
            break;
输出计算结果 
采用倒序的方式输出，因为我们数据保存是倒序结构，也就是低位在前。 
    //逆序打印输出
    for (int i=lenc-1; i>=0; i--) {
        printf("%d", c[i]);
    printf("\n"); 
例题和 AC 代码 
一本通 OJ：http://ybt.ssoier.cn:8088/problem_show.php?pid=1174，或者http://ybt.ssoier.cn:8088/problem_show.php?pid=1307。 
我自己 OJ：http://47.110.135.197/problem.php?id=1034。 
求两个不超过 200 位的非负整数的积。 
有两行，每行是一个不超过 200 位的非负整数，没有多余的前导 0。 
一行，即相乘后的结果。结果里不能有多余的前导 0，即如果结果是 342，那么就不能输出为 0342。 
12345678900
98765432100 
1219326311126352690000 
题目告诉我们不超过 200 位，也就是 MAXN = 200+4。特别的地方要注意乘积的长度为 2*MAXN。 
AC 代码 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200+4; //根据题目的最大值。+4为了防止A+B出现进位
char s1[MAXN] = {};//存储字符串
char s2[MAXN] = {};//存储字符串
int a[MAXN] = {};//存储加数A
int b[MAXN] = {};//存储加数B
int c[2*MAXN] = {};//存储和B
int main() {
    scanf("%s %s", s1, s2);//读入字符串
    //处理负数
    bool flaga = false;//乘数a的符号
    if ('-'==s1[0]) {
        flaga = true;
        strcpy(s1, &s1[1]);//删除负号
    bool flagb = false;//乘数b的符号
    if ('-'==s2[0]) {
        flagb = true;
        strcpy(s2, &s2[1]);//删除负号
    //处理输出的负号
    if ((true==flaga && false==flagb) || (false==flaga && true==flagb)) {
        printf("-");
    //处理乘数1
    int lena = strlen(s1);
    for (int i=0; i<lena; i++) {
        a[lena-i-1]=s1[i]-'0';
    //处理乘数2
    int lenb = strlen(s2);
    for (int i=0; i<lenb; i++) {
        b[lenb-i-1]=s2[i]-'0';
    //模拟竖式乘法
    int jw;//上一轮计算进位
    for (int i=0; i<lena; i++) {
        jw=0;
        for (int j=0; j<lenb; j++) {
            //交叉乘积
            c[i+j] = a[i]*b[j]+jw+c[i+j];//当前乘积+上次乘积进位+原数
            jw = c[i+j]/10;//处理进位
            c[i+j] %= 10;
        c[i+lenb]=jw;//进位设置
    //删除前导零
    int lenc=lena+lenb;
    for (int i=lenc-1; i>=0; i--) {
        //因为我们是从索引 0 开始，所以最高位是保存在 len-1
        if (0==c[i] && lenc>1) {
            //注意要有 lenc>1 这个条件。考虑特殊情况，加法结果为 00，我们实际要输出 0。
            lenc--;
        } else {
            //第一个不是零的最高位，结束删除
            break;
    //逆序打印输出
    for (int i=lenc-1; i>=0; i--) {
        printf("%d", c[i]);
    printf("\n");
    return 0;
模仿竖式乘法，在第一步计算的时候将进位保留，第一步计算完再处理进位。（见代码注释）
若要处理正负情况，可在数据输入后加以判断，处理比较简单。
小数计算也可参照该方法，不过对齐方式需要改变，或者改成二段计算。
#include &lt;iostream&gt;
#include &lt;cstring&gt;
#define MAXSIZE 20
#define MAXOUTS...
				C++ 高精度乘法可以使用 vector 容器来实现。具体步骤如下：
1. 定义两个 vector 容器存储两个高精度数，例如 vector<int> a 和 vector<int> b。
2. 定义一个 vector 容器存储结果，例如 vector<int> c，初始时将其填充为 0。
3. 从两个高精度数的最低位开始，按照竖式乘法的规则逐位相乘，将结果存储在 c 中相应的位置。
4. 处理进位，将 c 中每一位上的数字对 10 取模并记录进位，将进位值加到下一位的计算结果中。
5. 删除 c 中前导 0。
6. 将 c 中每一位上的数字转换为字符并拼接成字符串，即为高精度乘法的结果。
以下是基于 vector 实现的 C++ 高精度乘法示例代码：
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<int> multiply(vector<int> a, vector<int> b) {
    vector<int> c(a.size() + b.size(), 0); // 存储结果，初始值为 0
    for (int i = 0; i < a.size(); i++) {
        int carry = 0; // 进位值
        for (int j = 0; j < b.size(); j++) {
            int tmp = a[i] * b[j] + c[i + j] + carry; // 乘法计算
            c[i + j] = tmp % 10; // 取模
            carry = tmp / 10; // 进位
        if (carry) c[i + b.size()] += carry; // 处理最高位的进位
    while (c.size() > 1 && c.back() == 0) c.pop_back(); // 删除前导 0
    return c;
int main() {
    string num1, num2;
    cin >> num1 >> num2;
    vector<int> a, b;
    for (int i = num1.size() - 1; i >= 0; i--) a.push_back(num1[i] - '0');
    for (int i = num2.size() - 1; i >= 0; i--) b.push_back(num2[i] - '0');
    vector<int> c = multiply(a, b);
    for (int i = c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;
    return 0;
该代码中，输入的两个高精度数 num1 和 num2 都是字符串类型，需要将其转换为 vector 容器进行计算。输出结果时，需要将计算结果的 vector 容器中的数字逆序输出。