如何在只有 32 位 int 的系统上模拟 256 位整数数学运算？
我想使用一系列（无符号）整数编写一个简单的 bignum 类。我可以大致了解加法和减法是如何工作的，但除法和乘法是另一回事。我知道 32 位编译器可以通过将 int64 拆分为两个 int32 来模拟 64 位 int。我正在寻找一种有效的方法来做到这一点。
我想要 C++ 代码，而不是汇编。速度不是主要问题，但无需组装的最有效解决方案总是很高兴。
I'd like to write a deadsimple bignum class using a series of (unsigned) integers. I can loosely see how addition and subtraction would work, but division and multiplication is another story. I know 32-bit compilers can emuate 64-bit int's by splitting the int64 in two int32's. I'm looking for an efficient method to do that.
I'd like to have C++ code, not assembly. Speed is no primary concern, but the most efficient solution without assemble is always nice to have.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
也许这可以作为一个起点。它使用以 65,536 为基数的表示形式，实现最多 2,048 位无符号整数。这意味着每个数字可以容纳 16 位，并且我们可以通过简单地使用 32 位作为结果来轻松检测溢出（即使在乘法时）。
然而，这是 C 代码，但移植到 C++ 应该很简单，或者只是用作灵感。它针对可读性而不是速度进行了非常优化，因为这不完全是我擅长的东西。 :)
Perhaps this can serve as a starting point. It implements up to 2,048-bit unsigned integers, using a base-65,536 representation. This means each digit fits in 16 bits, and we can trivially detect overflow (even when multiplying) by simply using 32 bits for the results.
This is C code however, but should be trivial to port to C++, or just use as an inspiration. It's very much optimized for readability rather than speed since this is not exactly the kind of stuff I'm good at. :)
您最好看看任意精度算术，它将解释该过程背后的想法模拟比代码运行时更高精度的处理器。
You'd best have a look at arbitrary precision arithmetic which will explain the thinking behind the process of emulating higher precision processors than then one that your code is running on.
购买一本名为 NUMERICAL RECIPES IN C++ 的精装书，您将在从第 20.6 页 p916 到 p925 的页面中找到您要查找的内容
Purchase a hardback book called NUMERICAL RECIPES IN C++ and you will find what you are looking for on pages starting on 20.6 page p916 onto to p925
只使用
long long有什么问题吗？这保证是在至少 64 位。否则，您的 Knuth（第 2 卷）应该提供基本的
算法。
What's wrong with just using
long long? That's guaranteed to be atleast 64 bits. Otherwise, your Knuth (vol. 2) should provide the basic
algorithms.
使用简单的字节数组。您可以拥有任何您想要的整数大小*。您只需以二进制进行操作并考虑字节顺序（您的位将为 7-6-5-4-3-2-1-0-15-14-13...）
*RAM 有限
Use simple byte array. You can have size of integer whatever you want*. You just have to operate in binary and take endianess into consideration (your bits will be 7-6-5-4-3-2-1-0-15-14-13...)
*RAM is limited
对于任意大小，请尝试GMP，它也应该适用于 32 位上的 64 位数学，如果出于某种原因你可以'不要依赖编译器来为你做这件事。
for arbitrary sizes, give GMP a spin, it should also work for your 64bit math on 32bit if for some reason you can't rely on the compiler to do it for you.