支持负数的高精度模板

看到P1932时就想写高精度了, 但是因为种种原因(单纯因为懒和废)一直没有写. 因为实践课的附加题需要用到高精度, 于是就开始了漫长的爆肝之路(前前后后肝了接近五天).

主要参考: https://www.luogu.com.cn/blog/user24922/solution-p1932 增加了对负数运算的支持, 并且修复了一个bug.

因为代码比较长, 为了控制篇幅, 正文基本不会贴代码.

大整数的存储结构

很显然, 自带的数据类型并不够用, 所以我们需要自己造一个新类型.

既然支持负数运算, 那么一个标志位自然是必不可少的.

接着就需要存数据了, 显然, 有了标志位, 直接存绝对值会更方便, 所以我们直接开个 long long 数组(用有符号的便于加减法运算)来存就好了.

操作符重载

输入输出流

因为我不会, 所以照抄的. 因为重载得放在结构体后面, 所以添加了一个函数(print())方便debug. ### 赋值 思路类似, 但是加上了正负号的处理, 同时做了一些小调整(为了保证能够完全读入, 所以牺牲一些效率放宽了读入的访问范围. 这里还能卡常不成?) ### 比较 因为考虑了正负数, 所以代码量直接翻倍. 基本思路如下: 首先考虑符号, 然后考虑位数, 最后逐位判断. 同时因为有符号, 所以添加了一个函数(cmp_abs())来进行绝对值的比较. ### 加减 因为只能使用已经重载过的运算符, 所以加法(先重载的加法)中就必须考虑正负了, 所以对每种情况都需要处理. 重载减法时因为加法是可用的, 所以对一些情况直接转换成加法即可. ### 乘法 模拟乘法竖式即可, 基本照抄. 添加了对正负号的处理: 同号或者一个为0显然结果是非负数, 异号显然结果是负数. ### 移位 原版中移位是有bug的, 当num不为1时得出的不一定是正确结果, 于是简单粗暴的套了一层num次的循环解决问题. ### 除法 原理是减法, 通过倍增优化, 主要还是增加了对正负号的处理, 同上. ### ~膜~模 有了乘除, 怎么实现不需要多说(~其实是懒得写了~)吧.

踩的坑

首先是操作符重载过程中对 +=, -=之类的处理, 操作符重载中的*this对应的是左操作数.

//正确操作
BIGNUM operator += (const BIGNUM &a){
    *this = *this + a;
    return *this;
}
//错误操作, 并没有修改*this, 实际上(a += b)的值才等于(a + b)
BIGNUM operator += (const BIGNUM &a){
    return *this + a;
}

然后是操作符重载过程中对*this的处理, 某些操作中直接修改了*this的内容, 也就是说修改了操作数, 导致后续操作结果错误. 不明白的话举个例子就好了, 这就相当于执行完 "c = a + b; " 之后, a 或者 b 的值发生了改变.

还有一些就是逻辑错误了, 这个没什么好说的, 纯属脑子不清醒.

奇奇怪怪的优化

读原版代码的时候发现了一些神奇的语句:

//用异或实现char数字转int数字, 这里异或48相当于减48
s[s[0]] += (num[j] ^ 48) * w;
//左移实现 * 10
w = (w << 1) + (w << 3); 

还有通过倍增实现 O(n) 到 O(log2(n)) 的除法, 优化效果显著.

完整代码

更新记录(2021.04.11): + 修改输出流重载部分, 解决关闭同步后可能出现的问题. + 微调部分语句, 增加可读性.

点我查看完整代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>

const int LEN = 10009;
using namespace std;
typedef long long ll;

