在处理数据过程中，我们可能会遇到 int 类型或者 long long 类型都无法存储的大整数。有的语言如 python 和 java 已经有内建的大整数支持。然而，在没有内建大整数支持的语言中，我们需要自己实现大整数的存储以及运算。

实现大整数有十分多细节需要考虑，十分考验编程者的细心程度，因此本文篇幅也会比较长，如有错漏请指出。

本文介绍的是比较朴素简单的一种实现。用以完成这道最小公倍数的题目。

大整数的基础

大整数的存储

我们很自然可以想到，存储整数，需要存储它的正负、每一位的数字，以及这个数的长度。为此，我们定义 BigInt 结构如下：

1
2
3
4
5
struct BigInt{
	bool negative; // false 为正，true 为负
	int len;
	int nums[10000];
};

为了方便起见，我们直接规定最大存储位数为 10000 位，对于这道题目而言已经足够，日后可以改写为动态分配长度以满足不同需求。

大整数的读入

为了方便理解，我们规定 nums[0] 为整数的个位，nums[1] 为整数的百位，依此类推。

然而，在将数字作为字符串 s 读取时，s[0] 存储的是数字的最高位。所以，在读取后，我们需要将其进行倒序处理，同时，将数字长度也存储起来。函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct BigInt read() {
	struct BigInt a;
	memset(&a, 0, sizeof(a));
	
	char input[10001];
	scanf("%s", input);
	// 符号的处理
	int end = 0;
	if (input[0] == '-') {
		a.negative = true;
		end = 1;
	}
	
	if (input[0] == '+') {
		end = 1;
	}
	
	for(int i = strlen(input) - 1; i >= end ; i--){
		if (input[i] >= 48 && input[i] <= 57) // 过滤非数字
		a.nums[a.len++] = input[i] - 48;
	}
	
	return a;
}

大整数的输出

只需要输出负号（如有），然后从高位到低位输出数字即可。

1
2
3
4
5
6
void output(struct BigInt a) {
	if (a.negative) printf("-");
	for(int i = a.len - 1; i >= 0; i--){
		printf("%d", a.nums[i]);
	}
}

大整数的四则运算

大整数的加法

当我们实现读入并存储了大整数之后，就要开始实现加法了。

实现加法的过程实际上就是我们手动列竖式计算的过程：

$$ \begin{array}{ccc} & a_n & a_{n-1} & \cdots & a_1 \\ + & b_n & b_{n-1} & \cdots & b_1 \\ \hline =& a_n + b_n & a_{n-1} + b_{n-1} & \cdots & a_1 + b_1 \end{array} $$

上面的公式并没有考虑进位，而进位的处理并不复杂，进位的处理：

$$ c_{i+1} = \lfloor \frac{c_{i}} {10} \rfloor \tag{*} \\ c_i = c_i\ mod\ 10 $$

由于都是整形，在 C 语言中，(*)可以直接写除法而不必使用 floor 函数。

对于加法处理后的数字长度，最长不会超过 max(a.len, b.len) + 1 ，我们可以默认它就是这个数，然后在做完加法之后，从高位遍历到低位，找到第一个非零数，来确定真正的长度。

对于负数的处理，可以分为以下几种情况：

  1. 两个数一正一负
  2. 两个数同为负数

对于第一种情况，我们将其转换为两个正数的减法；对于第二种情况，我们直接做加法，然后将结果标记为负数即可。

参考代码如下：

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
struct BigInt add(struct BigInt a, struct BigInt b){
	struct BigInt c;
	memset(&c, 0, sizeof(c));
	
	if (a.negative ^ b.negative) // a, b 异号
		if (a.negative) {
			a.negative = false;
			return sub(b, a);
		}
		else {
			b.negative = false;
			return sub(a, b);
		}
	
	c.len = max(a.len, b.len) + 1;
	
	for(int i = 0; i < c.len; i++){
		c.nums[i] = a.nums[i] + b.nums[i];
	}
	
