大整数运算（高精度运算）C/C++

前言

这种类型，在做题过程中多为观察所给数据可能造成的大小来选择是否使用。

属于模板类型，学习者理解其格式并记住大致框架即可熟练应用。

---

一、什么是大整数（高精度）

想知道什么是大整数，不如换一个解释的方法：什么时候需要用到大整数？

众所周知，int类型的范围是-2147483648~2147483647。long long类型的范围是 -2^63 ~ (2^63)-1。那当题目需要用到或需要输出比long long类型的范围还要大的数字时，我们是不是就不能用常规办法去接收这些数字了。这个时候使用大整数就可以解决上述问题。即解决接收超出long long范围数字的问题。

二、大整数的存储

原理很简单，使用数组。

例如定义Int类型数组d[1000]，那么这个数组中的每一位就代表存放整数的每一位。比如将数字123456存储，则有d[0] = 6,d[1] = 5,d[2] = 4,d[3] = 3,d[4] = 2,d[5] = 1。整数的高位存在数组的高位，整数的低位存储在数组的低位。（为了契合加减乘除的思维）

这时候会产生一个需要注意的问题：把整数通过%s或者itoa的方式变成字符串的时候，一开始是逆位存储的，即d[0] = 1...，因此读入的之后需要在另存为至d[i]数组的时候反转一下。

为了方便随时获取大整数的长度，一般定义len来记录长度，并与d数组组合成结构体。

struct bign{
    int d[1000];
    int len;
};

bign是big number的缩写。

一般输入大整数时，都是先用字符串读入，然后再把字符串另存为至bign结构体。由于使用char数组进行读入时，整数高位会变成数组地位，整数的地位会变成数组的高位。因此为了让整数在bign中是顺位存储，需要让字符串倒着赋值给d[]数组。

bign change(char str[])//将整数转换为bign 
{
	bign a;
	a.len = strlen(str);//bign的长度就是字符串的长度
	for(int i = 0; i < a.len; i++)
	{
		a.d[i] = str[a.len-i-1] - '0';
	}
	return a;
}

 如果要比较两个bign变量的大小，也很简单：先判断len大小，若不相等，长的为大，若相等，则从高位至低位逐个比较，直到某一位不等，则可以判断两者大小。

int compare(bign a,bign b)
{
	if(a.len > b.len) return 1;//a大 
	else if(a.len < b.len) return -1;//a小 
	else
	{
		for(int i = a.len - 1; i >= 0; i--)//从高位到低位开始比较 
		{
			if(a.d[i] > b.d[i]) return 1;//只要有一位a大，则a大 
			else if(a.d[i] < b.d[i]) return -1;//只要有一位a小，则a小 
		}
		return 0;//两位相等 
	} 
}

最后如果需要输出bign变量的值，遍历一遍就可以实现了。 

void print(bign a) 
{
	for(int i = a.len - 1; i >= 0; i--) 
    {
		printf("%d",a.d[i]);
	}
	printf("\n"); 
}

三、大整数的四则运算

1、高精度加法

加法实现方式与我们以前学到的加法一样。对于某一位的运算：我们将该位上的两个数字与进位相加，得到的结果取个位数作为该结果，十位数作为新的进位。

bign add(bign a,bign b) 
{
	bign c;
	int carry = 0;	//carry是进位
	for(int i = 0; i < a.len || i < b.len; i++) //以较长的为界限 
    {		
		int temp = a.d[i] + b.d[i] + carry;		//两个对应位与进位相加 
		c.d[c.len++] = temp%10;		//个位数为该位的结果 
		carry = temp/10;	//十位数为新的进位 
	}
	if(carry != 0) //如果最后进位不为0，则直接赋给结果的最高位  
    {
		c.d[c.len++] = carry;		
	}
	return c; 
}

这里有一点需要注意，这样写法的条件是两个对象都是非负整数。如果有一方是负的，可以在转换到数组这一步时去掉符号，再使用高精度减法；如果两个都是负的，都去掉负号后采用高精度加法，最后负号加回去即可。

2、 高精度减法

通过对减法步骤的拆分可以得到一个简练的步骤：对某一位，比较被减位和减位，如果不够减，则令被减位的高位减1，被减位加10再进行减法；如果够减，直接减。最后需要注意减法后高位可能有多余的0，要去除他们，但也要保证结果至少有一位数。

bign sub(bign a,bign b) //a - b
{
	bign c;
	for(int i = 0; i < a.len || i < b.len; i++) //以较长的为界限
    {		
		if(a.d[i] < b.d[i]) //不够减 
        {		
			a.d[i + 1]--;	//向高位借位 
			a.d[i] += 10; 	//向前位借10  
		}
		c.d[c.len++] = a.d[i] - b.d[i];		//减法结果为当前位 
	}
	while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) 
    {
		c.len--;	//去除高位的0，同时至少保留一位最低位 
	} 
	return c; 
}

最后需要指出，使用sub函数前要比较两个数的大小，如果被减数小于减数，需要交换两个变量，然后输出负号，再用sub函数。

3、高精度与低精度的乘法

这里所谓的低精度就是基本数据类型存储的数据，如int。这里就是bign与int的乘法。

对某一位来说是这样的步骤：取bign的某位与int型整体相乘，再与进位相加，所得结果的个位数作为该结果，高位部分作为新的进位。

bign multi(bign a,int b) 
{
	bign c;
	int carry = 0;	//进位
	for(int i = 0; i < a.len; i++) 
    {
		int temp = a.d[i] * b + carry;
		c.d[c.len++] = temp % 10;		//个位作为该结果
		carry = temp / 10;	//高位部分作为新的进位 
	} 
	
	while(carry != 0) //和加法不一样，乘法的进位可能不止一位，因此用while 
    {	
		c.d[c.len++] = carry % 10;
		carry /= 10;
	}	
	return c; 
}

另外，如果a和b中存在负数，需要先记录下负号，然后取他们的绝对值带入函数。

4、高精度与低精度的除法 

归纳其中一位的步骤：上一步的余数乘以10加上该步的位，得到该步临时的被除数，将其与除数比较；如果不够除，则该位的商为0；如果够除，则商即为对应的商，余数即为对应的余数。最后一步要注意减法后高位可能有多余的0，要去除他们，但也要保证结果至少有一位数。

bign divide(bign a,int b,int& r) //r为余数 
{	
	bign c;
	c.len = a.len;//被除数的每一位和商的每一位是一一对应的，因此先令长度相等 
	for(int i = a.len - 1; i >= 0; i--)  //从高位开始 
    {	 
		r = r * 10 + a.d[i];		//和上一位遗留的余数组合
		if(r < b) c.d[i] = 0;		//不够除，该位为0 
        else //够除 
        {		
			c.d[i] = r / b;	//商
			r = r % b;		//获得新的余数 
		}
	}
	while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) 
    {	
		c.len--; //去除高位的0，同时至少保留一位最低位 
	}
	return c; 
}

考虑到很多题目会要求得到余数，因此把余数写成引用的形式直接作为参数传入，或者也可以把余数设成全局变量。