为什么模3是低效的？

Question

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

但是为什么模3是低效的呢？它不是在下面做同样的操作吗？模运算的复杂度是多少？

Answer 1

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

给定任意数字n，n % 2可以是0或1，所以您所要做的就是保留最后一位的值。您可以使用一个非常简单的二进制文件来实现这一点：

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是如何在硬件中实现的，但不管它是如何实现的，它都会比模2稍微复杂一些。也就是说，认为你可以在软件中实现比硬件中已有的更有效的模运算是愚蠢的。

Answer 2

在汇编级，模数是用指令DIV实现的，对于大数来说，它比使用逻辑运算、移位和分支要慢。

DIV指令(和它对应的有符号数的IDIV指令)同时给出商和余数(模数)。

r16通过16位操作数在DX:AX中搜索32位数，并将商存储在AX中，将余数存储在DX中。DIV

Answer 3

不是在下面做同样的操作吗？

不会，因为代码不正确:使用输入21尝试一下，它将返回false。但是，21 % 3是0。

21是0b10101。这意味着链接的算法在while循环之后有oddCtr = 3和evenCtr = 0。因为3 != 0，所以算法返回false。