	for(int i = 0; i < c.len; i++){
		c.nums[i+1] = c.nums[i] / 10 + c.nums[i+1];
		c.nums[i] = c.nums[i] % 10;
	}
	
	while (c.nums[c.len] == 0 && c.len > 0){
		c.len--;
	}
	
	c.len++;
	c.negative = a.negative & b.negative;
	
	return c;
}

大整数的减法

在加法的实现中，我们调用了尚未实现的 sub 减法函数，下面我们就来实现 a - b。

位数方面，结果不会超过 max(a.len, b.len)，其余思想和加法类似。

计算的过程同样基于竖式计算：

$$ \begin{array}{ccc} & a_n & a_{n-1} & \cdots & a_1 \\ - & b_n & b_{n-1} & \cdots & b_1 \\ \hline =& a_n - b_n & a_{n-1} - b_{n-1} & \cdots & a_1 - b_1 \end{array} $$

不同的是，我们需要处理借位的情况。这时，我们从低位向高位处理，假如发现某位小于零，则向高位“借” 10。

$$ if\ c_i < 0 \\ c_{i+1} = c_{i+1} - 1 \\ c_{i} = c_{i} + 10 $$

同样，关于负数的处理，有下面几种情况：

  1. a 正 b 负
  2. a 负 b 正
  3. a 负 b 负

对于第一种以及第二种情况，我们可以将 b 的符号置反，然后调用加法实现；对于第三种情况，将其作为 (-b) - (-a) 处理即可。

通常为了编写程序方便，我们用绝对值较大的数减去绝对值较小的数，为此，我们编写一个比较两个数绝对值大小的函数。

大整数的绝对值比较

比较绝对值可以分为几个步骤：

  1. 比较长度，长度大的更大；
  2. 若长度相等，从高位依次比较到低位，若有不一致，即为比较结果；
  3. 若每一位都相等，则认为两个数绝对值相等。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define GREATER 1
#define LESS -1
#define EQUAL 0

int cmp(struct BigInt a, struct BigInt b){
	if(a.len > b.len) return GREATER;
	if(a.len < b.len) return LESS;
	
	if(a.len == b.len){
		for(int i = a.len - 1; i >= 0; i--){
			if(a.nums[i] > b.nums[i]) return GREATER;
			if(a.nums[i] < b.nums[i]) return LESS;
		}
		return EQUAL;
	}
	return EQUAL;
}

有了这个比较函数，我们就可以实现减法函数了。

参考代码如下：

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
struct BigInt sub(struct BigInt a, struct BigInt b){
	struct BigInt c;
	memset(&c, 0, sizeof(c));
	
	if (a.negative ^ b.negative) {
		b.negative = !b.negative;
		return add(a, b);
	}
	
	if (a.negative & b.negative) {
		a.negative = b.negative = false;
		return sub(b, a);
	}

	if(cmp(a, b) == LESS){
		c = a;
		a = b;
		b = c;
		memset(&c, 0, sizeof(c));
		c.negative = true;
	}
	
	c.len = max(a.len, b.len);
	
	for(int i = 0; i < c.len; i++){
		c.nums[i] = a.nums[i] - b.nums[i];
	}
	
	for(int i = 0; i < c.len; i++){
		if(c.nums[i] < 0){
			c.nums[i+1]--;
			c.nums[i] += 10;
		}
	}
	
	while (c.nums[c.len] == 0 && c.len > 0){
		c.len--;
	}
	
	c.len++;
	
	return c;
}

大整数的乘法

我们知道，乘法其实是做很多次加法。但是显然，单纯的一遍遍模拟加法是不现实的，我们同样使用竖式乘法来实现计算过程，只是相比起加法更复杂了一些。计算过程请阅读代码理解。

位数方面，不会超过 a.len + b.len 。实际位数的确定和加法一样，进位的处理也和加法一样。

而符号，则是两个数符号异或的结果，因为负负得正嘛。

