详解C/C++高精度(加减乘除)算法中的压位优化

什么是高精度算法？

高精度算法（又叫大数算法）是指可以处理比计算机支持的最大数值范围更大的数值计算方法。在C/C++中，int类型变量的最大范围一般为2^31-1即2147483647，而long long型变量的最大范围一般为2^63-1即9223372036854775807。如果需要处理比这更大的数字，则无法使用普通的数据类型进行计算，需要使用高精度算法来处理。

为什么需要压位优化？

高精度算法是通过将大数拆分成若干个小数的方式来进行计算的。例如，“12345678901234567890”可以拆分成“1234567890”和“1234567890”，然后进行逐位相加或相乘，得出最终答案。这种拆分操作会产生很多的进位（或借位）操作，导致算法效率不高。而压位优化则可以有效降低进位（或借位）的次数，提高算法效率。

压位优化的具体实现方法

压位优化的实现方法比较简单，只需要将高精度算法中的拆分操作重新定义，使得可以同时处理更多位数的数字。具体来说，可以先将高精度数值按照32位（或64位）一组进行划分，再进行计算。

具体实现方法可以参考以下代码：

#include <bits/stdc++.h>
using namespace std;

const int BASE = 1000000000;
const int WIDTH = 9;

typedef long long ll;

struct BigInt {
    vector<int> s;

    BigInt& clean() {while(!s.back() && s.size() > 1) s.pop_back(); return *this;}

    BigInt(ll num = 0) {*this = num;}
    BigInt(string s) {*this = s;}

    BigInt& operator = (long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }

    BigInt& operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start,end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return (*this).clean();
    }

    BigInt operator + (const BigInt& b) const {
        BigInt c;
        c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }

    BigInt operator * (const BigInt& b) const {
        vector<ll> num(s.size()+b.s.size(), 0);
        for (int i = 0; i < s.size(); i++)
            for (int j = 0; j < b.s.size(); j++)
                num[i+j] += (ll)s[i] * b.s[j];

        BigInt c;
        c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g ==0 && i >= num.size()) break;
            ll x = num[i] + g;
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c.clean();
    }

    // ...

};

int main() {
    BigInt a, b, c;
    a = "1234567890123456789012345678901234567890";
    b = "1098765432109876543210987654321098765432109876543210";
    c = a + b;
    cout << c << endl;
    return 0;
}

在以上代码中，对高精度数字的拆分操作被重新定义为32位的数字组，在进行加法和乘法操作时，可以同时处理更多的位数，降低进位和借位的次数，提高算法效率。

示例说明

以下是使用以上代码进行加法运算的示例：

BigInt a, b, c;
a = "1234567890123456789012345678901234567890";
b = "1098765432109876543210987654321098765432109876543210";
c = a + b;
cout << c << endl;

以上代码中，首先声明了三个BigInt类型的变量a、b、c，并通过字符串的方式将大数赋值给a和b。然后通过c = a + b的方式进行加法操作，最终输出结果。由于使用了压位优化，计算速度比普通的高精度算法要快很多。

另外一个使用压位优化进行高精度乘法的示例代码如下：

BigInt a, b, c;
a = "1234567890123456789012345678901234567890";
b = "1098765432109876543210987654321098765432109876543210";
c = a * b;
cout << c << endl;

以上代码中，同样使用了压位优化的乘法函数，可以同时处理更多的位数，提高计算效率。