【C/C++】【高精度算法】1、高精度加法

一、为什么需要高精度算法

我们应该也有必要知道数据类型是有长度的吧。

比如32位？那位是？01一组01的二进制就是1位，8个1位放在一起叫做一个字节。

我们还记得int类型是4个字节，之前可能不知道啥意思，那放在这里，4*8是不是恰好等于32？

那32就是int类型的长度。很多情况下int类型是不能满足大数计算的。例如：计算 12345678901234567890 + 98765432109876543210

在很多情况下，普通的数据类型如int、long long等无法满足对极大整数进行计算的需求。比如计算非常大的阶乘、进行超大数的加法、乘法等运算时，就需要高精度算法来准确地处理这些数值。

1. 超出数据类型范围

   • C++ 中的普通数据类型如int、long long等都有一定的表示范围。当需要处理的整数超出这个范围时，就无法使用普通的数据类型进行计算。
   • 例如，计算两个非常大的数的和，如 12345678901234567890 + 98765432109876543210，普通的数据类型无法存储和计算这样的大整数。

2. 准确性要求

   • 在一些应用场景中，需要精确的计算结果，不能有任何误差。高精度加法运算可以确保计算的准确性，不会因为数据超出范围而出现溢出或错误的结果。
   • 比如在密码学、数值计算等领域，对计算结果的准确性要求非常高，高精度加法运算就显得尤为重要。

3. 灵活性

   • 高精度加法运算可以处理任意长度的大整数，不受数据类型的限制。这使得程序在处理大整数问题时更加灵活，可以适应不同的需求。
   • 无论是计算非常大的整数，还是处理位数不确定的大整数，高精度加法运算都能提供可靠的解决方案。

其实这个过程就是把数字当作文字输入进来，再放进int数组中。然后利用算法计算两个int数组的和就完了。

让我们来详细学习一下吧：

高精度加法运算的步骤

1. 数据存储

   • 首先，将大整数用数组存储，数组的每个元素存储一位数字，通常从低位到高位依次存储。例如，整数 12345 可以存储为数组 [5,4,3,2,1]。
   • 这样存储的好处是便于逐位进行运算和处理进位。

2. 对齐操作

   • 如果要相加的两个大整数位数不同，需要进行对齐操作。可以在较短的数前面补零，使得两个数的位数相同，方便后续的逐位相加。
   • 例如，要计算 1234 和 987654，将 1234 表示为 [4,3,2,1,0,0]，987654 表示为 [4,5,6,7,8,9]。

3. 逐位相加

   • 从低位向高位逐位相加。对于每一位，将两个数对应位上的数字相加，并加上前一位的进位值。
   • 如果相加的结果小于 10，则直接将结果作为当前位的值，并且进位值为 0。
   • 如果相加的结果大于等于 10，则将结果对 10 取余作为当前位的值，并且进位值为 1。
   • 例如，计算上述对齐后的两个数，从最低位开始相加，0 + 4 = 4，没有进位；接着是 1 + 5 = 6，也没有进位…… 以此类推，直到最高位。

4. 处理进位

   • 当所有位都相加完毕后，如果进位值为 1，说明最高位有进位，需要在结果数组的最高位添加一个 1。
   • 例如，在前面的例子中，如果最高位相加后有进位，结果数组应该是 [5,8,9,9,1,0,0]。

5. 输出结果

   • 最后，将结果数组从高位到低位输出，即为两个大整数相加的结果。
     
     
      

详细代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=250;
//stringA和b
char sa[maxn],sb[maxn];
//a原数组1，b原数组2，c加后的数组
int a[maxn],b[maxn],c[maxn];
int main(){
	//sa是大数字1，sb是大数字2.字符串类型的
	scanf("%s",sa);
	scanf("%s",sb);
	//第二步是把大数string，放到int数组中。
	int la=strlen(sa);
	int lb=strlen(sb);
	for(int i=0;i<la;i++){
		//倒着放，字符减去字符‘0’代表了一个数字本身
		a[la-i-1]=sa[i]-'0';
	}
	for(int i=0;i<lb;i++){
		//倒着放，字符减去字符‘0’代表了一个数字本身
		b[lb-i-1]=sb[i]-'0';
	}
	//lc是新数组的长度
	int lc=la>lb?la:lb;
	for(int i=0;i<lc;i++){
		c[i]=a[i]+b[i]+c[i];
		//进位
		if(c[i]>=10){
			c[i+1]=c[i]/10;
			//剩下的数存起来
			c[i]=c[i]%10;
		}
	}
	//看一下最后一位有没有进位，如果最后一位上的数字是大于0的，给再加一位
	if(c[lc]>0)lc++;
	//倒着输出c就好了
	for(int i=lc-1;i>=0;i--){
		printf("%d",c[i]);
	}
	
	//当然如果题中有说先导0，比如001+0004的情况
	//可以去除先导0
	cout<<endl;
	int cnt=lc-1;
	while(c[cnt]==0){
		cnt--;
	}
	for(int i=cnt;i>=0;i--){
		printf("%d",c[i]);
	}
	return 0;  
}

当然这个过程只是帮助我们学习大整数的原理，我们还可以通过简单点的vector来实现。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 高精度加法函数
vector<int> add(vector<int> a, vector<int> b) {
    vector<int> c;
    int carry = 0; // 进位标志，初始为 0
    for (size_t i = 0; i < max(a.size(), b.size()); ++i) {
        int sum = carry; // 当前位的和初始为进位值
        if (i < a.size()) sum += a[i]; // 如果 a 数组还有当前位，则加上
        if (i < b.size()) sum += b[i]; // 如果 b 数组还有当前位，则加上
        c.push_back(sum % 10); // 将当前位的和对 10 取余，得到当前位的结果存入结果数组 c
        carry = sum / 10; // 更新进位值为当前位的和除以 10
    }
    if (carry > 0) c.push_back(carry); // 如果最后还有进位，则将进位存入结果数组
    return c;
}

// 输出结果函数
void print(vector<int> v) {
    for (auto it = v.rbegin(); it!= v.rend(); ++it) {
        cout << *it; // 从高位到低位输出结果数组中的数字
    }
    cout << endl;
}

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

    vector<int> a, b;
    for (int i = num1.length() - 1; i >= 0; --i) {
        a.push_back(num1[i] - '0'); // 将输入的第一个大整数转换为数字数组，从低位到高位存储
    }
    for (int i = num2.length() - 1; i >= 0; --i) {
        b.push_back(num2[i] - '0'); // 将输入的第二个大整数转换为数字数组，从低位到高位存储
    }

    vector<int> result = add(a, b);
    print(result);

    return 0;
}