高精度加法和减法

高精度加法

在C/C++中，我们经常会碰到限定数据范围的情况，我们先来看看常用的int和long long两种数据类型的范围吧。
C++标准规定：int占一个机器字长。在32位系统中int占32位，即4个字节，所以int的范围是[-2的31次方，2的31次方-1]，为1e8数量级；longlong的范围则是[-2的63次方，2的63次方-1]，为1e18数量级。如果超过该数量级，该怎么办?
此时就需要用到高精度算法

输入两个整数a,b输出他们的和（a,b<=10的500次方）

这时我们只能使用高精度来解决

高精度加法的核心思想：

1.将大数分解成每一位的数字：将大数按位分解为数组或字符串形式，使得可以逐位进行加法操作。通常情况下，数字的每一位都会以逆序存储（即个位在前），方便进行加法。

2.逐位加法：从最低位开始进行加法。对于每一位，计算对应的数字之和，并处理进位。进位可能会影响到下一位的计算，因此需要将进位信息传递到下一位。

3.处理进位：每一位的计算可能会产生进位，需要将进位加到下一位的计算中。

4.去除前导零：计算完所有位后，结果可能会有前导零，需要去除这些零以得到最终的结果。

高精度加法的步骤：

1.初始化：

创建足够大的数组来存储每一位的结果，通常比输入数字的长度多一个位置以处理进位。

2.数字转换：

将输入的大数（字符串形式）转换为数字形式，并存储在数组中。由于我们处理的数字是逆序存储的，个位在数组的第一个位置。

3.执行加法：

从最低位（数组的第一个位置）开始，对每一位进行加法操作。计算每一位的和，并存储在结果数组中，同时处理进位。

4.处理进位：

每次加法操作后，计算进位并将其加到下一位的计算中。

5.去除前导零：

检查结果数组中是否有前导零，并将其去除。

6.输出结果：

从结果数组中输出高精度加法的结果，通常是从数组的最后一个有效位置（最高位）开始输出。
在这里插入图片描述
我们来看一道题这道题就运用了高精度加法
代码如下：

#include <iostream>
#include <cstring>  // 用于 strlen 函数
#include <algorithm> // 用于 max 函数
using namespace std;char s1[505], s2[505]; // 存储输入的大数
int a[505], b[505], c[505]; // 存储数字形式的输入和结果int main()
{int la, lb, lc; // s1、s2 和结果数组的长度// 读取两个大数作为字符串cin >> s1;cin >> s2;// 获取两个输入字符串的长度la = strlen(s1);lb = strlen(s2);// 将 s1 的字符转换为整数，并以逆序存储到数组 a 中for (int i = 0; i < la; i++){a[la - i] = s1[i] - '0'; // 通过减去 '0' 将字符转换为整数}// 将 s2 的字符转换为整数，并以逆序存储到数组 b 中for (int i = 0; i < lb; i++){b[lb - i] = s2[i] - '0'; // 通过减去 '0' 将字符转换为整数}// 确定结果数组的最大长度，加一是为了处理可能的进位lc = max(la, lb) + 1;// 逐位进行加法运算for (int i = 1; i <= lc; i++){c[i] += a[i] + b[i]; // 将对应位的数字和进位相加c[i + 1] = c[i] / 10; // 计算进位c[i] = c[i] % 10; // 当前位的结果}// 移除结果数组中的前导零if (c[lc] == 0 && lc > 0){lc--;}// 从最高位到最低位打印结果for (int i = lc; i > 0; i--){cout << c[i]; // 打印结果的每一位}return 0;
}

下面是用y总模板写的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 使用向量实现高精度加法
vector<int> add(vector<int> &A, vector<int> &B)
{// 确保 A 总是比 B 长（长度可能不同）if (A.size() < B.size()) return add(B, A);vector<int> C; // 存储结果的向量int carry = 0; // 存储当前位的进位// 遍历 A 中的每一位for (int i = 0; i < A.size(); i++){carry += A[i]; // 将 A 的当前位加到 carry 中if (i < B.size()) carry += B[i]; // 如果 B 还有相应位，加上 B 的当前位C.push_back(carry % 10); // 当前位的结果是 carry 除以 10 的余数carry /= 10; // 更新进位 carry，即 carry 除以 10 的商}// 如果最后还有进位 carry，则将其添加到结果中if (carry) C.push_back(carry);return C; // 返回结果
}int main()
{string s1, s2;cin >> s1 >> s2;// 将输入字符串转换为向量（每个字符转换为整数，且逆序存储）vector<int> A(s1.size()), B(s2.size());for (int i = 0; i < s1.size(); i++) {A[s1.size() - 1 - i] = s1[i] - '0';}for (int i = 0; i < s2.size(); i++) {B[s2.size() - 1 - i] = s2[i] - '0';}// 调用加法函数得到结果vector<int> C = add(A, B);// 去除前导零并输出结果int start = C.size() - 1;while (start > 0 && C[start] == 0) {start--;}for (int i = start; i >= 0; i--) {cout << C[i];}cout << endl;return 0;
}

