高精度算法：突破整型限制的算法实现【C++实现】

大数计算，如计算 11112345678901234567890 和 111198765432109876543210的运算；竞赛场景，如 CCF CSP、NOI、ACM 等常考题型；科学/金融/密码学计算，需处理任意长度的大整数。常规整型变量无法满足精度需求，因此我们需要模拟竖式运算的过程，通过字符串或数组逐位计算来实现。

2301_81831423

5217人浏览 · 2025-08-06 10:02:23

2301_81831423 · 2025-08-06 10:02:23 发布

思考2：我们为什么要存储数字而不是存储字符？

4.2高精度减法

4.3高精度乘法

4.4高精度除法

思考1：为什么需要数组t?为什么这里需要把b拷贝给t而不是直接使用b？

思考2：为什么这里需要进行传值引用？

📌 小结对比

在日常编程中，我们使用的 int、long、long long 类型都有固定的取值范围，例如 int 在大多数平台中最大为 2^31-1，即约 21 亿。当我们处理非常大的整数（比如上百位甚至上千位）时，这些类型就"力不从心"了。高精度计算因此应运而生。

本文将带你了解 高精度算法 的背景、原理，并以 C++ 实现为例，展示完整的代码与讲解。

一、背景介绍

高精度算法主要用于解决如下问题场景：

大数计算，如计算 11112345678901234567890 和 111198765432109876543210的运算；
竞赛场景，如 CCF CSP、NOI、ACM 等常考题型；
科学/金融/密码学计算，需处理任意长度的大整数。

常规整型变量无法满足精度需求，因此我们需要模拟竖式运算的过程，通过字符串或数组逐位计算来实现。

二、算法分类

高精度算法主要分为以下几类：

1. 高精度加法

原理：模拟小学竖式加法，从个位开始逐位相加，处理进位问题。

核心思想：

将两个大数倒序存储在数组中（个位在数组开头）
从低位到高位逐位相加
每位相加后如果 ≥ 10，就向高位进位

时间复杂度：O(max(len1, len2))

2. 高精度减法

原理：模拟小学竖式减法，从个位开始逐位相减，处理借位问题。

核心思想：

确保被减数 ≥ 减数（处理符号问题）
从低位到高位逐位相减
如果当前位不够减，从高位借1

时间复杂度：O(max(len1, len2))

3. 高精度乘法

原理：模拟小学竖式乘法，每一位都要与另一个数的每一位相乘。

核心思想：

第i位与第j位相乘的结果应该加到第(i+j)位上
处理进位，确保每位都是0-9的单数字

时间复杂度：O(len1 × len2)

4. 高精度除法

原理：模拟长除法过程，从高位开始试商。

核心思想：

从被除数的最高位开始，逐位确定商
用减法模拟除法过程
处理余数

时间复杂度：O(len1 × len2)

三、实现思路

3.1 高精度加、减、乘法思路

✅ 输入两个字符串表示的大整数 s1 和 s2
从用户输入中读取两个可能非常大的整数（超过 long long 范围），以字符串形式存储，避免精度丢失。

✅ 将它们倒序存入数组 a[]、b[]
为了模拟手算，从个位开始逐位操作，将字符串从右往左转换为整型数组，便于按位计算。

✅ 模拟运算过程，将结果存入 c[]
逐位执行加法、减法或乘法操作，根据每位的计算结果更新 c[] 数组。

✅ 注意进位/借位处理

加法：若当前位之和 ≥10，需进位
减法：若当前位不足以减去对应位，需向更高位借位
乘法：按位相乘后累加到结果数组中，同时注意进位

✅ 输出最终结果（倒序输出）
结果数组中从低位到高位存储，输出时需从高位到低位，且去除前导 0。

3.2 高精度除法思路

⚠️ 高精度除法与加减乘法不同，从高位到低位逐位模拟。

高精度除法与加减乘法的本质区别

