C语言——高精度加法

我们知道long long int类型的数据的最大数量级大概是10 ^ 18，这个数量级已经和大了是吧，但是实际上还有更大的数，例如10 ^ 100。

如果写一个加法程序，输入两个整数a、b，a、b的范围都在10 ^ 17内，那样可以选用long long int整型类型存储变量，如下：

#include <stdio.h>

int main()
{
	long long a = 0, b = 0;
	scanf("%lld %lld",&a,&b);
	long long res = a + b;
	printf("%lld",res);
	return 0;
}

那如果数据非常大，例如10 ^ 100 + 10 ^ 100 怎么计算呢，这里就需要高精度加法了，实际上高精度加法还要用到我们小学加法中的按位相加的操作，如下图

从最低位依次相加，逢十进一，较高一位加一。

这样我们的高精度加法就有一些逻辑了。

我们可以把这些大数存在数组中，以防止某个数据丢失，然后通过遍历的方式将两个数组的每一位进行相加操作，然后将得到的数据进行上面(逢十进一)的操作，最终把数据存到一个新数组中。

代码实现：

#include <stdio.h>
#include <string.h>

void DigitReverse(char arr[])//更换顺序，将输入的数字倒序，方便从最低位计算
{
	int length = (int)strlen(arr);//计算数字的长度
	for (int i = 0; i < length / 2; i++)//只用遍历数字长度的一半，即可将数字倒序
	{
		int temp = arr[i];
		arr[i] = arr[length - i - 1];
		arr[length - i - 1] = temp;
	}
}

void StringtanstoNumber(char arraych[],int arraynum[])//将字符数组转换成整型数组，方便后面按位计算
{
	int length = (int)strlen(arraych);
	for (int i = 0; i < length; i++)
	{
		arraynum[i] = arraych[i] - '0';//利用ASCII码的特，用每一个字符减去字符0，就可以实现字符数组向整型数组的转换
	}
}

void BigNumberAdd(char arraynum1[],char arraynum2[],int arraynum3[],int length)//arraynum3作为最终计算的和的存储数组
{
	DigitReverse(arraynum1);//将数组一倒序
	DigitReverse(arraynum2);//将数组二倒序

	int arrnum1[500] = {0};//创建两个整型数组用来存储字符数组转换成的整型数组
	int arrnum2[500] = {0};

	StringtanstoNumber(arraynum1,arrnum1);//将两个字符数组转换成整型数组
	StringtanstoNumber(arraynum2,arrnum2);

	int carry = 0;//carry作为进位变量，来存储进位数据，初始为0，代表第一位不用加进位，carry只会是0或1
	for (int i = 0; i < length + 1; i++)//length + 1的原因是如果数字最后一位进位了，数字长度就超过了length一位
	{
		arraynum3[i] = arrnum1[i] + arrnum2[i] + carry;//这里arraynum3 = (两个数字对应位的和) + (进位数字)
		carry = arraynum3[i] / 10;//这里的carry作为与(i + 1)位相加的进位数字，进位数字的值是i位的数字除以10
		arraynum3[i] = arraynum3[i] % 10;//arraynum3中的i位数字为相加的结果对10取模
	}
	if (carry > 0)//检查最后一位的进位是否是大于零的，如果是大于零的，就要再进一位，这时最终的和的数字长度大于了两个加数的长度，长度为length + 1
	{
		arraynum3[length] = carry;//将length + 1位赋值为进位数字
	}
}

void Print(int arr[],int length)//这里传来的参数length是两个加数中最长的加数的长度，而在经过相加运算后的结果可能会大于这个长度，最长只会是length + 1
{
	int i = length + 1;//假设是最长的情况
	//采用将数组倒序打印，可以减少将数组单独倒序的步骤
	//因为在前面我们假设是最长的情况，可能导致打印时会有前导0，这样不够简洁
	//所以我们利用下面的while循环来去掉前导0
	while (i > 0 && arr[i] == 0)//用来去除前导0，只要没遇到非零数就将这一位去除，也就是去除这一位前导0
	{ 
		i--;
	}
	for (; i >= 0; i--)//打印去掉前导0后的数字
	{
		printf("%d", arr[i]);
	}
}

int main()
{
	char ch1[505] = "0";
	char ch2[505] = "0";

	scanf("%s",ch1);
	scanf("%s",ch2);

	int length = (int)(strlen(ch1) > strlen(ch2) ? strlen(ch1) : strlen(ch2));//将最长的数的长度作为length，以便之后传参

	int SumNum[505] = {0};//创建一个整型数组用来存储相加结果

	BigNumberAdd(ch1,ch2,SumNum,length);//调用高精度运算函数，以及传参数

	Print(SumNum,length);//调用打印数组函数，以及传参
}