在处理数据的时候经常需要用到一些无比巨大的数，比如41856410684191645611这种的，或者是十进制的二进制转化，显然cpp里不能直接用int存放这些数据，然而long类型也是有上限的，这时就需要引入一个新的算法，叫做高精度算法

算法本质思想

感觉多数思路就是用数组之类的容器存放数据，采用最原始的方式一点点进位计算之类的。（果然高端的食材往往采用最朴素的烹饪方式）。

细节处理

高精度计算中有几个细节需要注意：

  • 数据接受和储存： 当输入的数很长时，可以使用字符串方式输入和储存，再用字符串函数进行操作运算，将每一位去取出，存入数组。

    1
    2
    3
    4
    5
    6
    7
    void init(int a[]) { // 传入数组
        string s;
        cin >> s; 
        len = s.length(); // s.length --> 计算字符串位数
        for(int i=1; i<=len; i++)     
            a[i] = s[len -i] - '0'; //将字符串s转换为数组a, 倒序存储
    }

  • 进位错位处理：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 加法进位: c[i] = a[i] + b[i]
     
    code:    if(c[i] >= 10) {
                c[i] %= 10;
                ++c[i++];
             }
     
    //减法借位: c[i] = a[i] - b[i]
     
    code:    if(a[i] < b[i]) {
                 --a[i+1];
                 a[i] += 10;   
             } 
     
    //乘法进位: c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
              x = c[i + j - 1] / 10;
              c[i + j - 1] % 10;

    高精度加法：

    输入两个数到变量中，然后用赋值语句求它们的和后输出 . But，我们知道，在 C++ 语言中任何数据类型都有一定表示范围. 当两个加数很大时，以前的算法显然不能求出精确解，因此我们需要寻求另一种方法 .在读小学时，我们做加法都采用竖式方法 . 这样我们方便写出两个整数相加的算法 .

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 高精度加法
    string add(string num1, string num2) {
        int carry = 0;
        int n1 = num1.size(), n2 = num2.size();
        int i = n1 - 1, j = n2 - 1;
        string sum = "";
        while (i >= 0 || j >= 0 || carry) {
            int digit1 = (i >= 0) ? num1[i--] - '0' : 0;
            int digit2 = (j >= 0) ? num2[j--] - '0' : 0;
            int s = digit1 + digit2 + carry;
            carry = s / 10;
            sum = to_string(s % 10) + sum;
        }
        return sum;
    }

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 高精度减法
string subtract(string num1, string num2) {
    int borrow = 0;
    int n1 = num1.size(), n2 = num2.size();
    int i = n1 - 1, j = n2 - 1;
    string diff = "";
    while (i >= 0 || j >= 0) {
        int digit1 = (i >= 0) ? num1[i--] - '0' : 0;
        int digit2 = (j >= 0) ? num2[j--] - '0' : 0;
        int d = digit1 - digit2 - borrow;
        if (d < 0) {
            d += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        diff = to_string(d) + diff;
    }
    // 删除前导零
    diff.erase(0, diff.find_first_not_of('0'));
    return (diff == "") ? "0" : diff;
}

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 高精度乘法
string multiply(string num1, string num2) {
    int n1 = num1.size(), n2 = num2.size();
    vector<int> result(n1 + n2, 0);
    for (int i = n1 - 1; i >= 0; i--) {
        for (int j = n2 - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + result[i + j + 1];
            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    }
    // 转换为字符串
    string product = "";
    for (int digit : result) {
        if (!(product.empty() && digit == 0)) {  // 忽略前导零
            product += to_string(digit);
        }
    }
    return (product == "") ? "0" : product;
}

高精度除法

高精度除以低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 高精度除法（除以低精度）
pair<string, int> divide(string dividend, int divisor) {
    string quotient = "";
    int remainder = 0;
    for (char digit : dividend) {
        int num = digit - '0' + remainder * 10;
        quotient += to_string(num / divisor);
        remainder = num % divisor;
    }
    // 删除前导零
    quotient.erase(0, quotient.find_first_not_of('0'));
    return make_pair((quotient == "") ? "0" : quotient, remainder);
}

高精度除以高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 高精度除法（除以高精度）
pair<string, string> divide(string dividend, string divisor) {
    string quotient = "0", remainder = dividend;
    while (remainder.size() >= divisor.size() && remainder >= divisor) {
        int n = remainder.size() - divisor.size();
        string temp = divisor;
        temp.append(n, '0'); // 补零
        int count = 1;
        while (remainder >= temp) {
            remainder = subtract(remainder, temp);
            quotient = add(quotient, "1" + string(n, '0'));
            count++;
        }
    }
    // 删除前导零
    quotient.erase(0, quotient.find_first_not_of('0'));
    remainder.erase(0, remainder.find_first_not_of('0'));
    return make_pair((quotient == "") ? "0" : quotient, (remainder == "") ? "0" : remainder);
}

压位技巧

谁说数组每个元素只能是一位数？显然这会造成巨大的浪费。
这时我们就可以使用压位的技巧来节省运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
using namespace std;

// 压位技巧高精度加法
string add(string num1, string num2) {
    vector<int> result(max(num1.size(), num2.size()) + 1, 0); // 结果数组
    int carry = 0; // 进位
    int i = num1.size() - 1, j = num2.size() - 1, k = result.size() - 1; // 从个位开始相加
    while (i >= 0 || j >= 0 || carry) {
        int digit1 = (i >= 0) ? num1[i--] - '0' : 0; // 获取num1的当前位数字
        int digit2 = (j >= 0) ? num2[j--] - '0' : 0; // 获取num2的当前位数字
        int sum = digit1 + digit2 + carry; // 当前位的和
        result[k--] = sum % 10; // 将当前位的和放入结果数组
        carry = sum / 10; // 更新进位
    }
    // 转换结果数组为字符串
    string sum = "";
    for (int digit : result) {
        if (!(sum.empty() && digit == 0)) { // 忽略前导零
            sum += to_string(digit);
        }
    }
    return (sum == "") ? "0" : sum; // 如果结果为空字符串，则返回"0"
}

int main() {
    string num1 = "123456789012345678901234567890";
    string num2 = "987654321098765432109876543210";
    cout << "高精度加法结果：" << add(num1, num2) << endl;
    return 0;
}


总之大多数需要根据现实情况变通。。。。