C++
高精度乘法算法
admin SU @ 2025-5-16 10:05:53

C++ 高精度乘法教程（零基础版）

在日常编程中，我们经常需要处理数值计算。但当数字非常大时，比如超过了 C++ 内置数据类型（像 int、long long）的表示范围，该怎么办呢？这时候就需要用到高精度算法了。本教程将带你从零开始学习高精度乘法的实现，即使你是编程小白也能轻松理解！

为什么需要高精度算法？

C++ 中的基本数据类型都有一定的数值范围限制：

int 通常只能表示到约 21 亿（2^31 - 1）
long long 能表示的范围大约是 ±9e18
而在实际应用中，可能会遇到像天文数字、密码学中的大质数等远远超过这些范围的数

高精度算法的核心思想是：用字符串或数组来存储大数的每一位，然后模拟手工计算的过程。

高精度乘法的基本思路

我们小学时学过的多位数乘法是这样的：

    123
  ×  45
  ------
    615   (123 × 5)
   4920   (123 × 4，注意这里要左移一位)
  ------
   5535   (615 + 4920)

高精度乘法就是模拟这个过程：

将两个大数以字符串的形式存储
逐位相乘并处理进位
累加中间结果
处理前导零并输出结果

下面我们一步步实现这个算法！

完整代码实现

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 高精度乘法函数
string multiply(string num1, string num2) {
    // 处理特殊情况：如果任一数为0，则结果为0
    if (num1 == "0" || num2 == "0") return "0";
    
    // 获取两个数的长度
    int n = num1.size();
    int m = num2.size();
    
    // 结果数组，长度最多为 n + m 位
    vector<int> result(n + m, 0);
    
    // 从右向左遍历两个数的每一位
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            // 将字符转换为数字
            int digit1 = num1[i] - '0';
            int digit2 = num2[j] - '0';
            
            // 计算乘积
            int product = digit1 * digit2;
            
            // 计算在结果数组中的位置
            int p1 = i + j;      // 当前位
            int p2 = i + j + 1;  // 进位位
            
            // 计算总和（包括之前的进位）
            int sum = product + result[p2];
            
            // 更新结果数组
            result[p2] = sum % 10;  // 当前位的值
            result[p1] += sum / 10; // 进位值
        }
    }
    
    // 构建结果字符串
    string res;
    for (int num : result) {
        // 跳过前导零
        if (!(res.empty() && num == 0)) {
            res.push_back(num + '0');
        }
    }
    
    return res;
}

int main() {
    string num1, num2;
    
    // 输入两个大数
    cout << "请输入第一个大数: ";
    cin >> num1;
    cout << "请输入第二个大数: ";
    cin >> num2;
    
    // 调用高精度乘法函数
    string product = multiply(num1, num2);
    
    // 输出结果
    cout << "乘积结果: " << product << endl;
    
    return 0;
}

代码详细解释

1. 函数参数与特殊情况处理

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    // ...
}

函数接收两个字符串形式的大数作为参数
先处理特殊情况：如果任一数为 0，则直接返回 0

2. 初始化结果数组

int n = num1.size();
int m = num2.size();
vector<int> result(n + m, 0);

result 数组用于存储中间计算结果
两个数相乘的结果最多有 n + m 位（例如 99 × 99 = 9801，4 位）

3. 逐位相乘并处理进位

for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
        int digit1 = num1[i] - '0';
        int digit2 = num2[j] - '0';
        int product = digit1 * digit2;
        int p1 = i + j;
        int p2 = i + j + 1;
        int sum = product + result[p2];
        result[p2] = sum % 10;
        result[p1] += sum / 10;
    }
}

从右向左遍历两个数的每一位（个位开始）
digit1 和 digit2 分别表示当前位的数值
product 是当前两位的乘积
p1 和 p2 是乘积在结果数组中的位置
sum 是乘积加上之前的进位
更新当前位和进位位的值

4. 构建结果字符串

string res;
for (int num : result) {
    if (!(res.empty() && num == 0)) {
        res.push_back(num + '0');
    }
}

遍历结果数组，将数字转换为字符
跳过前导零（当结果字符串还为空且当前数字为 0 时）

5. 主函数

int main() {
    string num1, num2;
    cout << "请输入第一个大数: ";
    cin >> num1;
    cout << "请输入第二个大数: ";
    cin >> num2;
    string product = multiply(num1, num2);
    cout << "乘积结果: " << product << endl;
    return 0;
}

读取用户输入的两个大数
调用乘法函数计算结果
输出最终结果

示例运行

