钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

支持负数的高精度模板

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

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

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

大整数的存储结构

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

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

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

操作符重载

输入输出流

因为我不会, 所以照抄的.
因为重载得放在结构体后面, 所以添加了一个函数(print())方便debug.

赋值

思路类似, 但是加上了正负号的处理, 同时做了一些小调整(为了保证能够完全读入, 所以牺牲一些效率放宽了读入的访问范围. 这里还能卡常不成?)

比较

因为考虑了正负数, 所以代码量直接翻倍.
基本思路如下: 首先考虑符号, 然后考虑位数, 最后逐位判断.
同时因为有符号, 所以添加了一个函数(cmp_abs())来进行绝对值的比较.

加减

因为只能使用已经重载过的运算符, 所以加法(先重载的加法)中就必须考虑正负了, 所以对每种情况都需要处理.
重载减法时因为加法是可用的, 所以对一些情况直接转换成加法即可.

乘法

模拟乘法竖式即可, 基本照抄.
添加了对正负号的处理: 同号或者一个为0显然结果是非负数, 异号显然结果是负数.

移位

原版中移位是有bug的, 当num不为1时得出的不一定是正确结果, 于是简单粗暴的套了一层num次的循环解决问题.

除法

原理是减法, 通过倍增优化, 主要还是增加了对正负号的处理, 同上.

有了乘除, 怎么实现不需要多说(其实是懒得写了)吧.

踩的坑

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

1
2
3
4
5
6
7
8
9
//正确操作
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 的值发生了改变.

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

奇奇怪怪的优化

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

1
2
3
4
//用异或实现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):

  • 修改输出流重载部分, 解决关闭同步后可能出现的问题.
  • 微调部分语句, 增加可读性.