高精度运算——高精度正整数的存储

通过前面章节的学习，我们已经知道C/C++中存储整数一般使用 int 类型，如果要存储更大的整数，可以使用long long类型。如果要存储更大的整数，还可以尝试使用float或者double浮点数，但这样做精度会受到影响。如果处理的整数特别大，例如位数成百上千，这个时候用基本的数据类型已经无法处理了。这个时候可以用数组来模拟位数非常大的整数（也称为高精度整数），并且通过模拟数学四则运算的方法来实现高精度整数的四则运算（高精度运算）。注意，为了简化处理，本章介绍的高精度整数都是高精度非负整数。

注意：C++14支持__int128（两个下划线开始，CSP/NOIP支持），这是目前最大的整型，存储范围是\(2^{-127}～2^{127}-1\)，对应的还有无符号的 unsigned __int128 。__int128正常运算与普通int无异，但是输入输出时无论是cin、cout还是printf都会报错，所以必须自己实现输入（快读）输出（按位拆分+递归）。

首先来探讨如何使用数组存储高精度整数。输入时可以用字符串来存储高精度整数，为了提高计算效率，可以进一步将高精度整数每位上的数字存储到一个 int 数组中。具体如何存储，有两个选择：高精度整数的低位放到数组大下标（和书写保持一致）或者高精度整数的低位放到数组小下标（和书写正好逆序）？如何选择可以先考虑哪种方案对于后续要实现的高精度运算更方便。我们先看数学的竖式加法运算：

竖式加法就是将两个整数每一位做加法并处理进位。可以看出，必须从低位到高位依次按位相加并处理进位，进位整数的位数会发生变化，减法和乘法也存在这样的情况。由此可知，为了方便后续高精度运算的实现，将高精度整数按位存储到int数组a中，应该将高精度整数的低位存储到数组a的小下标中。此外还有一个技巧，可以将高精度整数的位数存储到a[0]中。

可以使用一个函数来实现由字符串高精度整数生成遵循上述规则存储高精度整数的int数组：

/* 高精度正整数字符串（char数组）格式化存储到数组
** arr[0]保存数字位数
** arr[1],arr[2],...,arr[arr[0]]从低位到高位依次存储高精度整数 
**/
void convert(char s[],int arr[]){ 
	memset(arr,0,N*sizeof(int));		//数组arr全部元素初始化为0 
	for(int i=strlen(s)-1;i>=0;i--){
		arr[0]++;
		arr[arr[0]] = s[i]-'0';
	}
}

/* 高精度正整数字符串（string）格式化存储到数组
** arr[0]保存数字位数
** arr[1],arr[2],...,arr[arr[0]]从低位到高位依次存储高精度整数 
**/
void convert(string s,int arr[]){ 
	memset(arr,0,N*sizeof(int));		//数组arr全部元素初始化为0 
	for(int i=s.length()-1;i>=0;i--){
		arr[0]++;
		arr[arr[0]] = s[i]-'0';
	}
}

还可以使用一个函数来输出存储在int数组中的高精度整数：

/* 输出存储在数组中的高精度整数 
**/ 
void print(int arr[]){
	for(int i=arr[0];i>=1;i--) printf("%d",arr[i]);
}

完整的测试程序如下：

#include<cstdio>
#include<cstring>
#define N 10010
char s1[N],s2[N];
int a[N],b[N];

/***********************************************************************
** 函数申明
***********************************************************************/
void convert(char s[],int arr[]);		//高精度整数字符串格式化存储到数组 
void print(int arr[]);				   //输出存储在数组中的高精度整数
/**********************************************************************/
//函数申明结束


/* 高精度正整数字符串格式化存储到数组
** arr[0]保存数字位数
** arr[1],arr[2],...,arr[arr[0]]从低位到高位依次存储高精度整数 
**/
void convert(char s[],int arr[]){ 
	memset(arr,0,N*sizeof(int));	//数组arr全部元素初始化为0，也可以用memset(arr,0,(arr[0]+1)*sizeof(int));

	for(int i=strlen(s)-1;i>=0;i--){
		arr[0]++;
		arr[arr[0]] = s[i]-'0';
	}
}

/* 输出存储在数组中的高精度整数 
**/ 
void print(int arr[]){
	for(int i=arr[0];i>=1;i--) printf("%d",arr[i]);
}

int main()
{
	//将高精度正整数按照字符串的方式输入存储 
	scanf("%s%s",s1,s2);
	
	//遵循存储规则，得到存储高精度正整数的数组 
	convert(s1,a);
	convert(s2,b);
	
	printf("输入的第1个高精度正整数是：\n");
	print(a);
	
	printf("\n\n");
	
	printf("输入的第2个高精度正整数是：\n");
	print(b);
	return 0;
}