高精度四则运算

大整数四则运算

  1. 高精度加法
    #include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    const int N = 1e6 + 6;
    string a, b;
    vector<int> A, B;
    
    vector<int> add(vector<int> &A, vector<int> &B) {
        vector<int> C;
        int t = 0;
        int lenA = A.size(), lenB = B.size(), lim = max(lenA, lenB);
        for (int i = 0; i < lim; ++i) {
            if (i < lenA) t += A[i];
            if (i < lenB) t += B[i];
            C.push_back(t % 10);
            t /= 10;
        }
        if (t) C.push_back(1);
        return C;
    }
    
    int main() {
        cin >> a >> b;
        int lenA = a.size(), lenB = b.size();
        for (int i = lenA - 1; i >= 0; --i) {
            A.push_back(a[i] - '0');
        }
        for (int i = lenB - 1; i >= 0; --i) {
            B.push_back(b[i] - '0');
        }
        auto C = add(A, B);
        int lenC = C.size();
        for (int i = lenC - 1; i >= 0; --i) {
            cout << C[i];
        }
        return 0;
    }

    逆序vector存储大整数比较方便,
    操作是定义一个临时变量t,
    遍历两数对应位加到t上,
    模十push_back到vector尾部,
    除以十作为进位信息。

  2. 大整数相减
    #include <bits/stdc++.h>
    
    using namespace std;
    
    vector<int> A, B;
    
    bool cmp(vector<int> &A, vector<int> &B) {
        if (A.size() != B.size()) return A.size() > B.size();
        for (int i = A.size() - 1; i >= 0; --i) {
            if (A[i] != B[i]) return A[i] > B[i];
        }
        return true;
    }
    
    auto sub(vector<int> A, vector<int> B) { // 默认A >= B
        vector<int> C;
        int t = 0;
        for (int i = 0; i < A.size(); ++i) {
            t = A[i] - t;
            if (i < B.size()) t -= B[i];
            C.push_back((t + 10) % 10);
            if (t < 0) t = 1;
            else t = 0;
        }
        while (C.size() > 1 && C.back() == 0) C.pop_back();
        return C;
    }
    
    
    int main() {
        string a, b;
        cin >> a >> b;
        int lenA = a.length(), lenB = b.length();
        for (int i = lenA - 1; i >= 0; --i) {
            A.push_back(a[i] - '0');
        }
        for (int i = lenB - 1; i >= 0; --i) {
            B.push_back(b[i] - '0');
        }
        bool f = 0;
        if (!cmp(A, B)) swap(A, B), f = 1; // 特判如果结果是负数,只需计算-(B-A)即可。
        auto C = sub(A, B);
        int lenC = C.size();
        if (f) putchar('-');
        for (int i = lenC - 1; i >= 0; --i) {
            printf("%d", C[i]);
        }
        return 0;
    }

    核心代码是借位的计算,对应位置A减去B(若存在)再减去上一位的进位,将结果加十模十push_back进C(加十模十是为了抹掉负数结果),如果结果为负数,表明借位为1,否则没有借位。

    需要注意的细节:该模板默认A>=B,若结果为负,需要在外部做相应判断。

  3. 大整数乘小整数
    #include <bits/stdc++.h>
    
    using namespace std;
    
    auto multiply(vector<int> &A, int B) {
        vector<int> C;
        int lenA = A.size();
        int t = 0;
        for (int i = 0; i < lenA || t; ++i) {
            if (i < lenA) t += A[i] * B;
            C.push_back(t % 10);
            t /= 10;
        }
        while (C.size() > 1 && C.back() == 0) C.pop_back();
        return C;
    }
    
    int main() {
        string a;
        int b;
        cin >> a >> b;
        vector<int> A;
        for (int i = a.size() - 1; i >= 0; --i) {
            A.push_back(a[i] - '0');
        }
        auto C = multiply(A, b);
        for (int i = C.size() - 1; i >= 0; --i) {
            printf("%d", C[i]);
        }
        return 0;
    }

    思想与大整数相加类似,注意去除前导零即可。

  4. 大整数除以小整数
    #include <bits/stdc++.h>
    
    using namespace std;
    
    auto divide(vector<int> &A, int B, int &r) {
        vector<int> C;
        int lenA = A.size();
        r = 0;
        for (int i = lenA - 1; i >= 0; --i) {
            r = r * 10 + A[i];
            C.push_back(r / B);
            r %= B;
        }
        reverse(C.begin(), C.end());
        while (C.size() > 1 && C.back() == 0) C.pop_back();
        return C;
    }
    
    int main() {
        string a;
        int b;
        cin >> a >> b;
        vector<int> A;
        for (int i = a.size() - 1; i >= 0; --i) {
            A.push_back(a[i] - '0');
        }
        int r;
        auto c = divide(A, b, r);
        for (int i = c.size() - 1; i >= 0; --i) {
            printf("%d", c[i]);
        }
        cout << "\n" << r;
        return 0;
    }

    为了与前面三则运算统一,同样逆序存储,实际遍历从高位开始,每次循环时从高位借位*10加上当前位数字,结果除以push_back进C,模B用于下一次借位。

上一篇:windows应用程序签名


下一篇:WAA可视化