高精度运算

高精度计算用于解决位数超过32位的大整数加减乘除问题。
高精度的存储是把每一位单独储存，如num[1]为个位，num[2]为十位。

高精度加法

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string a, b;
    int A[250], B[250];
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    cin >> a >> b;
    A[0] = a.length(); B[0] = b.length();
    for (int i = 1; i <= A[0]; ++i) {
        A[i] = a[A[0] - i] - '0';
    }
    for (int i = 1; i <= B[0]; ++i) {
        B[i] = b[B[0] - i] - '0';
    }
    int len = (A[0] > B[0] ? A[0] : B[0]);
    for (int i = 1; i <= len; ++i) {
        A[i] += B[i];
        A[i + 1] = A[i] / 10;
        A[i] %= 10;
    }
    len++;
    while (A[len] == 0 && len > 1)len--;
    for (int i = 1; i <= len; ++i) {
        cout << A[i];
    }
    return 0;
}

高精度减法

高精度减法由于需要考虑某一位相减后变为负数，所以要稍微复杂一些。
并且要先确定相减后结果的正负号。

#include <iostream>
#include <string>
using namespace std;

bool compare(string s1, string s2) {
    if (s1.length() > s2.length())return true;
    if (s1.length() < s2.length())return false;
    for (int i = 0; i <= s1.length(); ++i) {
        if (s1[i] > s2[i])
            return true;
        if (s1[i] < s2[i])
            return false;
    }
    return true;
}

int main()
{
    string a, b;
    int A[250], B[250];
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    cin >> a >> b;
    A[0] = a.length(); B[0] = b.length();
    for (int i = 1; i <= A[0]; ++i) {
        A[i] = a[A[0] - i] - '0';
    }
    for (int i = 1; i <= B[0]; ++i) {
        B[i] = b[B[0] - i] - '0';
    }
    if (compare(a, b)) {
        for (int i = 1; i <= A[0]; ++i) {
            A[i] -= B[i];
            if (A[i] < 0){
                A[i + 1]--;
                A[i] += 10;
            }
        }
        while (A[A[0]] == 0 && A[0] > 1)A[0]--;
        for (int i = A[0]; i > 0; --i)cout << A[i];
    }
    else {
        cout << "-";
        for (int i = 1; i <= B[0]; ++i) {
            B[i] -= A[i];
            if (B[i] < 0) {
                B[i + 1]--;
                B[i] += 10;
            }
        }
        while (B[B[0]] == 0 && B[0] > 1)B[0]--;
        for (int i = B[0]; i > 0; --i)cout << B[i];
    }
    return 0;
}

高精度乘法

乘法的难点在于如何处理位与位之间的关系
例如第一个数的第位乘上第二个数的第位，那么乘得的数应该占在第位，处理进位的方式与加法相同。

#include <iostream>
#include <string>
using namespace std;


int main()
{
    string a, b;
    int A[250], B[250], C[500];
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    memset(C, 0, sizeof(C));
    cin >> a >> b;
    A[0] = a.length(); B[0] = b.length();
    for (int i = 1; i <= A[0]; ++i) {
        A[i] = a[A[0] - i] - '0';
    }
    for (int i = 1; i <= B[0]; ++i) {
        B[i] = b[B[0] - i] - '0';
    }
    for(int i=1;i<=A[0];++i)
        for (int j = 1; j <= B[0]; ++j) {
            C[i + j - 1] += A[i] * B[j];
            C[i + j] += C[i + j - 1] / 10;
            C[i + j - 1] %= 10;
        }
    int len = A[0] + B[0] + 1;
    while (C[len] == 0 && len > 1)len--;
    for (int i = len; i > 0; --i) {
        cout << C[i];
    }
    cout << endl;
    return 0;
}

高精度除法

高精度除法分为两种情况，一种是高精度除以低精度，一种是高精度除以高精度。
这里只写出第一种。

#include <iostream>
#include <string.h>
#include <string>
#define charToNum(x) (x-'0')
using namespace std;


int main()
{
    string a;
    int b, re = 0;
    int save[1010];
    int result[1010];
    memset(save, 0, sizeof(save));
    memset(result, 0, sizeof(result));
    cin >> a >> b;
    save[0] = a.size();
    for (int i = 0; i < a.size(); ++i) {
        save[i] = charToNum(a[i]);
    }
    for (int i = 0; i < a.size(); ++i) {
        result[i] = (re * 10 + save[i]) / b;
        re = (re * 10 + save[i]) % b;
    }
    int lenc = 0;
    while (result[lenc] == 0 && lenc < a.size()-1)lenc++;
    for (int i = lenc; i < a.size(); ++i) {
        cout << result[i];
    }
    cout <<" "<< re << endl;
    return 0;
}