我应该使用哪种数据结构来实现 BigInt 类？

Question

我想实现一个BigInt类，它可以处理非常大的数字。 我只想添加和乘以数字，但是该类还应处理负数。

我想将数字表示为字符串，但将字符串转换为int并进行加法会有很大开销。 我想按照高中的方式执行加法，在相应顺序上添加，如果结果大于10，则将进位添加到下一个顺序中。

然后我认为最好将其作为无符号长整型数组处理，并通过布尔值将符号分离。 在这种情况下，我担心int的大小，因为据我所知，C++标准仅保证int < float < double。 如果我达到某个数字，我应该向前移动数组并开始将数字添加到下一个数组位置。

是否有任何适合此问题的数据结构或更好的方法？

- user1086004

---

对我来说，这似乎是一个合理的实现。但是，如果您使用的是ULONGs，则数组中的每个元素可以保存从0到2^32-1的值，而不是从0到10。这应该可以为您节省一些字节。 :-) - Adam Liss

标准仅保证 float <= double（请注意等号）。 - ipc

是的，那正是我想表达的。但是在Linux和Solaris上，2^32 - 1是否相同？它们的大小是否保证在任何地方都一样？我的意思是，例如我得到了MyBigIntClass number = "234567434256547"; ，然后我开始将这个字符串数字转换为类中的内部表示，该表示为unsigned long long int（也许是:-)），并且当数字达到2^32时，我会移动到数组中的另一个位置。这样正确吗？ - user1086004

使用2的补码表示负数，而不是符号位。这样你就不需要特别处理有符号算术了。另外，如果你只是为了个人娱乐而这么做，那就继续吧（编写一个大整数类确实很有趣，尤其是通过FFT进行乘法和使用牛顿方法进行除法）。如果你只需要一个可用的大整数类，请看一下优秀的Gnu MP库（以及相关的MPFR）。 - Alexandre C.

我正在做作业。希望我不需要除法 :-) - user1086004

Answer 1

所以，你想要一个已知大小的整数动态数组？

听起来像是vector<uint32_t>适合你。

- Joni

---

不幸的是，STL 不被允许。 - user1086004

作业？嵌入式？无论如何，您都需要类似于“向量”的东西。幸运的是，重新创建基本的“动态数组”是一个简单的练习。 - Joni

Answer 2

正如你已经发现的那样，你将需要在你的平台（或者如果你使用C++11，则为语言）中使用具有固定大小的特定类型。一个常见的大数实现会使用32位整数，并确保只设置了较低的16位。这使你可以在“数字”上进行操作（其中数字将是[0..2^16)），然后通过应用进位来“标准化”结果。

- David Rodríguez - dribeas

---

对于加法/减法，可以一路上进行进位，并且不需要两次操作。对于乘法，这取决于算法，但如果你使用浮点FFT方法，也不需要进位（但最好使用16位的“数字”，因为在FFT过程中会积累舍入误差）。 - Alexandre C.

Answer 3

在现代的64位x86平台上，最好的方法可能是将您的bigint作为无符号32位整数的动态分配数组存储，以便您的算术可以适应64位。您可以将您的符号单独处理为类的成员变量，或者您可以使用2的补码算术（这是signed int通常表示的方式）。

标准C <stdint.h>包含文件定义了uint32_t和uint64_t，因此您可以避免平台相关的整数类型。或者（如果您的平台没有提供这些），您可以自己定义这种类型的东西 - 最好在单独的"platform_dependent.h"文件中...

- comingstorm

---

2 的补码对于动态长度的大整数来说并不容易实现（而且效果不是很好），但我同意其余部分。 - Sopel