封装 BigInt 的伟大计划

大眼仔Happy · 2024-10-13 08:22:43 · 科技·工程

Preface

~~来一点对 OI 没有一点用的垃圾~~。

没有任何多项式科技。

适用于长度在 10 ^ 4 以内。

正文

喜欢的请点赞并收藏喵。

第一次封装 BigInt 失败了，卷土重来。

这次吸取失败的经验，并且借助 AI 的力量，直接是写了出来。

由于篇幅过长，下面只给出函数的声明，最后会给出 link。

首先仿照 bitset<N>，定义 BigInt<N> 为 N\times 32 位的有符号整型。

template <size_t N>
class BigInt {};

为了下面方便，可以重载一下 []，直接调用 bit。

static constexpr size_t n = N;
uint32_t bit[N];
uint32_t &operator [](size_t index);
const uint32_t &operator [](size_t index) const;

然后最高位是符号位，我们也写一个 sign() 来求出符号，1 表示负，0 表示正。

static bool sign(const BigInt &x);

接下来先写最简单的无参数构造函数，默认是全部为 0。

BigInt();

然后写取反和取负，由于储存的是补码，所以取负等于取反 +1。

BigInt operator ~() const;
BigInt operator -() const;

然后就可以接受 int/long long 类型的构造了。

BigInt(int x);
BigInt(long long x);

接下来是 string 和 BigInt 的互相转换的辅助函数，这为我们接受 string 的构造和输入输出提供便利帮助。

注意使用 static。

static BigInt StringToBigInt(const string &str);
static string BigIntToString(BigInt num);

接受 string 的构造和输入输出流的重载。

BigInt(const string &str);
friend istream& operator >> (istream &in, BigInt &x);
friend ostream& operator << (ostream &out, const BigInt &x);

接下来封装其他的位运算。

BigInt& operator &= (const BigInt &o);
BigInt operator & (const BigInt &o) const;
BigInt& operator |= (const BigInt &o);
BigInt operator | (const BigInt &o) const;
BigInt& operator ^= (const BigInt &o);
BigInt operator ^ (const BigInt &o) const;
BigInt& operator <<= (size_t shift);
BigInt& operator >>= (size_t shift);
BigInt operator << (const size_t &o) const;
BigInt operator >> (const size_t &o) const;

然后是比较运算的封装：

bool operator == (const BigInt &o) const;
bool operator != (const BigInt &o) const;
bool operator < (const BigInt &o) const;
bool operator > (const BigInt &o) const;
bool operator <= (const BigInt &o) const;
bool operator >= (const BigInt &o) const;

加减乘的运算比较简单，直接做无符号运算就对了。

这是因为 -x 的补码相当于 2^{32\times N} - x，两者在 \bmod 2^{32\times N} 是等价的。所以在 \bmod2^{32\times N} 的这个同余系里面就是可以直接算的。

BigInt& operator += (const BigInt &o);
BigInt operator + (const BigInt &o) const;
BigInt& operator -= (const BigInt &o);
BigInt operator - (const BigInt &o) const;
BigInt& operator ++ ();
BigInt operator ++ (int);
BigInt& operator -- ();
BigInt operator -- (int);
BigInt& operator *= (const BigInt &o);
BigInt operator * (const BigInt &o) const;

除法和取模比较复杂，首先是还得考虑符号位的影响，然后转化成非负整数才能做。

BigInt& operator /= (const BigInt &o);
BigInt operator / (const BigInt &o) const;
BigInt& operator %= (const BigInt &o);
BigInt operator % (const BigInt &o) const;

当然了，有时候还需要高精乘单精，高精除单精，高精模单精，于是这些都封装了。

注意暂时没有封装 long long / uint64_t 的。

BigInt& operator *= (const uint32_t &o);
BigInt operator * (const uint32_t &o) const;
BigInt& operator *= (int o);
BigInt operator * (const int &o) const;
BigInt& operator /= (const uint32_t &o);
BigInt operator / (const uint32_t &o) const;
BigInt& operator /= (int o);
BigInt operator / (const int &o) const;
BigInt& operator %= (const uint32_t &o);
BigInt operator % (const uint32_t &o) const;
BigInt& operator %= (int o);
BigInt operator % (const int &o) const;

于是就封装完成了！

完整代码：link

测试正确性：

typedef BigInt<4> i128; 
i128 a, b; 
int main() {
    cin >> a >> b; 
    cout << a + b << ' ' << a - b << ' ' << a * b << ' ' << a / b << ' ' << a % b << '\n';
    cout << (a << 2) << ' ' << (a >> 2) << '\n';
    cout << (a & b) << ' ' << (a | b) << ' ' << (a ^ b) << '\n';
    if(a % b == (a - a / b * b)) cout << "Yes";
    else cout << "No";
    return 0;
}
/*
in : 
101 22

out :
123 79 2222 4 13
404 25
4 119 115
Yes
*/

实战：

国王游戏：record。
Super GCD：record