C++大整数类的设计与实现

1. 简介

我们知道现代的计算机大多数都是64位的，因此能处理最大整数为$2^{64}-1$。那如果是超过了这个数怎么办呢，那就需要我们自己手动模拟数的加减乘除了。

2. 思路

我们可以用一个数组来存储大数，数组中的每一个位置表示一个数位。为了方便，我们直接用$STL$中的vector来存。

2.1 大数加法

我们需要把两个大数的最低位对齐，然后再开始相加。唯一需要注意的是处理一下最高位置的进位置。

2.2 大数减法

大数减法跟加法不一样的是，我们需要处理相减后的前导0，因为有可能出现相减为0的情况。处理前导0只需要从最高位开始到第2位的连续0。

2.3 大数乘法

大数乘法与加法不同的是，每次相乘后放到相应的位置而不是相乘的位次本身。

2.4 大数除法

大数除法是最难的，我们用减法进行模拟。

假设两个大数为$ab$， $a$为除数，$b$为被除数。

我们每次需要找到最接近被除数的除数的进制次倍数$m$：

D 0 : = { d : a × 1 0 d ≤ b } d 0 = max ⁡ { D 0 } m 0 = a × 1 0 d 0 D_0 := \{d: a\times 10^d \le b\}\\ d_0 =\max \{D_0\}\\ m_0=a \times 10^{d_0} D0​:={d:a×10d≤b}d0​=max{D0​}m0​=a×10d0​
通过大数减法算出$t_0=\lfloor b/m_0\rfloor$, 因此商需要加上$ans=ans+t_{0}10^{d_0}$。

此时余数为$b_1$，如果$b_1<a$，说明我们的除法做完了，否则令$b=b_1$, 继续重复上面的过程直到$b_k<a$。

2.5 符号问题

我们在加减乘除的时候，

可以将符号问题单独考虑。

因此可以写一个绝对值的大数相加，还有一个版本

的一个大的大数减一个小的大数的大数减法。

而至于乘除法的符号问题比较容易处理，因此可以

一同处理符号的问题。

3. 实现

放在gitee上了。

4. TODO

• 更加丰富的测试样例
• 加减乘除未兼容普通整数
• 大数除法中的负数的商不是最小非负余数