在高精度算法中，加、减、乘法通常遵循**“从低位到高位”**的处理顺序，原因在于：

加法与乘法可能在当前位数产生进位，需要影响更高位；

减法可能在当前位不足时需要从更高位借位；

所以，计算从低位向高位是自然且必要的。

而高精度除法则反其道而行之：

高精度除法的思路更类似于我们日常手算的“长除法”；

它是从高位到低位逐步构造当前“被除数段”，然后尝试整除；

若当前位不足整除（即“够除”），则需要补位（即补 0）继续向低位借数，而不是向高位借；

换言之，除法是一个向右补齐的过程，不是向左传递影响。

✅ 输入：一个大整数 s1（被除数），一个整数 b（除数）

s1 用字符串存储，b 用整型（假设不超过 int）

✅ 初始化余数变量 r = 0，准备结果数组 c[]

使用整型变量 r 维护当前余数

使用 c[] 存储每一位的商

✅ 从高位到低位遍历 s1 的每一位字符

for i in 0 to len(s1)-1:
    r = r * 10 + s1[i] - '0'  // 模拟进位形成新数
    c[i] = r / b              // 当前位的商
    r = r % b                 // 更新余数

每一轮相当于手算除法中的“试商取整”

✅ 处理前导 0（商）

跳过商中的前导 0，仅输出有效位

✅ 输出商和余数

商存储在数组 c[]

余数为最终保留的 r

四、完整代码与注释

4.1高精度加法

#include<iostream>
using namespace std;
//高精度加法

//高精度加法本质是对竖式相加的模拟
//因为高精度一般位数有很多所以会采用string来进行输入
const int N=1e5+10;
int a[N],b[N],c[N];//a,b存储要相加的两个数，c里面存储结果
int la,lb,lc;//a,b,c数组中的有效位数 
int main()
{
	string s1,s2;//数
	cin>>s1>>s2;
    //思考1：我们为什么要进行逆序存储？
    //思考2：我们为什么要存储数字？
	for(int i=s1.size()-1;i>=0;i--)	a[la++]=(s1[i]-'0');
	for(int i=s2.size()-1;i>=0;i--) b[lb++]=(s2[i]-'0');
	lc=max(la,lb);
	//两数相加
	for(int i=0;i<lc;i++)
	{
        //这里是+=，原因是可能有来自低位的进位
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]%=10;	
	} 
	if(c[lc]>0) lc++;
	
	for(int i=lc-1;i>=0;i--)
	{
		cout<<c[i];
	}
	cout<<endl;
}

思考1：我们为什么要进行逆序存储？

        1. 更容易从低位开始模拟人工运算

大整数的加减乘除都从低位开始运算（跟我们手工算数一样），逆序后：

最低位变成了数组下标 0 的元素。

可以直接从 a[0] 开始操作，无需倒着遍历，提高代码效率与可读性。

        2. 简化进位 / 借位逻辑

高精度加减乘常常涉及进位或借位，逆序处理时：

进位/借位都往更高的数组下标走（如 i+1），这在数组中处理非常自然。

正序存储则需要倒着处理，容易出错，代码也更复杂。

        3. 更容易处理高精度乘法

在模拟乘法（如竖式乘法）时，逆序让我们能够直接按位累加：
for (int i = 0; i < la; i++) 
    for (int j = 0; j < lb; j++)
        c[i + j] += a[i] * b[j];
然后统一处理进位，结构清晰，效率高

思考2：我们为什么要存储数字而不是存储字符？

1. 数字可以直接参与计算
如果你将每一位存为整数（int 类型），你就可以直接执行：
c[i] = a[i] + b[i];
如果你将它们作为字符（char），你就必须先转换：
c[i] = (a[i] - '0') + (b[i] - '0'); // 需要减去 '0'，再计算
✔️ 使用数字 → 运算直接、快速、简洁
❌ 使用字符 → 每次运算都要转换、易出错

