计算机如何求模数？
有一些很酷的按位运算算法吗？
Is there some cool algorithm with bit wise operations?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
有一些很酷的按位运算算法吗？
Is there some cool algorithm with bit wise operations?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（6）
通常，处理器上的模数和除法运算是同一件事。例如，请参阅 http://jsimlo.sk/docs/cpu/index。 php/div.html 。这是 Intel 处理器上除法指令的实现。
Often, the modulus and divide operations on a processor are the same thing. For instance, refer to http://jsimlo.sk/docs/cpu/index.php/div.html . This is the implementation of the divide instruction on Intel processors.
大多数时候，模数只是通过将两个数字相除来计算的。商存储在一个寄存器中，余数存储在另一寄存器中。你会去追求剩下的。
Most of the time, modulus is just computed by dividing the two numbers. The quotient is stored in one register, and the remainder is stored in the other register. You would go after the remainder.
如果预先知道除数（例如，对于 C 编译器生成的代码，这是在编译时已知的常数），则整数除法（从中可以轻松获得模数）有时可以通过乘法和移位来实现。请参阅本文了解详细信息（警告：这不是轻松阅读）。
在许多处理器中，整数乘法比整数除法快得多；有些处理器甚至没有整数除法操作码（n 位值的乘法可以优化为深度 O(log n) 的电路，而没有已知的优化深度低于O(n)）的除法电路的方法。
If the divisor is known in advance (e.g. for code produced by a C compiler, this is a constant known at compile time) then integer division (from which the modulus can be easily obtained) can sometimes be implemented with a multiplication and a shift. See this article for details (warning: this is not light reading).
In many processors, integer multiplication is vastly faster than integer division; some processors do not even have an integer division opcode (multiplication on n-bit values can be optimized into a circuit of depth O(log n), whereas there is no known method to optimize a division circuit below a depth of O(n)).
除了上面提到的使用
DIV和IDIV（对于 x86）的明显方法之外，任何数字以 2 的幂为模的结果都可以通过以下方式计算：按位与：x mod y（其中 y 是 pow2）与x AND (y - 1)相同。大多数编译器都会在可能的情况下执行此操作，因为除法比按位运算要昂贵得多Apart from the obvious method using
DIVandIDIV(for x86) as mentioned above, the result of any number modulo'd by a power of two can be calculated by taking the bitwise and:x mod ywhere y is pow2 is the same asx AND (y - 1). Most compilers perform this when possible, as division is far more expensive than bitwise opsx mod y = x - y*(x/y)
其中 (x/y) 是整数除法。
x mod y = x - y*(x/y)
where (x/y) is an integer divide.
检查模 2 也很容易，因为通常只需要检查最低有效位。
引用维基百科：
Also checking the modulo 2 is easy, as it only need to check the least significant bit, usually.
Quoting wikipedia: