编程分享 | 大整数的实现


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

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

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

大整数的基础

大整数的存储

我们很自然可以想到,存储整数,需要存储它的正负、每一位的数字,以及这个数的长度。为此,我们定义 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));
}

总结

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

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

发表评论

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