2. 更节省空间（与更高效）

char 是一个 1 字节的类型，存字符数字 '0'~'9' 本质还是 ASCII 编码（如 '0' 是 48）。

int 或 short 存的是实际数字 0~9，在实际中更接近机器计算。

虽然 char 占用空间小，但：

在高精度中我们只需要存 0~9，不会大量浪费。

如果确实需要节省空间，还可以用 unsigned char 或手动打包多个数字。

3. 字符容易引入错误
如果你忘记将字符 '5' 转换为数字，就会得到奇怪的结果：
char a = '5'; cout << a + 1; // 输出的是 '6' 的 ASCII 值（54）
而使用数字就不会有这个问题。

4.2高精度减法

#include<iostream>
using namespace std;
//高精度减法 

//高精度减法本质是对竖式相减的模拟
//因为高精度一般位数有很多所以会采用string来存储
const int N=1e5+10;
int a[N],b[N],c[N];//a,b存储要相加的两个数，c里面存储结果
int la,lb,lc;//a,b,c数组中的有效位数 
int main()
{
	string s1,s2;//数
	cin>>s1>>s2;
	if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2))
	{
		cout<<"-";//提前输出减号
		swap(s1,s2);	
	}
	for(int i=s1.size()-1;i>=0;i--)	a[la++]=(s1[i]-'0');
	for(int i=s2.size()-1;i>=0;i--) b[lb++]=(s2[i]-'0');
	lc=la;//此时的la一定最大
	for(int i=0;i<lc;i++)
	{
		c[i]+=a[i]-b[i];//处理低位因为不足借1问题
		if(c[i]<0) 
		{
			c[i]+=10;
			c[i+1]--;
		}	
	}
	while(lc>1&&c[lc-1]==0)//当只有1位数字且是0的情况下应保证正常输出 
	{
		lc--;//处理前导0问题 
	}
	for(int i=lc-1;i>=0;i--)
	{
		cout<<c[i];	
	} 
}

注意：处理前导0时，应保证输出的位数至少是1，避免出现0不输出情况

4.3高精度乘法

#include<iostream>
using namespace std;
//高精度乘法 

//高精度减法本质是对竖式相乘的模拟
//因为高精度一般位数有很多所以会采用string来存储
const int N=1e5+10;
int a[N],b[N],c[N];//a,b存储要相加的两个数，c里面存储结果
int la,lb,lc;//a,b,c数组中的有效位数 
int main()
{
	string s1,s2;//数
	cin>>s1>>s2;
	if(s1=="0"||s2=="0")
	{
		cout<<0<<endl;
		return 0;
	}
	for(int i=s1.size()-1;i>=0;i--)	a[la++]=(s1[i]-'0');
	for(int i=s2.size()-1;i>=0;i--) b[lb++]=(s2[i]-'0');
	lc=la+lb-1;
	for(int i=0;i<la;i++)
	{
		for(int j=0;j<lb;j++)
		{
			c[i+j]+=a[i]*b[j];//注意处理进位，同时c的位置等于a+b的位置
			c[i+j+1]+=c[i+j]/10;//最需要注意点：这里的进位并不是只有一次 
			c[i+j]%=10;	
		} 
	} 
	while(c[lc]>0) lc++;//处理最高位进位问题 
	for(int i=lc-1;i>=0;i--)
	{
		cout<<c[i];
	} 
}

注意：乘法的每次相乘后的结果都需要进位，所以进位需要累加

4.4高精度除法

#include<iostream>
#include<cstring>  // 用于memset函数
using namespace std;
//高精度除法 

//因为高精度一般位数有很多所以会采用string来存储
const int N=1e5+10;
int a[N],b[N],c[N],t[N];// 
int la,lb,lc,lt;//a,b,c数组中的有效位数 
//思考2：为什么这里需要进行传值引用？ 
void cpy(int x[],int y[],int offerset,int lx,int& ly)
{
	for(int i=0;i<lx;i++)
	{
		y[i+offerset]=x[i];	
	}	
	ly=lx+offerset;
} 
 
