key 总贴，阅读更佳

高精度的意义

相信大家在做题时，时常会遇到数据大于 $long long$ 极限的值，此时我们有两种选择:

1. 使用内存更大的 $unsigned long long$.
2. 那如果更大呢？ $C 、C++$ 的码农们就需要自己写高精了。

版权声明：以下代码均为整理，非亲写，不过有较为详细的批注。

//注1：头文件最好为#include<bits/stdc++.h>，因为此模板涉及的头文件很多
//注2：如果你想新建一个BigInteger，可以BigInteger a=BigInteger(x)，x可以为int整型或string字符串 
//注3：使用时全盘复制就好，像平常运算那样使用，输出符号和左移符号容易混淆，同时用时要加上括号和空格 

// 常量，分别表示正数、负数、相等。
const int POSITIVE = 1, NEGATIVE = -1, EQUAL = 0;

高精度————大整数 $BigInteger$

class BigInteger
{
    // 重载输出符号。
    friend ostream& operator<<(ostream&, const BigInteger&);
    // 比较操作。
    friend int compare(const BigInteger&, const BigInteger&);
    friend bool operator<(const BigInteger&, const BigInteger&);
    friend bool operator<=(const BigInteger&, const BigInteger&);
    friend bool operator==(const BigInteger&, const BigInteger&);
    // 相关运算的实现：加法、减法、乘法、除法、模、乘方、左移。
    friend BigInteger operator+(const BigInteger&, const BigInteger&);
    friend BigInteger operator-(const BigInteger&, const BigInteger&);
    friend BigInteger operator*(const BigInteger&, const BigInteger&);
    friend BigInteger operator/(const BigInteger&, const BigInteger&);
    friend BigInteger operator%(const BigInteger&, const BigInteger&);
    friend BigInteger operator^(const BigInteger&, const unsigned int&);
    friend BigInteger operator^(const BigInteger&, const BigInteger&);
    friend BigInteger operator<<(const BigInteger&, const unsigned int&);
    public:
        BigInteger() {};
        // 将长整型及字符串转换为高精度整数的构造函数。
        BigInteger(const long long&);
        BigInteger(const string&);
        // 获取高精度整数的最后一个数位值。
        int lastDigit() const { return digits.front(); }
        ~BigInteger() {};
    private:
        // 清除运算产生的前导零。
        void zeroJustify(void);
        // 采用 10000 作为基数。数位宽度为 4。
        static const int base = 10000;
        static const int width = 4;
        // 符号位和保存数位的向量。
        int sign;
        vector<int> digits;
        int stoi(string s)
        {
            int ans=0,l=s.size();
            for(int i=0;i<l;i++)
            {
                ans*=10;
                ans+=s[i]-'0';
            }
            return ans;
        }
};

移除无效的前导零。

void BigInteger::zeroJustify(void)
{
    for (int i = digits.size() - 1; i >= 1; i--)
    {
        if (digits[i] > 0)
            break;
        digits.erase(digits.begin() + i);
    }
    if (digits.size() == 1 && digits[0] == 0)
        sign = POSITIVE;
}

重载输出符号以输出大整数。

ostream& operator<<(ostream& os, const BigInteger& number)
{
    os << (number.sign > 0 ? "" : "-");
    os << number.digits[number.digits.size() - 1];
    for (int i = (int)number.digits.size() - 2; i >= 0; i--)
        os << setw(number.width) << setfill('0') << number.digits[i];
    return os;
}

将长整型数转换为大整数。

BigInteger::BigInteger(const long long& value)
{
    if (value == 0)
    {
        sign = POSITIVE;
        digits.push_back(0);
    }
    else
    {
        // 不断模基数取余得到各个数位。
        sign = (value >= 0 ? POSITIVE : NEGATIVE);
        long long number = abs(value);
        while (number)
        {
            digits.push_back(number % base);
            number /= base;
        }
    }
    // 移除前导零。
    zeroJustify();
};

将十进制的字符串转换为大整数。

BigInteger::BigInteger(const string& value)
{
    if (value.length() == 0)
    {
        sign = POSITIVE;
        digits.push_back(0);
    }
    else
    {
        // 设置数值的正负号。
        sign = value[0] == '-' ? NEGATIVE : POSITIVE;
        // 四个数字作为一组，转换为整数存储到数位数组中。
        string block;
        for (int index = value.length() - 1; index >= 0; index--)
        {
            if (isdigit(value[index]))
                block.insert(block.begin(), value[index]);
            if (block.length() == width)
            {
                digits.push_back(stoi(block));
                block.clear();
            }
        }
        if (block.length() > 0)
            digits.push_back(stoi(block));
    }
    // 移除前导零。
    zeroJustify();
}

比较两个高精度整数的大小。

// x 大于 y，返回 1，x 小于 y，返回-1，x 等于 y，返回 0。
// 为了后续除法的需要调整了实现，使得对于未经前导零调整的整数也能够得到正确的处理。
int compare(const BigInteger& x, const BigInteger& y)
{
    // 符号不同，正数大于负数。
    if (x.sign == POSITIVE && y.sign == NEGATIVE ||
    x.sign == NEGATIVE && y.sign == POSITIVE)
        return (x.sign == POSITIVE ? 1 : -1);
    // 确定 x 和 y 的有效数位个数，前导零不计入有效数位。
    int xDigitNumber = x.digits.size() - 1;
    for (; xDigitNumber && x.digits[xDigitNumber] == 0; xDigitNumber--) ;
    int yDigitNumber = y.digits.size() - 1;
    for (; yDigitNumber && y.digits[yDigitNumber] == 0; yDigitNumber--) ;
    // 符号相同，同为正数，数位个数越多则越大，同为负数，数位个数越多则越小。
    if (xDigitNumber > yDigitNumber)
        return (x.sign == POSITIVE ? 1 : -1);
    // 符号相同，同为正数，数位个数越少则越小，同为负数，数位个数越少则越大。
    if (xDigitNumber < yDigitNumber)
        return (x.sign == NEGATIVE ? 1 : -1);
    // 符号相同，数位个数相同，逐位比较。
    for (int index = xDigitNumber; index >= 0; index--)
    {
        if (x.digits[index] > y.digits[index])
            return (x.sign == POSITIVE ? 1 : -1);
        if (x.digits[index] < y.digits[index])
            return (x.sign == NEGATIVE ? 1 : -1);
    }
    // 两数相等。
    return 0;
}

未完待续......

(滚回去准备期末考啦！)