大数运算（加、减、乘、除）

前言

由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。

比如bc命令是任意精度计算器语言，通常在Linux下当计算器使用，它就可以进行大数的运算。

对于这种大数的计算，编程语言提供的基本数值数据类型已经无法进行存储，此时可以将这些大数存储到字符串当中，然后实现基于字符串的加减乘除运算即可。

一、大数加法

1. 基本思想

将两个字符串中的数相加其实非常简单，就像我们小学时列竖式计算一样。我们会从两个数字的最低位开始进行计算，如果低位相加时有进位，则会将该进位记录下来，下一次将两个数高一位对应的数字相加时就会将该进位一同加上。

2. 代码实现

//大数加法
string AddString(string num1, string num2)
{
	int end1 = num1.size() - 1, end2 = num2.size() - 1;
	string ret; //存储两个字符串相加后的结果
	int carry = 0; //进位（初始时进位设置为0）
	while (end1 >= 0 || end2 >= 0)
	{
		//1、取出num1中本次待相加的数字
		int a = 0;
		if (end1 >= 0)
		{
			a = num1[end1] - '0';
			end1--;
		}
		//2、取出num2中本次待相加的数字
		int b = 0;
		if (end2 >= 0)
		{
			b = num2[end2] - '0';
			end2--;
		}
		//3、将这两个数字相加（注意加上进位）
		int sum = a + b + carry;
		//4、判断是否需要进位
		if (sum > 9)
		{
			sum -= 10;
			carry = 1; //需要进位，将carry设置为1
		}
		else
		{
			carry = 0; //不需要进位，将carry设置为0
		}
		ret += (sum + '0');
	}
	if (carry != 0) //判断是否还需进位（可能两个数的最高位相加后会进位）
		ret += '1';

	reverse(ret.begin(), ret.end()); //将ret字符串进行反转
	return ret; //返回两个字符串相加后的结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

代码说明：

• 在代码中，需要进位时直接将carry设置成了1，因为两个数相加后如果有进位，其进位就是1。
• 如果将两个数的对应位相加后没有产生进位，需要及时将carry的值重新设置为0，防止对下一次相加造成影响。
• 当对两个数中所有的位都进行相加操作后，最后还需要判断carry的值是否为1，如果carry的值为1，则还需要在结果中尾插一个1（这个1在进行字符串反转后也就是最高位的1）。
• 由于我们是从最低位开始进行对应位的相加的，因此我们每得到一个位的结果就需要将其头插到ret字符串中，而头插时需要将字符串中所有的字符向后移动一位，时间复杂度是$O(N)$。因此我们这里选择先尾插，当需要返回最终结果时再进行一次字符串反转即可。

二、大数减法

1. 基本思想

将两个字符串中的数相减也是非常简单的，和字符串相加类似。也是从两个数字的最低位开始进行计算，如果低位相减时有借位，则会将该借位记录下来，下一次将两个数高一位对应的数字相减时就会将该借位一同减去。

2. 代码实现

//大数比较
int Cmp(string& num1, string& num2)
{
	if ((num1.size() > num2.size()) || (num1.size() == num2.size() && num1 > num2))
		return 1; //num1大于num2，返回1
	else if ((num1.size() < num2.size()) || (num1.size() == num2.size() && num1 < num2)) 
		return -1; //num1小于num2，返回-1
	else
		return 0; //num1等于num2，返回0
}
//大数减法
string SubString(string num1, string num2)
{
	//保证num1大于等于num2
	if (Cmp(num1, num2) == -1)
	{
		return "-" + SubString(num2, num1); //num1小于num2，则返回num2-num1所得到的结果的负值
	}
	int end1 = num1.size() - 1, end2 = num2.size() - 1;
	string ret; //存储两个字符串相减后的结果
	int borrow = 0; //借位（初始时借位设置为0）
	while (end1 >= 0)
	{
		//1、取出num1中本次待相减的数字
		int a = num1[end1] - '0';
		end1--;
		//2、取出num2中本次待相减的数字
		int b = 0;
		if (end2 >= 0)
		{
			b = num2[end2] - '0';
			end2--;
		}
		//3、将这两个数字相减（注意减去借位）
		int differ = a - b - borrow;
		//4、判断是否需要进位
		if (differ < 0)
		{
			differ = 10 + differ;
			borrow = 1; //需要借位，将borrow设置为1
		}
		else
		{
			borrow = 0; //不需要借位，将borrow设置为0
		}
		ret += (differ + '0');
	}
	reverse(ret.begin(), ret.end()); //将ret字符串进行反转
	//过滤掉ret字符串前面的'0'
	size_t pos = ret.find_first_not_of('0');
	if (pos == string::npos) //ret中全部为'0'，则两个数相减后的结果为0
	{
		return "0";
	}
	return ret.substr(pos); //返回两个字符串相减后的结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

代码说明：

• 与字符串相加时类似，当需要借位时直接将borrow设置成了1，因为两个数相减时如果需要借位，也只需要借一次就够了。
• 如果将两个数的对应位相减时没有进行借位，对应也需要及时将borrow的值重新设置为0，防止对下一次相减造成影响。
• 当num1的值小于num2时，其相减后的结果是一个负值，该负值的绝对值与num2-num1的值是相同的，因此我们可以选择重新调用SubString函数，得到num2-num1的值后，在该结果前面加上一个负号即可。
• 由于我们保证了实际在进行相减操作时，num1的值是大于等于num2的值的，因此对两个数中所有的位都进行相减操作后，无需再判断borrow的值是否为1，此时borrow的值必然为0。
• 与字符串相加时一样，为了避免每次插入字符的时间复杂度都是$O(N)$，每次插入字符时也是进行的尾插，当需要返回最终结果时再进行一次字符串反转即可。

三、大数乘法

1. 基本思想

字符串相乘相对来说会难一点，但其原理还是和我们平时列竖式时是一样的。我们平时会将乘数的每一位与被乘数的每一位相乘，将相乘后的结果写到对应的位置，然后将这些乘积对应加起来就得到了两个数相乘后的结果。

实际我们在计算的过程中也可以先不进行进位，先将每位相乘后的乘积放到对应的位置，然后将对应位置的乘积加起来。

最后再对这个序列从低位到高位依次进行进位操作，最终也能够得到这两个数相乘后的结果。只不过我们平时列竖式计算时是时刻都在进行进位操作的，而我们现在统一将进位的过程放到了最后。

问题一：如果我们将这些乘积累加到vector当中，这个vector应该开辟多大的空间？

首先我们需要明确的是：如果被乘数num1的长度为m，乘数num2的长度为n，则它们乘积的长度为m+n-1或m+n。

证明如下：

• 若num1和num2都取最小值，则num1=10^m-1, num2=10^n-1，那么它们的乘积就为10^m+n-2，此时乘积的长度为m+n-1。
• 若num1和num2都取最大值，则num1=10^m-1, num2=10ⁿ-1，那么它们的乘积就为10^m+n-10^m-10ⁿ+1，该结果是小于10^m+n而大于10^m+n-1的，此时乘积的长度为m+n。

综上所述：长度分别为m和n的数相乘后，乘积的长度为m+n-1或m+n。

因此，如果我们要将这些乘积累加到vector当中，为了确保能够容纳得下这些乘积，这个vector的必须要能够存储m+n个元素。

问题二：乘数的每一位与被乘数的每一位相乘后的结果，到底应该累加到vector中的哪一个下标位置？

以图中的例子为例，这里的被乘数和乘数的长度都是3，因此vector的大小应该开辟为6，稍作观察可以看到，乘数的第i位与被乘数的第j位相乘后的乘积，应该累加到vector中下标为i+j+1的位置。

将vector从低位到高位进行进位操作后，最终vector当中存储的序列就是这两个数相乘后的结果，此时我们需要从vector的高位开始，将其一个个尾插到一个字符串中，最后返回的这个字符串即为字符串相乘后的字符串。

此时需要注意，两个数相乘后乘积的长度可能是m+n-1，因此vector中下标为0的位置可能未使用，所以在将vector当中的序列插入到字符串中时，需要先判断vector中下标为0的位置是否被使用，如果未被使用则从vector中下标为1的位置开始往后才算作有效序列。

2. 代码实现

//大数乘法
string MulString(string num1, string num2)
{
	if (num1 == "0" || num2 == "0") //两个操作数中有一个为0，则结果为0
		return "0";

	int m = num1.size(), n = num2.size();
	vector<int> arr(m + n, 0); //开辟数组arr的大小为m+n，并且全部初始化为0
	
	//1、取乘数的每一位与被乘数的每一位相乘，将结果累加到数组arr的对应下标位置
	for (int i = n - 1; i >= 0; i--) //取乘数的每一位
	{
		int a = num2[i] - '0';
		for (int j = m - 1; j >= 0; j--) //取被乘数的每一位
		{
			int b = num1[j] - '0';
			arr[i + j + 1] += a*b; //乘数第i位与被乘数第j位相乘后的结果累加到数组arr中下标为i+j+1的位置
		}
	}

	//2、从后往前对数组arr进行进位操作
	int end = m + n - 1;
	while (end > 0)
	{
		arr[end - 1] += arr[end] / 10; //进位的值加到前一个位置
		arr[end] %= 10; //进位后剩下的值存放到当前位
		end--; //处理下一位
	}

	//3、依次将数据尾插到字符串ret当中
	string ret; //存放两个字符串相乘后的结果
	int flag = 1; //默认有效值从数组arr当中下标为1的位置开始
	if (arr[0] != 0)
		flag = 0; //若数组arr当中下标为0的位置的值不为0，则有效值从第0位开始
	for (int i = flag; i < m + n; i++)
	{
		ret += (arr[i] + '0');
	}
	return ret; //返回两个字符串相乘后的结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

代码说明：

• 若传入的两个操作数当中其中有一个为0，则相乘后的结果就是0，因此直接返回"0"即可。
• 代码中定义vector时，将开辟的m+n个位置都先初始化为了0，因此最后在将vector当中的序列尾插到字符串时，可以通过判断vector中下标为0的位置是否为0，来得知该位置是否算作有效值。

四、大数除法

1. 基本思想

两个数相除的商值代表的是，被除数当中最多有多少个除数，而两个数相除的余数代表的是，被除数被分成一个个除数后剩下的不够再分出一个除数的值。比如$456÷123$，其中被除数456最多可以被分成3个123，此时分完后还剩下的87就不够再分出一个123了，因此$456÷123=3...87$。

当然，如果要求最终结果精确到小数点后的若干位，在余数不够一个除数的大小时，应该在余数后面补0，然后继续进行计算。

以结果当中的小数点为界限，可以将除法分为两个过程：

• 计算小数点前面的数。
• 计算小数点后面的数。

计算小数点前面的数

首先，如果被除数的位数小于除数的位数，那么结果中小数点前的值就是0了，计算后的余数就是被除数本身，该余数用于后续计算小数点后的值。但如果被除数的位数大于或等于除数的位数，那么此时就需要计算了。

回想我们平时列竖式计算时，如果除数的位数len小于被除数的位数，那么我们刚开始时是先只看被除数的前len位的，将被除数的前len位与除数进行除法运算得到一个商值，当余数不够时再将被除数后面的位补到余数后面，然后继续进行除法运算。

因此当两个数相除时，如果除数的位数len小于被除数的位数，那么我们应该先用被除数的前len位进行判断，此时被除数的前len位最多可以被分成几个除数，则说明应该商几，当余数不够时再将被除数后面的位依次添加到余数后面继续进行计算，直到被除数的所有位都被用完，此时得到的商序列就是小数点前的值，而最终剩下的余数就用于后续计算小数点后的值。

当我们要判断一个数a最多可以被分成多少个b时，实际上非常简单，我们只需要判断当前a的值是否大于等于b，如果是，则可以在a的基础上减去b，然后继续该判断。最终a最多可以被分成多少个b，也就却决于a执行多少次减b操作后是小于b的。因此字符串相除可以被转换成字符串相减。

按照上述方法得到小数点前的结果后，需要判断所得字符串的最高位是否为0，如果为0并且0的后面不是小数点，则需要将这个0过滤掉，比如$200÷30=06.66$，此时我们需要将前面的0过滤掉。但如果字符串的最高位为0，但是0后面是小数点，那么这个0不能被过滤，比如$1÷3=0.33$，此时的0不能被过滤。

计算小数点后面的数

计算小数点后面的数的方法与计算小数点前面的数的方法类似，只不过此时我们在余数后面补的就不是被除数后面的位了，而直接是0，补0后再继续进行计算。

但实际有些数相除永远除不尽，因此这里我们可以给函数设置一个参数n，表示要求计算结果保留到小数点后的第n位，此时我们就将补n次0后最终得到的值进行返回即可。

2. 代码实现

//大数除法
string DivString(string num1, string num2, int n)
{
	if (num2 == "0") //除数不能为0
		return "error";
	string ret; //存储两个字符串相除后的结果
	string tmp; //余数

	//1、先计算小数点前面的数
	if (num1.size() < num2.size()) //num1的位数小于num2
	{
		ret += "0."; //商为0
		tmp = num1; //余数为num1
	}
	else //num1的位数大于等于num2
	{
		size_t len = num2.size(); //除数的长度
		tmp = num1.substr(0, len); //先取出被除数的高len位
		while (1)
		{
			//a、计算tmp当中最多有多少个num2（tmp除以num2的商）
			int count = 0;
			while (Cmp(tmp, num2) != -1) //tmp大于等于num2，则说明商可以更大
			{
				tmp = SubString(tmp, num2);
				count++; 
			}

			//b、将商值尾插到ret当中
			ret += (count + '0');

			//c、如果num1的所有位都被取完了，则小数点之前的结果计算完毕
			if (len >= num1.size())
				break;

			//d、如果num1当中还有未取的位，则继续从num1中一位尾插到tmp当中
			tmp += num1[len];
			len++; //下一次待取位下标
		}
		ret += "."; //小数点之前的结果计算完毕，加上小数点

		//如果ret最高位为0，且该位后面不是小数点，则需要将这个0过滤掉
		if (ret.size() != 2 && ret[0] == '0')
			ret = ret.substr(1);
	}

	//2、再计算小数点后面的数（保留n位小数）
	for (int i = 0; i < n; i++)
	{
		if (tmp == "0") //tmp为0（余数为0）
		{
			ret += "0"; //则直接在ret后面补0即可
		}
		else //tmp不为0（余数不为0）
		{
			tmp += "0"; //在余数后面补0，继续进行计算

			//a、计算tmp当中最多有多少个num2（tmp除以num2的商）
			int count = 0;
			while (Cmp(tmp, num2) != -1)
			{
				tmp = SubString(tmp, num2);
				count++;
			}

			//b、将商值尾插到ret当中
			ret += (count + '0');
		}
	}
	return ret; //返回两个字符串相除后的结果
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

代码说明：

• 两个数相除时要求除数不能为0，如果除数为0则可以做出相应的处理，代码中当除数为0时返回"error"字符串以示错误。