0 前言
当我们遇到需要处理非常大的整数的情况时,标准的数据类型如int或long long int可能无法满足需求,因为这些类型的数值范围有限。在这种情况下,我们需要一种方法来处理超出常规数据类型范围的大整数。本文将介绍如何使用C++实现大整数相加。
1 大整数相加的基本原理
从最低位开始逐位相加,并处理进位。由于C++的标准数据类型不足以存储非常大的数,我们可以使用字符串来存储这些大整数。每个字符代表一个数字,通过遍历字符串中的每一位来进行加法运算。
2 实现步骤
2.1 输入处理:
为了方便计算,将这两个字符串反转,较长的在上方,较短的在下方,使得个位对齐,较短的数值高位使用0补充。如下图所示。
2.2 加法运算
- 初始化一个变量用于保存进位值,例如变量carry。
- 从最低位开始,同时遍历两个字符串的每一位,计算当前位的和加上进位值。
- 如果当前位的和大于等于10,则设置进位值为1,否则为0。
- 当前位的结果为和模10的值。
算法过程如下图所示。
3 代码
点击查看代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 大整数相加函数
string add(string num1, string num2)
{
//保存计算信息及结果
vector<vector<char>> arr(3, vector<char>(max(num1.length(), num2.length()), '0'));
//较长的串在上方,默认s1串在上方,s2在下方,最底行保存计算结果。
string s1 = num1.length() > num2.length() ? num1 : num2;
string s2 = num1.length() < num2.length() ? num1 : num2;
//反序后填入到arr中
reverse(s1.begin(), s1.end());
for (int a = 0; a < s1.length(); ++a)
{
arr[0][a] = s1.at(a);
}
reverse(s2.begin(), s2.end());
for (int a = 0; a < s2.length(); ++a)
{
arr[1][a] = s2.at(a);
}
//进位值
int carry = 0;
//从左往右依次计算
for (int a = 0; a <= arr.front().size()-1; ++a)
{
arr[0][a] += carry;//第一个值加上进位值
carry = 0;
short v1 = arr[0][a] - '0';
short v2 = arr[1][a] - '0';
if (v1 + v2 >= 10)//需要设置进位
{
carry = (v1 + v2) / 10;//相加结果>=10,需要设置进位
arr[2][a] = ((v1 + v2) % 10) + '0';//计算结果为取模10
}
else//不需要设置进位
{
arr[2][a] = (v1 + v2) + '0';
}
}
//反序
string res("");
for (int a = arr.front().size() - 1; a >= 0; --a)
{
res = res.append(1, arr[2][a]);
}
return res;
}
int main()
{
//相乘的两个整数
string num1 = "123456";
string num2 = "8762";
string ret = add(num1, num2);
cout << "两个整数和: " << ret << endl;
return 0;
}
点击查看运行结果
两个整数乘积为: 132182
D:\Visual Studio 2019\项目\大整数加法\x64\Debug\大整数加法.exe (进程 12336)已退出,代码为 0。
按任意键关闭此窗口. . .