全能編程開發工程師必備技能——如何優化大整數的計算

本文將會為你分享如何解決大整數計算問題，以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;
}

總結

以上就是對大整數計算的優化方法，我們可以通過字符串來表示大整數，並且模擬手工計算的過程來進行各種運算。希望本文能夠對你有所幫助。