超大数字的四则运算是如何实现的呢？
By Long Luo
众所周知，计算机系统从 \(16\) 位发展到 \(32\) 位，再从 \(32\) 位发展到 \(64\) 位，与此同时不同的数据类型也随着系统的位数增大而增大。早期的操作系统是 \(16\) 位系统，int用2字节表示，范围是-32768~32767，long用4字节表示，范围是-2147483648~2147483647；后来发展到 \(32\) 位操作系统，int用4字节表示，与long相同。
目前的操作系统已发展到 \(64\) 位操作系统，但因程序编译工艺的不同，两者表现出不同的差别：
- \(32\) 位编译系统：int占四字节，与long相同。
- \(64\) 位编译系统：int占四字节，long占8字节，long数据范围变为：\(-2^63~2^63-1\)
具体在标准中，并没有规定long一定要比int长，也没有规定short要比int短，只是规定了长整型至少和整型一样长，整型至少和短整型一样长。这个规则同样适用于浮点型long double至少和double一样长，double至少和float一样长。至于如何实现要看编译器厂商。
下表所展示的是Java的8种基本数据类型的详细数据：
| 基本类型 | 大小 | 最小值 | 最大值 | 包装器类型 | 默认值 |
|---|---|---|---|---|---|
| boolean | / | / | / | Boolean | false |
| char | 2 | Unicode 0 | Unicode 2^16-1 | Character | ‘u0000’ |
| byte | 1 | -128 | 127 | Byte | 0 |
| short | 2 | -2^15 | +2^15-1 | Short | 0 |
| int | 4 | -2^31 | +2^31-1 | Integer | 0 |
| long | 8 | -2^63 | +2^63-1 | Long | 0 |
| float | 4 | IEEE754 | IEEE754 | Float | 0 |
| double | 8 | IEEE754 | IEEE754 | Double | 0 |
从上述表格中可以看出，普通工作生活中所涉及的数字都不会超过int所能表示的范围，而超过long long类型则少之又少。但是具体到一些行业或者科研中，比如天文，石油开采等，经常需要和天文数字进行打交道。举例来说，\(50!\)，\(10^20\) 这种阶乘或者指数函数轻而易举就突破最大所能表示的范围。
如何表示这些超大数字以及对其进行数学运算呢？
大数字如何表示？
首先需要解决的问题就是如何表示，用数据类型是不可能了，那么我们应该怎么做呢？
很容易想到的就是将超大数字拆分为一个个位进行展示，存储这些位的值就可以了。至于怎么存，可以使用string, 也可以使用list, array等。这里为了方便，我们使用string来说明及展示。 例子：1
string number = "3377733333332222";
解决了展示问题，下面我们来展示如何对超大数字进行数学运算：
加法(Add)
让我们回到小学课堂，重温我们学习加法的第一课。回想我们是如何做加法的呢？1
2
3Input : str1 = "3333311111111111",
str2 = "44422222221111"
Output : 3377733333332222
很明显，我们是从低位开始，按位相加，直至最高位。
那么实现大数字的加法就可以很简单的分成3步： 1. 翻转每个string； 2. 从第 \(0\) 位开始依次相加到相对小的string，每位的数字是 \(sum mod 10\) ，如果有进位则进位为 \(sum / 10\)； 3. 对得到的结果进行翻转。
我们直接看实现吧：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
31string sum_of_large_number(string num1, string num2) {
if (num1.length() > num2.length()) {
swap(num1, num2);
}
int len1 = num1.length();
int len2 = num2.length();
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
string result = "";
int carry = 0;
for (int i = 0; i < len1; i++) {
int sum = (num1.at(i) - '0') + (num2.at(i) - '0') + carry;
result.push_back(sum % 10 + '0');
carry = sum / 10;
}
for (int i = len1; i < len2; i++) {
int sum = num2.at(i) - '0' + carry;
result.push_back(sum % 10 + '0');
carry = sum / 10;
}
if (carry) {
result.push_back(carry + '0');
}
reverse(result.begin(), result.end());
return result;
}
减法(Subtract)
对于减法来说，和加法类似，如下所示：1
2
3Input : str1 = "11443333311111111100",
str2 = "1144422222221111"
Output : 11442188888888889989
很明显，我们是从低位开始，按位相减，直至最高位。
那么实现大数字的减法就可以很简单的分成 \(3\) 步：
- 翻转每个string；
- 从第 \(0\) 位开始依次相减到相对小的string，如果相减 \(> 0\) 则不需要借位，如果 \(< 0\) 则需要借位，与借位 \(\times 10\) 再进行相减，同时借位需要 \(-1\)；
- 对得到的结果进行翻转。
我们直接看实现吧：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
72
73
74
75
76
77bool isSmaller(string str1, string str2) {
int len1 = str1.length();
int len2 = str2.length();
if (len2 < len1) {
return false;
}
if (len2 > len1) {
return true;
}
if (len1 == len2) {
for (int i = 0; i < len1; i++) {
if (str1[i] < str2[i]) {
return true;
} else if (str1[i] > str2[i]) {
return false;
}
}
}
return false;
}
string subtract_of_large_number(string num1, string num2) {
bool isNegative = false;
if (isSmaller(num1, num2)) {
isNegative = true;
swap(num1, num2);
}
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int len1 = num1.length();
int len2 = num2.length();
string result = "";
int carry = 0;
for (int i = 0; i < len2; i++) {
int sub = (num1[i] - '0') - (num2[i] - '0') - carry;
if (sub < 0) {
sub = sub + 10;
carry = 1;
} else {
carry = 0;
}
result.push_back(sub + '0');
}
for (int i = len2; i < len1; i++) {
int sub = (num1[i] - '0') - carry;
if (sub < 0) {
sub = sub + 10;
carry = 1;
} else {
carry = 0;
}
result.push_back(sub + '0');
}
// remove 0
int length = result.length();
while (result[length - 1] == '0' && length > 1) {
result.pop_back();
length--;
}
if (isNegative) {
result.push_back('-');
}
reverse(result.begin(), result.end());
return result;
}
乘法(Multiply)
对于乘法来说，乘法的原理如下所示：
那么如何做呢？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
48string multiply(string number1, string number2) {
int len1 = number1.length();
int len2 = number2.length();
if (len1 == 0 || len2 == 0) {
return "0";
}
vector<int> result(len1 + len2, 0);
int idx_num1 = 0;
int idx_num2 = 0;
for (int i = len1 - 1; i >= 0; i--) {
int carry = 0;
int n1 = number1.at(i) - '0';
idx_num2 = 0;
for (int j = len2 - 1; j >= 0; j--) {
int n2 = number2.at(j) - '0';
int sum = n1 * n2 + result[idx_num1 + idx_num2] + carry;
carry = sum / 10;
result[idx_num1 + idx_num2] = sum % 10;
idx_num2++;
}
if (carry > 0) {
result[idx_num1 + idx_num2] += carry;
}
idx_num1++;
}
int length = result.size() - 1;
while (length >= 0 && result[length] == 0) {
length--;
}
if (length == -1) {
return "0";
}
string output = "";
while (length >= 0) {
output += std::to_string(result[length--]);
}
return output;
}
除法(Division)
相对于加法，减法，乘法来说，除法相对来说最复杂，1
2
3Input : number = 1260257
divisor = 37
Output : 34061
目前我也只实现了除数可以使用int类型表示的算法。超大数字比如 \(90!/45!\) 这种难度和复杂度太大，暂时还没有实现。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20string findDivide(string num1, int divisor) {
string ans = "";
int idx = 0;
int temp = num1[idx] - '0';
while (temp < divisor) {
temp = temp * 10 + (num1[++idx] - '0');
}
while (num1.size() > idx) {
ans += temp / divisor + '0';
temp = (temp % divisor) * 10 + (num1[++idx] - '0');
}
if (ans.length() == 0) {
return "0";
}
return ans;
}
实践
通过上面，我们已经掌握了超大数字的四则运算方法，现在开始实践吧！
Leetcode上面有一些题目就是超大数字的四则运算如何实现，如下所示：
43. 字符串相乘 415. 字符串相加 445. 两数相加 II
总结
如上所示，我们就掌握了大数字的表示及简单数学运算的实现算法。