参考代码如下：

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
struct BigInt multiply(struct BigInt a, struct BigInt b){
	struct BigInt c;
	memset(&c, 0, sizeof(c));
	
	c.len = a.len + b.len;
	
	for(int i = 0; i < a.len; i++){
		for(int j = 0; j < b.len; j++){
			c.nums[i+j] = c.nums[i+j] + a.nums[i] * b.nums[j];
		}
	}
	
	for(int i = 0; i < c.len; i++){
		c.nums[i+1] = c.nums[i] / 10 + c.nums[i+1];
		c.nums[i] = c.nums[i] % 10;
	}
	
	while (c.nums[c.len] == 0 && c.len > 0){
		c.len--;
	}
	
	c.len++;
	
	c.negative = a.negative ^ b.negative;
	
	return c;
}

大整数的除法

这里的除法和 C 语言的整数除法一样，我们默认结果是向下取整的。同样我们可以想到，除法可以用减法来模拟，但这同样太过耗时。而我的一种朴素的想法是逐位试商，然后将试出来的商和被除数比较。而商的位数不会超过被除数的位数，所以我们一开始便默认商的位数是被除数的位数，然后开始试商过程。这里需要用到之前的 cmp 函数来比较结果。

符号的处理和乘法一样。

虽然个人感觉效率并不高，但比减法还是要快上不少。如果有更好的解决方法，欢迎在评论中提出。

参考代码如下：

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
struct BigInt divide(struct BigInt a, struct BigInt b){
	struct BigInt c; 
	memset(&c, 0, sizeof(c));	
		
	c.len = a.len;	
	
	for(int i = a.len; i > 0; i--){
		while(1){
			c.nums[i - 1]++;
			if(cmp(multiply(c, b), a) == GREATER){
				c.nums[i - 1]--;
				break;
			} 
		}
	}
	
	while (c.nums[c.len] == 0 && c.len > 0){
		c.len--;
	}
	
	c.len++;

	c.negative = a.negative ^ b.negative;
	
	return c;
}

大整数的其他运算

大整数的取余

我们知道，lcm(a, b) = a * b / gcd(a, b)。这里，最大公约数函数我们使用辗转相除法来实现。

一般整数的辗转相除法实现是这样子的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int gcd(int a, int b) {
	if (a < b) {
		int c = a;
		a = b;
		b = c;
	}

	while(r = a % b) {
		a = b;
		b = r;		
	}

	return b;
}

可以看到，我们需要用到取余运算。在除法的基础上，取余十分容易，这里直接给出代码：

1
2
3
struct BigInt mod(struct BigInt a, struct BigInt b){
	return sub(a, multiply(divide(a, b), b));
}

大整数的最大公约数

至此，我们可以按照上述辗转相除法的思想，编写出大整数的 gcd 函数了。同样，这里直接给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct BigInt gcd(struct BigInt a, struct BigInt b){
	struct BigInt zero;
	memset(&zero, 0, sizeof(zero));
	zero.len = 1;
	zero.nums[0] = 0;
	
	if(cmp(a, b) == LESS){
		struct BigInt c = a;
		a = b;
		b = c;
	}

	struct BigInt r;
	
	while(1) {
		r = mod(a, b);
		if(cmp(r, zero) == EQUAL) break;
		a = b;
		b = r;
	} 
	
	return b;
}

大整数的最小公倍数

有了前面几个函数的基础，求最小公倍数就十分容易了：

1
2
3
struct BigInt lcm(struct BigInt a, struct BigInt b) {
	return divide(multiply(a, b), gcd(a, b));
}

总结

利用上面实现的函数，我们基本可以满足常见的大整数运算，也可以完成这道最小公倍数的题目了。

当然，以上的代码还有很多优化的空间，例如万进制优化，也有比如乘方等运算没有实现，但是，当我们完成了四则运算的实现之后，想必对大整数编程也有一定的理解，后续的优化和改进也变得不那么难了。