两个大整数相乘，如何在不损失精度的前提下计算得到正确的结果？

不限精度的整数运算

前一篇文章我们讨论了两个64位整数的乘法，本篇文章我们讨论高精度数值的加减运算问题。

大整数存储

很简单，使用数组即可。注意整数的高位存储在数组的末尾，整数的低位存储在数组的开头。

# 235813
d[0] = 3
d[1] = 1
d[2] = 8
d[3] = 5
d[4] = 3
d[5] = 2

这样做的原因是，四则运算一般是从低位向高位计算的，数组则是从0开始遍历的。不过如果数字以字符串存储则不然。比如s="235813"这个字符串的存储顺序和逻辑顺序恰恰相反。

class BigInt {
public:
    int d[1000]{};
    int len;
    BigInt() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
    static BigInt change(std::string str);
    static int compare(BigInt a, BigInt b);
    static BigInt add(BigInt a, BigInt b);
    static BigInt sub(BigInt a, BigInt b);
};

输入大整数时，一般都以string类型输入，因此需要执行reverse操作，或者直接逆序赋值。

大整数运算

加法

BigInt BigInt::add(BigInt a, BigInt b) {
    BigInt c;
    int carry = 0;
    for (int i = 0; i < a.len || i < b.len; ++i) {
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    if (carry != 0) {
        c.d[c.len++] = carry;
    }
    return c;
}

减法

BigInt BigInt::sub(BigInt a, BigInt b) {
    BigInt c;
    for (int i = 0; i < a.len || i < b.len; ++i) {
        if (a.d[i] < b.d[i]) {
            a.d[i+1]--;
            a.d[i] += 10; // 借位
        }
        c.d[c.len++] = a.d[i] - b.d[i];
    }
    while (c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
        c.len--;
    }
    return c;
}

比较

int BigInt::compare(BigInt a, BigInt b) {
    if (a.len > b.len) return 1;
    else if (a.len < b.len) return -1;
    else {
        for (int i = a.len-1; i >= 0; --i) {
            if (a.d[i] > b.d[i]) return 1;
            else if (a.d[i] < b.d[i]) return -1;
        }
        return 0;
    }
}

参考

算法笔记 5.6 节