请输入第一个大数: 123456789
请输入第二个大数: 987654321
乘积结果: 121932631112635269

复杂度分析

时间复杂度：O(n × m)，其中 n 和 m 分别是两个数的位数
空间复杂度：O(n + m)，主要用于存储结果数组

注意事项

输入的数必须是合法的非负整数
该算法处理的是两个非负数的乘法，如果需要处理负数，可以在函数外添加符号判断逻辑
对于非常大的数，计算可能会比较慢，但这是高精度算法的普遍特点

通过这个教程，你已经学会了如何用 C++ 实现高精度乘法！这种方法虽然比直接使用内置类型复杂一些，但它能处理任意大小的数，是解决大数计算问题的有效手段。

admin SU @ 2025-5-19 21:26:36

以下是添加了详细注释的代码：

#include <iostream>
#include <vector>
using namespace std;

// 将字符串逆序转为 vector<int>
// 例如：输入字符串 "123"，转换为向量 [3, 2, 1]
vector<int> strToVec(const string& s) {
    vector<int> res;
    // 从字符串的最后一个字符开始处理，将字符转换为数字并逆序存储
    for (int i = s.size() - 1; i >= 0; i--)
        res.push_back(s[i] - '0'); // '0' 的 ASCII 值为 48，字符数字减去 '0' 得到对应的数值
    return res;
}

// 高精度乘法函数 - 模拟竖式乘法
vector<int> multiply(const vector<int>& A, const vector<int>& B) {
    // 初始化结果数组，长度为两数位数之和（两数相乘的最大位数）
    vector<int> res(A.size() + B.size(), 0);
    
    // 模拟竖式乘法：逐位相乘并累加结果
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            res[i + j] += A[i] * B[j]; // 不考虑进位，直接累加乘积到对应位置
        }
    }
    
    // 处理进位
    int carry = 0;
    for (int i = 0; i < res.size(); i++) {
        int temp = res[i] + carry; // 当前位的值加上进位
        res[i] = temp % 10;        // 保留当前位的个位数
        carry = temp / 10;         // 计算进位值，将在下一步处理更高位
    }
    
    // 去掉前导0（例如，避免结果为 003 这种情况）
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();
    
    return res;
}

// 打印结果（逆序输出向量，恢复正确顺序）
void printResult(const vector<int>& v) {
    // 从向量的最后一个元素开始输出，恢复为正确的数字顺序
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << endl;
}

int main() {
    string a, b;
    cout << "请输入第一个大整数：";
    cin >> a;
    cout << "请输入第二个大整数：";
    cin >> b;
    
    // 将输入的字符串转换为逆序的数字向量
    vector<int> A = strToVec(a);
    vector<int> B = strToVec(b);
    
    // 执行高精度乘法
    vector<int> result = multiply(A, B);
    
    // 输出结果
    cout << "乘积结果是：" << endl;
    printResult(result);
    
    return 0;
}

代码说明：

输入处理：
- strToVec 函数将输入的字符串按字符逆序转换为数字向量（低位在前，高位在后），方便后续计算。
高精度乘法：
- multiply 函数模拟竖式乘法，逐位相乘并累加结果。
- 结果数组长度初始化为两数位数之和，确保足够存储最大可能的乘积。
- 处理进位时，从低位到高位逐位计算并更新进位值。
结果处理：
- 去除结果中的前导零（如 003 会被处理为 3）。
- printResult 函数将结果向量逆序输出，恢复正确的数字顺序。
主函数流程：
- 读取用户输入的两个大整数。
- 转换为逆序向量后进行乘法运算。
- 输出最终乘积结果。

算法关键点：

逆序存储：将数字按低位在前存储，便于逐位计算和进位处理。
进位处理：逐位处理进位，确保结果正确性。
前导零处理：确保结果不包含多余的前导零。

admin SU @ 2025-5-16 10:07:29

C++ 高精度乘法教程（0基础通俗易懂）

📚 什么是高精度乘法？

在C++中，int、long long 等基本数据类型都有其表示范围的限制。比如：

int：通常是 -2147483648 ~ 2147483647
long long：通常是 -9223372036854775808 ~ 9223372036854775807

如果我们想计算像这样的大数相乘：

12345678901234567890 * 98765432109876543210

那用普通的 * 运算符是不行的，因为结果会超出 long long 的范围，导致溢出。

所以我们就需要自己模拟乘法运算的过程，这就是所谓的 “高精度乘法”。

🧠 基本思路：模拟竖式乘法

我们小时候学过怎么做竖式乘法：

       123
     × 45
   -------
       615   ← 123 × 5
     492     ← 123 × 4，向左移一位
   -------
     5535

