java - 为什么模3效率低下？

我有此代码here.，此代码称为“有效”，因为它比模3更有效。

但是为什么模3效率低下？它在下面不执行相同的操作吗？
模运算的复杂性是什么？

最佳答案

渐近复杂度显然是相同的（它是恒定时间）。另一方面，模2很容易以二进制形式实现。模3稍微复杂一些。

给定任何数字n，n % 2可以是0或1，因此您要做的就是保留最后一位的值。您可以使用一个非常简单的二进制AND来执行此操作：

n % 2 == n & 1

另一方面，如果您执行n % 3，则所有有效答案都是（二进制）00，01和10。请注意，现在答案跨越了两位。但是，并非所有两位数字都是有效的（二进制11不能是n % 3的结果）。因此，您需要执行额外的操作：

// 3DEC == 11BIN, so (n & 3) keeps the last two bits of n. You
// then have to ensure that these last two bits are not both 1.
n % 3 == n & 3, if (n & 3) != 3

我不知道模数3是如何在硬件中实现的，但是不管模数3是如何实现的，它都将比模数2稍微复杂一些。也就是说，认为您可以进行更有效的模数运算是很愚蠢的在软件方面要比在硬件中已经可用。