modulo - 如何在 C++ 中找到大数除法的余数？

Question

我对 C++ 中的模数有疑问。我试图做的是划分一个非常大的数字，例如，M % 2，其中 M = 54,302,495,302,423。但是，当我去编译时，它说这个数字对于 int 来说是“长”的。然后，当我将其切换为双精度时，它会重复相同的错误消息。有没有办法可以做到这一点，我可以得到这个非常大的数字的剩余部分，或者可能更大的数字？感谢您的帮助，非常感谢。

Answer 1

You can try storing the number in a "long long" (64 bit integral value), just be aware that if your application is multi-threaded and running on a 32-bit CPU you will need to synchronize between threads when reading/writing this value as it takes 2 clock cycles to read/write.

Alternatively, try a bignum library

If you want to make things interesting, if you are only ever doing modulo 2 you can check the lowest bit and get your answer. If you are only doing up to modulo 255 you can take the lowest 8 (unsigned char) bits and do the operation on them. If you are only doing up to modulo 65535 you can take the lowest 16 bits (unsigned short) and do the operation on them.

Answer 2

对于 C++ 中的大数运算，请使用GMP库。特别是，该mpz_mod函数将执行此操作。

对于更自然的 C++ 包装器，mpz_class该类可以通过为多精度操作提供运算符重载来提供帮助。

Answer 3

整数的范围仅从 –2,147,483,648 到 2,147,483,647。检查 http://msdn.microsoft.com/en-us/library/s3f49ktz(VS.71).aspx了解数据类型范围。我推荐长长的。

Answer 4

提示：使用链表。将数字动态存储为一组数字。例如：

112233445566778899001122 => 11223344 55667788 99001122

现在考虑单个单元并从左到右开始。找到提醒并操作它以添加到下一个组并继续。

现在实施非常容易:)

编辑：

112233445566778899001122/6 =>  11223344 55667788 99001122/6


 11223344/6 =>2

 2*100000000 + 55667788 = 255667788
 255667788/6 => 0
 0*100000000 + 99001122 = 99001122
 99001122/6=>0

 So the reminder is 0.

请记住，操作后的单个单元应该在 int 可以支持的最大范围之下。