本文发布于 1678 天前，最后更新于 1600 天前，其中的信息可能已经有所发展或是发生改变。
日常怀念Python，自带高精永远的神！
高精度数字利用字符串表示
高精度数值计算实际上是一种特别的字符串处理。
「反转存储」
习惯上，下标最小的位置存放的是数字的 最低位，即存储反转的字符串。这么做的原因在于，数字的长度可能发生变化，但我们希望同样权值位始终保持对齐
同时，加、减、乘的运算一般都从个位开始进行
约定：定义一个常数 LEN = 1004 表示程序所容纳的最大长度
压位高精度
在位数较多的时候，拆分出的数也很多，高精度运算的效率就会下降。
注意到拆分数字的方式并不影响最终的结果，因此我们可以将若干个数码进行合并。
高精度读写
#include <bits/stdc++.h>
#define LEN 10086
using namespace std;
int a[LEN],b[LEN];
void clear(int a[])//清零函数，数字归零
{
for(int i=0; i<LEN; i++)
a[i]=0;
}
void read(int a[])
{
static char s[LEN+1];//静态 s 字符 组
scanf("%s",s);
clear(a);
//开始反转字符
int len = strlen(s);//计算字符串 str 的长度，直到空结束字符，但不包括空结束字符。
for(int i = 0; i < len; ++i)
{
a[len - i -1] = s[i] - '0'; // s[i] - '0' 就是 s[i] 所表示的数码
/* 也可能用 ord(s[i]) - ord('0') 的方式理解
Ord 的函数返回序数类型表达式的序数值。
例如，您可以通过这种方式检索字符的 Ascii 值
Ord('A') 返回 65
Ord('a') 返回 97
*/
}
}
void print(int a[])
{
int i;
for(i = LEN - 1; i >= 1; --i)//终止条件 i >= 1 而不是 i >= 0 是因为当整个数字等于 时仍希望输出一个字符 0。
{
if(a[i] != 0) break;
}
for(; i >= 0; --i) //从最高位开始向下寻找第一个非零位，从此处开始输出
putchar(a[i] + '0'); //用于将给定的字符输出到控制台
putchar('\n');
}
int main()
{
read(a);
print(a);
}
四则运算
加法
#include <bits/stdc++.h>
#define LEN 1000
using namespace std;
int a[LEN],b[LEN],c[LEN];
int main()
{
string A,B;
cin >> A >> B;
int len = max(A.length(),B.length());
for(int i = A.length()-1,j = 0; i>=0; i--,j++)//倒叙存储，0为个位
{
a[j] = A[i] - '0';//依据数字与字符0的差确定数字
}
for(int i = B.length()-1,j = 0; i>= 0; i--,j++)
{
b[j] = B[i] - '0';
}
for(int i = 0; i < len; i++)
{
c[i] += a[i] + b[i];
c[i+1] = c[i] / 10;//进位
// cout << i <<" "<< c[i+1];
c[i] %=10;//个位上的数字为该位的实际数字
}
if(c[len]) len++; //如果最后进位了，那么总位数加一
for(int i = len-1; i>=0; i--)
cout << c[i];
}
换了一种写法，充当了解扩展了
减法
#include <bits/stdc++.h>
#define LEN 100100
using namespace std;
int a[LEN],b[LEN],c[LEN];
int num=0;
bool pd_0 = false;
bool mmax(int a[],int b[])
{
while(--num)
{
if(a[num]>b[num])
{
return true;
}
if(a[num]<b[num])
{
return false;
}
}
}
int main()
{
string A,B;
cin >> A >> B;
int len = max(A.length(),B.length());
for(int i = A.length()-1,j = 0; i>=0; i--,j++)//倒叙存储，0为个位
{
a[j] = A[i] - '0';//依据数字与字符0的差确定数字
num++;
}
for(int i = B.length()-1,j = 0; i>= 0; i--,j++)
{
b[j] = B[i] - '0';
}
bool pd = mmax(a,b);
if(A.length()>B.length()||(A.length()==B.length()&&pd))
{
// cout << "menth 1";
for(int i = 0; i < len; i++)
{
c[i] += a[i] - b[i];
if(c[i]<0) c[i+1]--,c[i]+=10;
// cout << i <<" "<< c[i+1];
c[i] %=10;//个位上的数字为该位的实际数字
if(i!=len-1) c[i] = abs(c[i]);
}
// if(c[len]) len++; //如果最后进位了，那么总位数加一
}
else
{
// cout << "menth 2";
for(int i = 0; i < len; i++)
{
c[i] += b[i] - a[i];
if(c[i]<0) c[i+1]--,c[i]+=10;
// cout << i <<" "<< c[i+1];
c[i] %=10;//个位上的数字为该位的实际数字
}
//cout << '-';//走过程2 的数均为减数大于等于被减数的，本想直接输出‘-’，但忽略了两数相等情况
pd_0 = true;
// if(c[len]) len++; //如果最后进位了，那么总位数加一
}
bool pd_begin = false;
bool pd__0 = true;
for(int i = len-1; i>=0; i--)
{
if(c[i]||pd_begin)
{
if(pd_0&&pd__0)
{
cout << "-";
pd__0 = false;
}
cout << c[i];
pd_begin = true;
}
}
if(!pd_begin) cout << '0';
}
按照自己理解写的，虽然成功，但代码太乱了，多次运用了判断，稍等学习一下大佬思路
先放一下大佬的思路，稍后再看。高精度减法
OI-WIKI 高精样例加个人解析（未完待续，高精除法为补充）
#include <bits/stdc++.h>
#define LEN 1008611
using namespace std;
int a[LEN],b[LEN],c[LEN];
void clear(int a[])// 清零函数，数字归零
{
for(int i=0; i<LEN; i++)
a[i]=0;
}
void read(int a[])
{
static char s[LEN+1];// 静态 s 字符 组
scanf("%s",s);
clear(a);
// 开始反转字符
int len = strlen(s);// 计算字符串 str 的长度，直到空结束字符，但不包括空结束字符。
for(int i = 0; i < len; ++i)// [1]表示个位！
{
a[len - i -1] = s[i] - '0'; // s[i] - '0' 就是 s[i] 所表示的 数!
/* 也可能用 ord(s[i]) - ord('0') 的方式理解
Ord 的函数返回序数类型表达式的序数值。
例如，您可以通过这种方式检索字符的 Ascii 值
Ord('A') 返回 65
Ord('a') 返回 97
*/
}
}
void print(int a[])
{
int i;
for(i = LEN - 1; i >= 1; --i)// 终止条件 i >= 1 而不是 i >= 0 是因为当整个数字等于 时仍希望输出一个字符 0。
{
if(a[i] != 0) break;
}
for(; i >= 0; --i) // 从最高位开始向下寻找第一个非零位，从此处开始输出
putchar(a[i] + '0'); // 用于将给定的字符输出到控制台
putchar('\n');
}
void add(int a[],int b[],int c[])// 两个相加数组，一个输出数组
{
clear(c);
// 高精度实现中，一般令数组的最大长度 LEN 比可能的输入大一些
// 然后略去末尾的几次循环，这样一来可以省去不少边界情况的处理
// 因为实际输入不会超过 1000 位，故在此循环到 LEN - 1 = 1003 已经足够
for (int i = 0; i < LEN - 1; ++i) {
// 将相应位上的数码相加
c[i] += a[i] + b[i];
if (c[i] >= 10)// 加法进位
{
c[i + 1] += 1;
c[i] -= 10;
}
}
}
void sub(int a[],int b[],int c[])// 注！ 此代码仅能处理a>b情况！
{
clear(c);
for(int i = 0; i<LEN-1; ++i)
{
if(c[i]<0)// 减法借位
{
c[i+1]--;
c[i]+=10;
}
}
}
void mul_short(int a[],int b,int c[])//高精度与单精度的乘法
{
clear(c);
for(int i = 0; i<LEN-1; ++i)// 因为都是整形，所以可以直接相乘，用求余确定数，/10确定进位
{
c[i] = a[i] * b;
if (c[i] >= 10)// 处理进位
{
c[i + 1] += c[i] / 10;// c[i] / 10 即除法的商数成为进位的增量值
c[i] %= 10; // 而 c[i] % 10 即除法的余数成为在当前位留下的值
}
}
}
void mul(int a[],int b[],int c[])//高精乘法
/*
于是可以将 b 分解为它的所有数码，
其中每个数码都是单精度数，将它们分别与 a 相乘，
再向左移动到各自的位置上相加即得答案。
当然，最后也需要用与上例相同的方式处理进位。
*/
{
clear(c);
for(int i = 0; i<LEN-1; ++i)
{
/*
这里直接计算结果中的从低到高第 i 位，且一并处理了进位
第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
这样做的效果和直接进行上图的运算最后求和是一样的，只是更加简短的一种实现方式
*/
for(int j = 0; j<=i; ++j)
{
c[i] += a[j] * b[i-j];
}
if (c[i] >= 10)
{
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
}
}
/*
高精除法是个难点，所以多写一点笔记
高精度除法，就是竖竖式长除法！
竖式长除法实际上可以看作一个逐次减法的过程。
例 456 / 12
商数十位的计算可以这样理解：将 45 减去 3 次 12 后变得小于 12 ，不能再减，故此位为 3
为了减少冗余运算，将提前获取被除数长度 l1 ，除数长度 l2 ，从 l1-l2 开始运算
从高位到低位运算商，
这和手工计算时将第一次乘法的最高位与被除数最高位对齐的做法是一样的。（？？？暂未理解
参考程序实现了一个函数 greater_eq() 用于判断被除数以下标 last_dg 为最低位
是否可以再减去除数而保持非负。
此后对于商的每一位，不断调用 greater_eq()，
并在成立的时候用高精度减法从余数中减去除数，也即模拟了竖式除法的过程。
*/
// 被除数 a 以下标 last_dg 为最低位，是否可以再减去除数 b 而保持非负
// len 是除数 b 的长度，避免反复计算
inline bool greater_eq(int a[],int b[],int last_dg,int len)
{
if(a[last_dg + len] != 0) return true; // 有可能被除数剩余的部分比除数长，这个情况下最多多出 1 位，故如此判断即可
for(int i = len-1; i>=0; --i) // 从高位到低位，逐位比较
{
if(a[last_dg + i] > b[i]) return true;
if(a[last_dg + i] < b[i]) return false;
}
return true; // 相等的情形下也是可行的
}
void div(int a[],int b[],int c[],int d[])
{
clear(c);
clear(d);
int la,lb;
for(la = LEN - 1; la>0; --la)
if(a[la - 1] != 0) break;
for(lb =LEN - 1; lb>0; --lb)
if(b[lb-1] != 0) break;
if(lb == 0)// 除数不能为0
{
puts("> <");
return;
}
// c 是商
// d 是被除数剩余部分，算法结束后自然成余数
for(int i = 0; i >la; ++i) d[i] = a[i];
for(int i = la - lb; i >= 0; --i)
{
// 计算商的第一位
while(greater_eq(d,b,i,lb))// 判断是否可减
{
// 高精度减法
for(int j = 0; j <lb; ++j)
{
d[i + j] -=b[j];
if(d[i + j] < 0)
{
d[i + j + 1] -=1;
d[i + j] +=10;
}
}
// 使商的这一位增加 1
c[i] +=1;
// 返回循环开头，重新检查
}
}
}
int main()
{
read(a);
read(b);
add(a,b,c);
print(c);
}