全能编程开发工程师必备技能——如何优化大整数的计算

本文将会为你分享如何解决大整数计算问题，以9999999967为例，我们将从多个方面对其做详细阐述，并给出完整的代码示例。

一、大整数的表示方法

在计算机中，我们通常采用二进制数来表达数字。然而，由于计算机的内存有限，只能存储一定范围的二进制数，因此对于大整数，需要采用其他方法来表示。

我们可以使用字符串来表示大整数，即将大整数的每一位数字都存储在一个字符中，然后用一个字符串来存储这些字符。例如，9999999967可以表示成字符串”9999999967″。

二、大整数的加法

在对大整数进行加法计算时，我们需要模拟手工计算的过程。从两个大整数的最低位开始逐位相加，并且要考虑进位。当一个数的位数不够时，可以在高位补0。

string add(string a, string b) {
    int lena = a.length(), lenb = b.length();
    int len = max(lena, lenb);
    int carry = 0;
    string res(len, '0');
    for (int i = 0; i < len; i++) {
        if (i < lena) carry += a[lena - i - 1] - '0';
        if (i < lenb) carry += b[lenb - i - 1] - '0';
        res[len - i - 1] = carry % 10 + '0';
        carry /= 10;
    }
    if (carry) res.insert(res.begin(), carry + '0');
    return res;
}

三、大整数的减法

在对大整数进行减法计算时，同样需要模拟手工计算的过程。从被减数的最低位开始逐位相减，并且考虑借位。当被减数小于减数时，需要向高位借位。

string sub(string a, string b) {
    int lena = a.length(), lenb = b.length();
    int len = max(lena, lenb);
    int borrow = 0;
    string res(len, '0');
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    for (int i = 0; i < len; i++) {
        int x = i < lena ? a[i] - '0' : 0;
        int y = i < lenb ? b[i] - '0' : 0;
        res[i] = (x - borrow - y + 10) % 10 + '0';
        borrow = x - borrow - y < 0 ? 1 : 0;
    }
    while (res.length() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

四、大整数的乘法

在对大整数进行乘法计算时，需要将乘数的每一位与被乘数相乘，并且考虑进位，最后将所有相乘结果相加。

string mul(string a, string b) {
    int lena = a.length(), lenb = b.length();
    vector res(lena + lenb, 0);
    for (int i = lena - 1; i >= 0; i--) {
        for (int j = lenb - 1; j >= 0; j--) {
            int x = a[i] - '0';
            int y = b[j] - '0';
            res[i + j + 1] += x * y;
            res[i + j] += res[i + j + 1] / 10;
            res[i + j + 1] %= 10;
        }
    }
    string ans = "";
    int k = 0;
    while (k < lena + lenb && res[k] == 0) k++;
    for (int i = k; i < lena + lenb; i++) ans += res[i] + '0';
    return ans.length() == 0 ? "0" : ans;
}

五、大整数的除法

在对大整数进行除法计算时，需要将除数逐位与被除数相除，统计商和余数。被除数小于除数时，算法结束。当被除数大于除数时，还需要考虑高位的0，以及余数的进位。

string div(string a, string b) {
    string ans = "0", cur = "";
    for (int i = 0; i < a.length(); i++) {
        cur += a[i];
        int cnt = 0;
        while (cur.length() >= b.length() && cur >= b) {
            cur = sub(cur, b);
            cnt++;
        }
        ans += (cnt + '0');
    }
    while (ans.length() > 1 && ans[0] == '0') ans.erase(ans.begin());
    return ans;
}

六、大整数的模取

在对大整数进行模取时，只需要求出大整数除以模数的余数即可。

int mod(string a, int b) {
    int ans = 0;
    for (int i = 0; i < a.length(); i++) {
        ans = ans * 10 + (a[i] - '0');
        ans %= b;
    }
    return ans;
}

总结

以上就是对大整数计算的优化方法，我们可以通过字符串来表示大整数，并且模拟手工计算的过程来进行各种运算。希望本文能够对你有所帮助。