本来以为会跑的飞快…没想到竟然慢成这样…真是丢人…

其实刚刚开始学 OI 的时候就一直有这样的想法，写一个基于 std::bitset 的高精（并且幻想它能跑的很快）。但是但是姿势水平还是不足，不会类模板的一套操作，也不懂补码之类的，手写原码硬刚，最后当然是死得很惨（雾）。

思路

大概是用 std::bitset 来存一个很长的二进制位，先实现一个 basic_uint ，然后考虑到补码的美妙性质，可以很轻松地派生出 u 和 i ，他们的数学运算是完全相同的。

数学运算

加减

这个没啥好说的，加法可以按位操作，而 a - b 就是 a + (~b + 1)：

    friend basic_uint<l> operator+(const basic_uint<l> &a, const basic_uint<l> &b) {
      basic_uint<l> res;
      unsigned int inc = 0;
      for (size_t i = 0; i < l; ++i) {
        res.data[i] = a.data[i] ^ b.data[i] ^ inc;
        inc = (a.data[i] + b.data[i] + inc) >= 2 ? 1 : 0;
      }
      return res;
    }

    friend basic_uint<l> operator-(const basic_uint<l> &a, const basic_uint<l> &b) {
      return (a + (~b + basic_uint<l>(1)));
    }

乘除

我是写的暴力乘法…然后就乘法最慢，真是丢人…而除法就是普通的长除法。

关系运算

只需要实现等于号和小于号即可，其他的都可以用他俩组合出来。

进制转换

这个大概是这个东西里难度最高的部分了。

dec2bin

这个其实海星，只需要对一个字符串不断除 2 就星。

bin2dec

这个麻烦一点，我开始的时候写了一个 naïve 的除 10 取余的做法，结果慢到怀疑人生。遂上网搜索，学到了一个叫做 Double Dabble 的玄妙算法，它通过奇妙的位移和加法操作，可以把一个二进制数转化成 BCD 码，也就是每四个二进制位表示一个十进制数。

Benchmark

ms / op: test on i1024
plus:0.094
minus:0.176
multiply:43.74
division:0.53
to_string:33.35

====================================================

ms / op: test on u1024
plus:0.088
minus:0.176
multiply:43.08
division:0
to_string:33.01

Link

仓库链接：https://github.com/Enter-tainer/libinteger