bool cmp(int x[],int y[],int n,int m)
{
	if(n<m)	return false;
	if(n>m) return true;
	if(n==m)
	{
		for(int i=0;i<n;i++)//因为存储是从高位到低位所以i从0开始 
		{
			if(x[i]==y[i]) continue;
			else return x[i]>y[i]; 
		}
	}
	return true;
}
void sub(int x[],int y[],int n,int offsert)
{

    //for(int i=n-1;i>=0;i--)//这里两种方案是为了更好的区分边界情况
	for(int i=n-1;i>=n-1-offsert;i--)
	{
		x[i]-=y[i];
		if(x[i]<0)
		{
			x[i]+=10;
			x[i-1]--; 
		}
	}
}
int main()
{
	string s1,s2;//数
	cin>>s1>>s2;
	if(s2=="0")
	{
		cout<<"/0error"<<endl;
		return 1;	
	} 
	//判断s1和s2的大小，如果s1比s2小的话，没有计算的必要
	if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2))
	{
		cout<<"0"<<endl;//商0，此时s1里面存放的就是余数
		return 0;//没有必要继续执行 
	} 
	for(int i=0;i<s1.size();i++)	a[la++]=(s1[i]-'0');//从高位到低位进行存储 
	for(int i=0;i<s2.size();i++) 	b[lb++]=(s2[i]-'0');
	// 用来减法来模拟大数除法
	lc=la-lb+1;//lc的有效位数
	for(int i=0;i<lc;i++)
	{
		memset(t,0,sizeof(t));
		//思考1：为什么这里需要把b拷贝给t而不是直接使用b？ 
		cpy(b,t,i,lb,lt); 
		la=lt;	
		while(cmp(a,t,la,lt))
		{
			sub(a,t,lt,lb);
			c[i]++;
		} 
	} 
	bool zero=false;
	for(int i=0;i<lc;i++)
	{
		if(zero||c[i])
		{
			cout<<c[i]; 
			zero=true;
		}
	}
    //此时数组a里面存放的就是余数
}

思考1：为什么需要数组t?为什么这里需要把b拷贝给t而不是直接使用b？

偏移操作的需要：

长除法需要将除数与被除数的不同位对齐

通过cpy(b,t,i,lb,lt)实现了将b数组拷贝到t数组的第i位开始

这相当于将除数左移i位的效果

如果直接使用b数组，无法实现这种偏移对齐

保护原始数据：

b数组存储的是原始除数，在整个除法过程中需要保持不变

在多次迭代中都需要使用相同的除数b

如果直接在b上操作，会破坏原始数据

内存布局的控制：

t数组通过memset(t,0,i*4)先清零前i位

然后将b的内容拷贝到从位置i开始的位置

这样t数组就表示了"左移i位的除数"

直接使用b数组无法实现这种精确的内存布局控制

算法逻辑的清晰性：

t数组明确表示"当前试商时使用的除数"

与被除数a进行比较和减法操作时，逻辑更清晰

避免了在原始数据上的复杂操作

思考2：为什么这里需要进行传值引用？

修改调用者的变量：函数需要修改lt的值，让调用者知道t数组的新的有效位数

保证代码可复用性：如果不用引用，调用者就需要手动计算并更新lt的值，代码就不够简洁和可复用

数据一致性：确保lt始终反映t数组的真实有效位数

注：这里的a,b,c都是s字符串的正序存储和加减乘法不同

📌 小结对比

运算	遍历方向	难点	说明
加法	从低到高	进位处理	对应每一位相加
减法	从低到高	借位处理	保证非负结果或做负数处理
乘法	从低到高	进位、位置	两重循环计算每一位
除法	从高到低	商判断	高精度减法模拟除法