C++ 实现大数乘法算法完整代码

算法原理与思路

大数乘法的本质是将两个巨大的数字看作字符串数组，避免使用固定长度的整数类型。主要逻辑如下：

• 数据存储：使用 string 类型读取用户输入的两个大数。
• 角色分配：为了减少外层循环次数，通常将较短的字符串作为内层乘数，较长的作为被乘数（或在逻辑内部统一处理）。
• 逐位计算：类似于小学学习的乘法竖式。对于第一个数的每一位，乘以第二个数的所有位，并将结果累加到对应的临时结果数组中。
• 进位处理：每次计算当前位的乘积后，需加上上一位的进位值，然后分离出新的当前位值和新的进位值。
• 结果整理：由于计算过程是从低位开始向高位进行的，最终结果在内存中是逆序存储的，输出前需要进行翻转或逆向遍历。

开发环境准备

编写此程序只需标准的 C++ 编译器，如 GCC、Clang 或 MSVC。推荐使用支持 C++11 及以上标准的编译器以确保 string 和 STL 容器的良好兼容性。无需安装任何额外的数学库或大数插件。

第 1 步：初始化项目文件

创建一个新的源代码文件，例如 big_mul.cpp。确保文件中包含必要的头文件：<iostream> 用于输入输出，<string> 用于字符串操作，<cstring> 用于字符数组长度获取。

第 2 步：核心算法实现

以下是经过梳理和优化的 C++ 大数乘法代码。代码注释解释了关键步骤，包括内存分配、乘积累加和进位逻辑。

// 大数乘法算法实现
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{
    string num1, num2;
    cin >> num1 >> num2;

    // 确定较长和较短的字符串，便于后续逻辑处理
    const char* n1;
    const char* n2;
    if (num1.size() < num2.size())
    {
        n1 = num2.c_str(); // n1 为长数
        n2 = num1.c_str(); // n2 为短数
    }
    else
    {
        n1 = num1.c_str();
        n2 = num2.c_str();
    }

    // 分配结果存储空间，最大长度为两数长度之和
    char* n = new char[strlen(n1) + strlen(n2) + 1];
    
    // 初始化结果数组为 '0'
    for (unsigned int i = 0; i < strlen(n1) + strlen(n2); i++)
        n[i] = '0';
    n[strlen(n1) + strlen(n2)] = '\0';

    int count = 0, flag = 0;
    
    // 外层循环：遍历长数的每一位
    for (int i = strlen(n1) - 1; i >= 0; i--)
    {
        flag++;
        int x1 = n1[i] - '0';
        char carry = '0';
        
        // 内层循环：遍历短数的每一位
        for (int j = strlen(n2) - 1; j >= 0; j--)
        {
            int x2 = n2[j] - '0';
            // 计算当前位的乘积总和：自身乘积 + 进位 + 原位置的值
            int sum = x1 * x2 + (carry - '0') + n[count] - '0';
            
            // 更新当前位置的值和新的进位
            n[count++] = (sum % 10) + '0';
            carry = (sum / 10) + '0';
        }
        
        // 如果内层循环结束后还有进位，则写入下一位
        if (carry != '0')
        {
            n[count] = carry;
            count = flag; // 重置计数器以便处理下一行
        }
        else
        {
            count = flag;
        }
    }

    // 逆向输出结果，跳过前导零
    for (int i = strlen(n) - 1; i >= 0; i--)
    {
        // 如果是最高位且值为0（且不是唯一的0），则跳过
        if ((i == strlen(n) - 1) && (n[i] == '0'))
            continue;
        cout << n[i];
    }
    cout << endl;

    delete[] n;
    system("pause");
    return 0;
}

运行验证与排错

编译并运行上述代码后，可以通过控制台输入两个大整数进行验证。

正常测试用例

输入两个较大的数字，例如：

Input: 123456789 987654321
Output: 121932631112635269

观察输出结果是否与实际数学计算一致。

常见错误排查

• 段错误 (Segmentation Fault)：检查是否正确释放了堆内存 delete[] n，以及数组 n 的索引 count 是否在分配的长度范围内。如果在极端情况下计算出的位数超出预期，可能导致越界访问。
• 输出结果缺失前导零后的第一个非零位：在最后的输出循环中，逻辑判断 (i == strlen(n)-1) && (n[i] == '0') 旨在去除高位无效的零。但如果结果是纯 0，某些实现可能会漏掉输出。本代码逻辑在处理单个零时需特别注意边界条件，但在大多数大数乘积场景下，乘积不会为纯零除非其中一个因子为零。
• 性能问题：该算法时间复杂度为 $O(N \times M)$，其中 N 和 M 分别为两个大数的位数。对于普通应用足够，但若需处理超大规模数据（如数万位以上），建议改用 FFT（快速傅里叶变换）优化的高精度乘法。

简要总结

通过 C++ 字符串数组模拟手工乘法过程，可以有效解决标准数据类型溢出的问题。核心技巧在于正确维护进位变量和处理累加位置。以上就是C++实现大数乘法算法代码的详细内容，更多关于C++高精度计算的资料请关注本站其它相关文章！