编程分享 | 大整数的实现

Posted on by howardlau


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

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

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

大整数的基础

大整数的存储

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

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

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

大整数的读入

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

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

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;
}

大整数的输出

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

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. 两个数同为负数

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

参考代码如下：

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. 若每一位都相等，则认为两个数绝对值相等。

参考代码如下：

#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;
}

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

参考代码如下：

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 。实际位数的确定和加法一样，进位的处理也和加法一样。

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

参考代码如下：

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 函数来比较结果。

符号的处理和乘法一样。

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

参考代码如下：

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)。这里，最大公约数函数我们使用辗转相除法来实现。

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

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;
}

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

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

大整数的最大公约数

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

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;
}

大整数的最小公倍数

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

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

总结

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

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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注