高精度加法模板

模板来自于y总

#include <vector>
using namespace std;
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{// 确保 A 总是比 B 长（长度可能不同）if (A.size() < B.size()) return add(B, A);vector<int> C; // 存储结果的数组int t = 0;     // 存储当前位的和以及进位// 遍历 A 中的每一位for (int i = 0; i < A.size(); i ++ ){t += A[i]; // 将 A 的当前位加到 t 中if (i < B.size()) t += B[i]; // 如果 B 还有相应位，加上 B 的当前位C.push_back(t % 10); // 当前位的结果是 t 除以 10 的余数t /= 10; // 更新进位 t，即 t 除以 10 的商}// 如果最后还有进位 t，则将其添加到结果中if (t) C.push_back(t);return C; // 返回结果
}

高精度减法

基本步骤

1. 数的表示方式

由于普通数据类型不能表示超大整数，高精度减法通常将两个大数以字符串或数组的形式存储。每一位数字分别存储到字符串或数组的元素中，从而避免溢出的问题。

2. 确定符号与大小

在进行减法之前，首先要确定两个大数的大小，判断被减数和减数的相对大小，以确保不会出现负数。
如果被减数小于减数，那么结果为负数，符号应在结果前加上负号。
如果被减数大于或等于减数，则可以直接进行相减操作。

3. 位对位相减

高精度减法的核心是模仿我们平常手算的逐位相减：
从最低位（即末尾）开始，依次对每一位进行减法运算。
如果当前位的被减数小于减数，需要向高位借位，将高位的值减1，当前位的值加上10再进行减法。
重复这个过程，直到所有位都减完。

4. 处理借位

当某一位的减数大于被减数时，就需要从高位借位。这一步骤的难点在于需要处理连续的借位情况：
若上一位需要借位，则本位需减1，并继续判断是否需要继续借位。

5. 去除前导零

计算完所有位后，可能会出现前导零（如1000 - 999 = 0001）。此时需要去掉这些前导零，确保结果的格式正确。
在这里插入图片描述
我们来看一道题这道题就运用了高精度减法
代码如下：

#include<iostream>
#include<cstring>  // 用于strlen, strcpy等字符串处理函数
using namespace std;char s1[10090], s2[10090], s3[10090];  // 字符数组用于存储输入的两个字符串以及临时交换用的字符串
int a[10090], b[10090], c[10090];      // 数组a, b分别存储字符串s1和s2的数字表示，c存储结果
int flag = 0;                          // 标志变量，用于判断是否需要输出负号// 比较两个字符串表示的数值大小，如果s1 >= s2返回true，否则返回false
bool compare(char s1[], char s2[])
{int u = strlen(s1), v = strlen(s2);   // 获取s1和s2的长度if (u != v)                          // 如果长度不同，则长度大的数更大{return u > v;}for (int i = 0; i < u; i++)          // 长度相同的情况下，逐位比较{if (s1[i] != s2[i])              // 如果某一位不同，则返回该位较大的结果{return s1[i] > s2[i];}}return true;                         // 如果所有位都相同，s1 == s2，返回true
}int main()
{int la, lb, lc;   // 定义变量存储s1、s2的长度以及最终结果的位数cin >> s1 >> s2;  // 输入两个字符串表示的大数// 如果s1 < s2，交换s1和s2，使得大数在前if (!compare(s1, s2)){flag = 1;                // 标志置为1，表示需要输出负号strcpy(s3, s1);          // 用临时数组s3保存s1的值strcpy(s1, s2);          // 将s2赋值给s1strcpy(s2, s3);          // 将临时数组s3的值赋给s2，完成交换}la = strlen(s1);  // 获取s1的长度lb = strlen(s2);  // 获取s2的长度// 将s1和s2的字符转为数字并倒序存入a和b数组for (int i = 0; i < la; i++){a[la - i] = s1[i] - '0';  // 将s1的第i个字符转为数字，倒序存入a}for (int i = 0; i < lb; i++){b[lb - i] = s2[i] - '0';  // 将s2的第i个字符转为数字，倒序存入b}lc = max(la, lb);  // lc是结果的最大可能位数，即la和lb中的最大值// 从低位到高位进行逐位减法for (int i = 1; i <= lc; i++){if (a[i] < b[i])   // 如果当前位a[i]小于b[i]，需要向高位借位{a[i + 1]--;    // 向高位借1a[i] += 10;    // 当前位加10}c[i] = a[i] - b[i];  // 计算当前位的差值并存入c数组}// 去掉前导零while (c[lc] == 0 && lc > 1){lc--;  // 如果最高位是0，且lc > 1，则将lc减1}// 如果flag标志为1，说明s1 < s2，需要输出负号if (flag == 1){cout << '-';}// 输出结果，从最高位输出到最低位for (int i = lc; i > 0; i--){cout << c[i];}return 0;
}