struct BIGNUM{
    static const int BIT = 9;
    static const int MOD = 1e9;//1eBIT 14 
    bool flag;//0 for 0 or positive, 1 for negative
    ll s[LEN];
    BIGNUM(){
        flag = 0;
        memset(s, 0, sizeof(s));
        s[0] = 1;
    }
    void init(){//数组清零
        memset(s, 0, sizeof(s));
    }
    void print(){//打印 
        BIGNUM a = *this;
        if (a.flag){
            printf("-");
        }	
        printf("%lld", a.s[a.s[0]]);
        for (int i = a.s[0] -1; i > 0; i--){
            printf("%09lld", a.s[i]);
        }
        printf("\n");
    }
    BIGNUM operator = (const char *num){
        if (num[0] == '-'){
            flag = 1;
            num++;
        }
        else if (num[0] == '+'){
            flag = 0;
            num++;
        }
        int l = strlen(num);
        s[0] = 0;
        for (int i = l - 1; i > -9; i -= 9){
            int temp = 0;
            for (int j = i - 8; j <= i; j++){
                if (j < 0)
                    continue;
                else{
                    temp = (temp<<1) + (temp<<3);
                    temp += num[j] ^ 48;
                }
            }
            s[++s[0]] = temp;
        }
        while(!s[s[0]] && s[0] > 1)	s[0]--;
        return *this;
    }
    BIGNUM operator = (const int num) {
        char a[LEN];
        sprintf(a, "%d", num);
        *this = a;
        return *this;
    }
    BIGNUM(int num) { *this = num; }
    BIGNUM(const char *num) { *this = num; }
    bool operator < (const BIGNUM &a){
        if (flag > a.flag)	return 1;
        else if (flag < a.flag)	return 0;
        else{
            if ((s[0] < a.s[0] && (!flag)) || (s[0] > a.s[0] && flag))	return 1;
            else if (s[0] != a.s[0])	return 0;
            else{
                for (int i = s[0]; i > 0; i--){
                    if (s[i] < a.s[i]){
                        if (flag)	return 0;
                        else	return 1;
                    }
                    else if (s[i] > a.s[i]){
                        if (flag)	return 1;
                        else	return 0;
                    }
                }
                return 0;
            }	
        }
    }
    bool operator > (const BIGNUM &a){
        if (flag > a.flag)	return 0;
        else if (flag < a.flag)	return 1;
        else{
            if ((s[0] > a.s[0] && (!flag)) || (s[0] < a.s[0] && flag))	return 1;
            else if (s[0] != a.s[0]){
                return 0;
            }
            else{
                for (int i = s[0]; i > 0; i--){
                    if (s[i] > a.s[i]){
                        if (flag)	return 0;
                        else	return 1;
                    }
                    else if (s[i] < a.s[i]){
                        if (flag)	return 1;
                        else	return 0;
                    }
                }
                return 0;
            }	
        }
    }
    bool operator == (const BIGNUM &a){
        if (flag != a.flag)	return 0;
        else{
            if (s[0] != a.s[0])	return 0;
            else{
                for (int i = s[0]; i > 0; i--){
                    if (s[i] != a.s[i])	return 0;
                }
                return 1;
            }	
        }
    }
    bool operator >= (const BIGNUM &a){
        if(*this > a || *this == a) return 1;
        return 0;
    }
    bool operator <= (const BIGNUM &a){
        return (*this == a)||(*this < a);
    }
    int cmp_abs(const BIGNUM &a){//1 for this > a, 0 for this == a, -1 for this < a
        if (s[0] > a.s[0])
            return 1;
        else if (s[0] < a.s[0])
            return -1;
        else{
            for (int i = s[0]; i > 0; i--){
                if (s[i] > a.s[i])
                    return 1;
                else if (s[i] < a.s[i])
                    return -1;
            }
        }
        return 0;
    } 
    BIGNUM operator + (const BIGNUM &B){
        BIGNUM c, a = *this, b = B;
        if (!(a.flag || b.flag) || (a.flag && b.flag)){
            c.flag = a.flag;
            int x = 0;
            c.s[0] = max(a.s[0], b.s[0]) + 1;
            for(int i = 1; i <= c.s[0]; i++) {
                 c.s[i] = a.s[i] + b.s[i] + x;
                   x = c.s[i] / MOD;
                c.s[i] %= MOD;
            }
        }
        else if (a.flag){// a < 0
            if (a.cmp_abs(b) == 1){//|a| > |b|, |ans| = |a| - |b|
                c.flag = 1;
                c.s[0] = max(a.s[0], b.s[0]) + 1;
                for(int i = 1; i <= c.s[0]; i++) {
                     c.s[i] = a.s[i] - b.s[i];
                       if (c.s[i] < 0){
                           c.s[i] += MOD;
                           a.s[i + 1]--;
                    }
                }
            }
            else{//|a| <= |b|, |ans| = |b| - |a|
                c.flag = 0;
                c.s[0] = max(a.s[0], b.s[0]) + 1;
                for(int i = 1; i <= c.s[0]; i++) {
                     c.s[i] = b.s[i] - a.s[i];
                       if (c.s[i] < 0){
                           c.s[i] += MOD;
                           b.s[i + 1]--;
                    }
                }
            }
        }
        else{// b < 0
            if (b.cmp_abs(a) == 1){// |b| > |a|, |ans| = |b| - |a|
                c.flag = 1;
                c.s[0] = max(a.s[0], b.s[0]) + 1;
                for(int i = 1; i <= c.s[0]; i++) {
                     c.s[i] = b.s[i] - a.s[i];
                       if (c.s[i] < 0){
                           c.s[i] += MOD;
                           b.s[i + 1]--;
                    }
                }
            }
            else{//|b| <= |a|, |ans| = |a| - |b|
                c.flag = 0;
                c.s[0] = max(a.s[0], b.s[0]) + 1;
                for(int i = 1; i <= c.s[0]; i++) {
                     c.s[i] = a.s[i] - b.s[i];
                       if (c.s[i] < 0){
                           c.s[i] += MOD;
                           a.s[i + 1]--;
                    }
                }
            }
        }
        while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
        return c;
    }
    BIGNUM operator += (const BIGNUM &a){
        *this = *this + a;
        return *this;
    }
    BIGNUM operator - (const BIGNUM &B){
        BIGNUM c, a = *this, b = B;
        if ((!a.flag) && (!b.flag)){
            if (a >= b){
                c.flag = 0;
                c.s[0] = max(a.s[0], b.s[0]) + 1;
                for(int i = 1; i <= c.s[0]; i++) {
                     c.s[i] = a.s[i] - b.s[i];
                       if (c.s[i] < 0){
                           c.s[i] += MOD;
                           a.s[i + 1]--;
                    }
                }
            }
            else{
                c.flag = 1;
                c.s[0] = max(a.s[0], b.s[0]) + 1;
                for(int i = 1; i <= c.s[0]; i++) {
                     c.s[i] = b.s[i] - a.s[i];
                       if (c.s[i] < 0){
                           c.s[i] += MOD;
                           b.s[i + 1]--;
                    }
                }
            }
        }
        else{
            b.flag = !b.flag;
            c = a + b;
        }
        while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
        return c;
    }
    BIGNUM operator -= (const BIGNUM &a){
        *this = *this - a;
        return *this;
    }
    BIGNUM operator * (const BIGNUM &B){
        BIGNUM c, a = *this, b = B;
        c.init();
        if (!(a.flag || b.flag) || (a.flag && b.flag))
            c.flag = 0;
        else{
            if ((a.s[0] == 1 && a.s[1] == 0) || (b.s[0] == 1 && b.s[1] == 0))	c = 0;
            else	c.flag = 1;
        }
        c.s[0] = a.s[0] + b.s[0];
        for(int i = 1; i <= a.s[0]; i++) {
            int x = 0;
            for(int j = 1; j <= b.s[0]; j++) {
                c.s[i + j - 1] += a.s[i] * b.s[j] + x;
                x = c.s[i + j - 1] / MOD;
                c.s[i + j - 1] %= MOD;
            }
            c.s[i + b.s[0]] = x;
        }
        while (c.s[c.s[0]] > 0)	c.s[0]++;
        while (c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
        return c;
    }
    BIGNUM operator *= (const BIGNUM &a){
        *this = *this * a;
        return *this;
    }
    BIGNUM operator << (const int &a){
        for (int i = 0; i < a; i++){
            s[0]++;
            for (int j = s[0]; j > 0; j--){
                s[j] <<= 1;
            }
            for (int j = 1; j < s[0]; j++){
                if (s[j] >= MOD){
                    s[j] -= MOD;
                    s[j + 1]++;
                }
            }
            while(s[s[0]] == 0 && s[0] > 1) s[0]--;
        }
        return *this;
    }
    BIGNUM operator <<= (const int &a){
        *this = *this << a;
        return *this;
    }
    BIGNUM operator >> (const int &a){
        for (int i = 0; i < a; i++){
            for (int j = s[0]; j > 0; j--){
                if ((s[j]&1) && j != 1)	s[j - 1] += MOD;
                s[j] >>= 1;
            }
        }
        while(s[s[0]] == 0 && s[0] > 1) s[0]--;
        return *this;
    }
    BIGNUM operator >>= (const int &a){
        *this = *this >> a;
        return *this;
    }
    BIGNUM operator / (const BIGNUM &c){
        BIGNUM a = *this, b = c, temp, ans;
        ans.init();
        temp.init();
        ans = 0;
        temp = 1;
        bool sign;
        if (!(a.flag || b.flag) || (a.flag && b.flag) || cmp_abs(c) == -1)	sign = 0;
        else sign = 1; 
        a.flag = b.flag = 0;
        while (a >= b){
            b <<= 1;
            temp <<= 1;
        }
        while (temp.s[0] > 1 || temp.s[1]){
            if (a >= b){
                a -= b;
                ans += temp;
            }
            b >>= 1;
            temp >>= 1;
        }
        while (!ans.s[ans.s[0]] && ans.s[0] > 1)	ans.s[0]--;
        ans.flag = sign;
        return ans;
    }
    BIGNUM operator /= (const BIGNUM &a){
        *this = *this / a;
        return *this;
    }
    BIGNUM operator % (const BIGNUM &a){
        BIGNUM c = *this / a, d = c * a;
        return *this - d;
    }
    BIGNUM operator %= (const BIGNUM &a){
        *this = *this % a;
        return *this;
    }
};
ostream& operator << (ostream &out, const BIGNUM &a) {
    if (a.flag){
        out << '-';
    }
    out << a.s[a.s[0]];
    for(int i = a.s[0] - 1; i >= 1; i--)
        out << fixed << setfill('0') << setw(9) << a.s[i];
    return out;
}
istream& operator >> (istream &in, BIGNUM &a) {
    char str[LEN];
    in >> str;
    a = str;
    return in;
}

int main(){
    BIGNUM a, b;
    cin>>a>>b;
    cout<<a + b<<'\n';
    cout<<a - b<<'\n';
    cout<<a * b<<'\n';
    cout<<a / b<<'\n';
    cout<<a % b<<'\n';
    return 0;
}