我们可以把两个大整数当作字符串来处理，然后按位模拟这个过程。

🛠️ 数据结构选择

我们使用 vector<int> 来存储每一位数字，这样便于操作和进位。

例如：

string a = "123";
vector<int> A;
for (int i = a.size() - 1; i >= 0; i--)
    A.push_back(a[i] - '0');

这样 A = {3, 2, 1} 就是逆序存储的数字，方便从个位开始计算。

📌 步骤总结

输入两个大整数（字符串形式）
把它们逆序转成 vector<int>
模拟竖式乘法，逐位相乘并累加
处理进位
输出结果（记得反转回来）

💻 示例代码（完整可运行）

#include <iostream>
#include <vector>
using namespace std;

// 将字符串逆序转为 vector<int>
vector<int> strToVec(const string& s) {
    vector<int> res;
    for (int i = s.size() - 1; i >= 0; i--)
        res.push_back(s[i] - '0');
    return res;
}

// 高精度乘法函数
vector<int> multiply(const vector<int>& A, const vector<int>& B) {
    vector<int> res(A.size() + B.size(), 0); // 初始化结果数组，最大长度是两数位数之和

    // 模拟竖式乘法
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            res[i + j] += A[i] * B[j]; // 先不考虑进位
        }
    }

    // 处理进位
    int carry = 0;
    for (int i = 0; i < res.size(); i++) {
        int temp = res[i] + carry;
        res[i] = temp % 10;
        carry = temp / 10;
    }

    // 去掉前导0
    while (res.size() > 1 && res.back() == 0)
        res.pop_back();

    return res;
}

// 打印结果
void printResult(const vector<int>& v) {
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << endl;
}

int main() {
    string a, b;
    cout << "请输入第一个大整数：";
    cin >> a;
    cout << "请输入第二个大整数：";
    cin >> b;

    vector<int> A = strToVec(a);
    vector<int> B = strToVec(b);

    vector<int> result = multiply(A, B);

    cout << "乘积结果是：" << endl;
    printResult(result);

    return 0;
}

📖 示例运行

输入：

请输入第一个大整数：123
请输入第二个大整数：45

输出：

乘积结果是：
5535

✅ 总结知识点

内容	说明
使用 `vector<int>`	存储每一位数字，方便操作
逆序存储	方便从个位开始计算
双重循环模拟竖式乘法	类似手算过程
进位处理	每一步都要处理进位
去除前导0	结果可能有多余的0

🧪 练习建议

你可以试着实现以下功能：

支持负数相乘（判断符号）
实现高精度除法
把结果写入文件或读取文件中的大数进行计算

🙋‍♂️ 如何继续学习？

如果你已经理解了高精度乘法，可以尝试挑战以下内容：

高精度幂运算（如 $a^b$ ）
高精度阶乘（如 $1000!$ ）
大数取模
大数比较大小

如果你有具体问题或者希望我扩展哪部分内容，请告诉我！😊

高精度乘法算法

C++ 高精度乘法教程（零基础版）

为什么需要高精度算法？

高精度乘法的基本思路

完整代码实现

代码详细解释

1. 函数参数与特殊情况处理

2. 初始化结果数组

3. 逐位相乘并处理进位

4. 构建结果字符串

5. 主函数

示例运行

复杂度分析

注意事项

2 条评论

代码说明：

算法关键点：

C++ 高精度乘法教程（0基础通俗易懂）

📚 什么是高精度乘法？

🧠 基本思路：模拟竖式乘法

🛠️ 数据结构选择

📌 步骤总结

💻 示例代码（完整可运行）

📖 示例运行

✅ 总结知识点

🧪 练习建议

🙋‍♂️ 如何继续学习？

状态

开发

支持

高精度乘法算法

C++ 高精度乘法教程（零基础版）

为什么需要高精度算法？

高精度乘法的基本思路

完整代码实现

代码详细解释

1. 函数参数与特殊情况处理

2. 初始化结果数组

3. 逐位相乘并处理进位

4. 构建结果字符串

5. 主函数

示例运行

复杂度分析

注意事项

2 条评论

代码说明：

算法关键点：

C++ 高精度乘法教程（0基础通俗易懂）

📚 什么是高精度乘法？

🧠 基本思路：模拟竖式乘法

🛠️ 数据结构选择

📌 步骤总结

💻 示例代码（完整可运行）

📖 示例运行

✅ 总结知识点

🧪 练习建议

🙋‍♂️ 如何继续学习？

状态

开发

支持

还没有账户？

登录