下面代码用y总模板写的

#include<iostream>
#include<vector>
#include<string>using namespace std;// 大数减法函数，计算 C = A - B，前提条件是 A >= B
vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;  // 定义一个vector C，用于存储结果for (int i = 0, t = 0; i < A.size(); i++)  // 从A的最低位到最高位遍历，t表示借位{t = A[i] - t;  // 当前位A[i]减去上一次的借位tif (i < B.size()) t -= B[i];  // 如果当前位i在B范围内，则从t中再减去B[i]// 处理当前位的差值，并将结果存入C// (t + 10) % 10 确保结果在0到9之间，处理借位情况C.push_back((t + 10) % 10);  // 如果t小于0，说明借位发生，设置t为1表示向下一位借位// 否则t为0，不需要借位if (t < 0) t = 1;else t = 0;}// 去掉结果C中的前导零，如果C的长度大于1，且最后一位是0，则将其删除while (C.size() > 1 && C.back() == 0) C.pop_back();return C;  // 返回存储结果的vector C
}// 比较两个大数 A 和 B，如果 A >= B 返回 true，否则返回 false
bool cmp(const vector<int>& A, const vector<int>& B)
{if (A.size() != B.size()) return A.size() > B.size();  // 位数不同则直接比较位数for (int i = A.size() - 1; i >= 0; i--)  // 从高位到低位逐位比较{if (A[i] != B[i]) return A[i] > B[i];}return true;  // 如果每一位都相同，则 A == B
}int main()
{string s1, s2;cin >> s1 >> s2;// 将字符串 s1 和 s2 转换为数字存储在 A 和 B 中，倒序存储以便逐位计算vector<int> A(s1.size()), B(s2.size());for (int i = 0; i < s1.size(); i++){A[s1.size() - 1 - i] = s1[i] - '0';  // 倒序存储 s1 中的数字}for (int i = 0; i < s2.size(); i++){B[s2.size() - 1 - i] = s2[i] - '0';  // 倒序存储 s2 中的数字}bool isNegative = false;  // 记录最终结果是否为负数if (!cmp(A, B))  // 如果 A < B，则交换 A 和 B，确保 A >= B{swap(A, B);isNegative = true;  // 结果是负数}// 调用大数减法函数vector<int> C = sub(A, B);// 输出结果，去掉前导零if (isNegative) cout << '-';  // 如果结果是负数，输出负号for (int i = C.size() - 1; i >= 0; i--){cout << C[i];}cout << endl;return 0;
}

高精度减法模板

// 计算C = A - B，其中A >= B，且A和B都是非负整数
vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;  // 定义一个vector C，用于存储结果for (int i = 0, t = 0; i < A.size(); i++)  // 从A的最低位到最高位遍历，t表示借位{t = A[i] - t;  // 当前位A[i]减去上一次的借位tif (i < B.size()) t -= B[i];  // 如果当前位i在B范围内，则从t中再减去B[i]// 处理当前位的差值，并将结果存入C// (t + 10) % 10 确保结果在0到9之间，处理借位情况C.push_back((t + 10) % 10);  // 如果t小于0，说明借位发生，设置t为1表示向下一位借位// 否则t为0，不需要借位if (t < 0) t = 1;else t = 0;}// 去掉结果C中的前导零，如果C的长度大于1，且最后一位是0，则将其删除while (C.size() > 1 && C.back() == 0) C.pop_back();return C;  // 返回存储结果的vector C
}