我应该使用什么数据结构来创建我自己的“BigInteger”班级？
作为一项可选作业，我正在考虑编写自己的 BigInteger 类实现，其中我将提供自己的加法、减法、乘法等方法。
这将适用于任意长的整数，甚至数百位数字长。
在对这些数字进行数学计算时，逐位计算并不难，您认为最好的数据结构是什么来表示我的“BigInteger”？
起初我正在考虑使用数组，但后来我想在大的加法或乘法之后我仍然可能会溢出（用完数组槽）。这是使用链表的好例子吗，因为我可以以 O(1) 时间复杂度添加数字？
是否有其他数据结构比链表更适合？我的数据结构所保存的类型应该是我可用的最小可能的整数类型吗？
另外，我应该小心如何存储我的“进位”变量吗？它本身应该是我的“BigInteger”类型吗？
As an optional assignment, I'm thinking about writing my own implementation of the BigInteger class, where I will provide my own methods for addition, subtraction, multiplication, etc.
This will be for arbitrarily long integer numbers, even hundreds of digits long.
While doing the math on these numbers, digit by digit isn't hard, what do you think the best datastructure would be to represent my "BigInteger"?
At first I was considering using an Array but then I was thinking I could still potentially overflow (run out of array slots) after a large add or multiplication. Would this be a good case to use a linked list, since I can tack on digits with O(1) time complexity?
Is there some other data-structure that would be even better suited than a linked list? Should the type that my data-structure holds be the smallest possible integer type I have available to me?
Also, should I be careful about how I store my "carry" variable? Should it, itself, be of my "BigInteger" type?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
请参阅 David R. Hanson 所著的C 接口和实现一书。它有 2 章介绍该主题，涵盖向量结构、字大小以及您可能遇到的许多其他问题。
它是为 C 编写的，但大部分适用于 C++ 和/或 Java。如果您使用 C++，它会更简单一些，因为您可以使用 std::vector 之类的东西来为您管理数组分配。
Check out the book C Interfaces and Implementations by David R. Hanson. It has 2 chapters on the subject, covering the vector structure, word size and many other issues you are likely to encounter.
It's written for C, but most of it is applicable to C++ and/or Java. And if you use C++ it will be a bit simpler because you can use something like
std::vectorto manage the array allocation for you.始终使用能够完成您需要的工作的最小 int 类型（字节）。链表应该可以很好地工作，因为您不必担心溢出。
Always use the smallest int type that will do the job you need (bytes). A linked list should work well, since you won't have to worry about overflowing.
如果您使用二叉树（其叶子是整数），您可以通过更简单的分而治之算法获得链表的所有优点（无限数量的数字等）。在这种情况下，你没有一个基础，而是有很多基础，具体取决于你工作的级别。
如果这样做，则需要使用 BigInteger 进行进位。您可能会认为“整数链表”方法的一个优点是进位始终可以表示为 int（这对于任何基数都是如此，而不仅仅是基数 10，因为大多数答案似乎都假设您应该使用。 .. 在任何基数中，进位始终是个位数）
我不妨这样说：当您可以使用 2^30 或 2^31 时，使用基数 10 将是一种可怕的浪费。
If you use binary trees (whose leaves are ints), you get all the advantages of the linked list (unbounded number of digits, etc) with simpler divide-and-conquer algorithms. You do not have in this case a single base but many depending the level at which you're working.
If you do this, you need to use a BigInteger for the carry. You may consider it an advantage of the "linked list of ints" approach that the carry can always be represented as an int (and this is true for any base, not just for base 10 as most answers seem to assume that you should use... In any base, the carry is always a single digit)
I might as well say it: it would be a terrible waste to use base 10 when you can use 2^30 or 2^31.
访问链表的元素很慢。我认为数组是可行的方法，可以根据需要进行大量边界检查和运行时数组大小调整。
澄清：遍历链表和遍历数组都是 O(n) 操作。但是遍历链表需要在每一步引用一个指针。仅仅因为两种算法都具有相同的复杂性，并不意味着它们都需要相同的运行时间。即使必须调整数组大小，在链表中分配和释放 n 个节点的开销也会比单个大小为 n 的数组的内存管理要重得多几次。
Accessing elements of linked lists is slow. I think arrays are the way to go, with lots of bound checking and run time array resizing as needed.
Clarification: Traversing a linked list and traversing an array are both O(n) operations. But traversing a linked list requires deferencing a pointer at each step. Just because two algorithms both have the same complexity it doesn't mean that they both take the same time to run. The overhead of allocating and deallocating n nodes in a linked list will also be much heavier than memory management of a single array of size n, even if the array has to be resized a few times.
哇，这里有一些……有趣的答案。我建议你读一本书，而不是试图整理所有这些相互矛盾的建议。
也就是说，C/C++ 也不适合这项任务。大整数是一种扩展精度数学。大多数 CPU 提供指令来以与普通数学相当或相同的速度（每条指令位数）处理扩展精度数学。当你添加 2^32+2^32 时，答案是 0…但是处理器的 ALU 也有一个特殊的进位输出，程序可以读取和使用它。
C++ 无法访问该标志，C 中也没有办法。你必须使用汇编程序。
为了满足好奇心，您可以使用标准布尔算术来恢复进位等。但是下载现有的库会更好。
Wow, there are some… interesting answers here. I'd recommend reading a book rather than try to sort through all this contradictory advice.
That said, C/C++ is also ill-suited to this task. Big-integer is a kind of extended-precision math. Most CPUs provide instructions to handle extended-precision math at comparable or same speed (bits per instruction) as normal math. When you add 2^32+2^32, the answer is 0… but there is also a special carry output from the processor's ALU which a program can read and use.
C++ cannot access that flag, and there's no way in C either. You have to use assembler.
Just to satisfy curiosity, you can use the standard Boolean arithmetic to recover carry bits etc. But you will be much better off downloading an existing library.
我会说一个整数数组。
I would say an array of ints.
数组确实是很自然的选择。我认为当你的内存空间不足时，抛出 OverflowException 是可以接受的。老师会看到对细节的关注。
乘法大约使数字加倍，加法最多增加 1。很容易创建一个足够大的数组来存储运算结果。
乘法中进位最多是一位长数（9*9 = 1，进位8）。一个 int 就可以了。
An Array is indeed a natural fit. I think it is acceptable to throw OverflowException, when you run out of place in your memory. The teacher will see attention to detail.
A multiplication roughly doubles digit numbers, addition increases it by at most 1. It is easy to create a sufficiently big Array to store the result of your operation.
Carry is at most a one-digit long number in multiplication (9*9 = 1, carry 8). A single int will do.
std::vector或std::vector可能是您想要的。您必须对它们进行push_back()或resize()，因为您需要更多空间进行乘法等。另外，如果您需要，请记住 Push_back 正确的符号位使用两个赞美。std::vector<bool>orstd::vector<unsigned int>is probably what you want. You will have topush_back()orresize()on them as you need more space for multiplies, etc. Also, remember to push_back the correct sign bits if you're using two-compliment.我会说一个std::char的向量（因为它只需要保存0-9）（如果你打算使用BCD）
如果不是BCD，那么使用int的向量（你没有说清楚）
要少得多的空间开销链接列表
所有建议都说“使用向量，除非你有充分的理由不使用向量”
i would say a std::vector of char (since it has to hold only 0-9) (if you plan to work in BCD)
If not BCD then use vector of int (you didnt make it clear)
Much less space overhead that link list
And all advice says 'use vector unless you have a good reason not too'
根据经验，请使用
std::vector而不是std::list，除非您需要经常在序列中间插入元素。向量往往速度更快，因为它们是连续存储的，因此受益于更好的空间局部性（现代平台上的主要性能因素）。确保使用适合平台的元素。如果您想与平台无关，请使用
long。请记住，除非您有一些特殊的编译器内在函数可用，否则您将需要至少两倍大的类型来执行乘法。我不明白为什么你希望进位是一个大整数。加法的进位是单个位，乘法的进位是元素大小。
请务必阅读 Knuth 的《计算机编程艺术》，其中大量描述了与任意精度算术相关的算法。
As a rule of thumb, use
std::vectorinstead ofstd::list, unless you need to insert elements in the middle of the sequence very often. Vectors tend to be faster, since they are stored contiguously and thus benefit from better spatial locality (a major performance factor on modern platforms).Make sure you use elements that are natural for the platform. If you want to be platform independent, use
long. Remember that unless you have some special compiler intrinsics available, you'll need a type at least twice as large to perform multiplication.I don't understand why you'd want carry to be a big integer. Carry is a single bit for addition and element-sized for multiplication.
Make sure you read Knuth's Art of Computer Programming, algorithms pertaining to arbitrary precision arithmetic are described there to a great extent.