c - C如何在内部执行%操作

Question

我很想了解 mod 操作背后的逻辑，因为我知道可以执行位移操作来执行不同的操作，例如位移到乘法。

我可以看到它正在完成的一种方法是通过递归算法，该算法不断除法，直到您不能再除法为止，但这似乎效率不高。

任何想法都会有所帮助。提前致谢!

Answer 1

快速版本是:取决于硬件，优化器，if it's division by a constant or not (pdf)，如果有异常要检查(例如模数为 0)，是否以及如何处理负数( this is a scary question for C++ )，等等...

R 对无符号整数给出了一个很好的、简洁的答案，但除非你精通 C，否则很难理解。

R 所阐明的技术的关键是去除 q 的倍数。直到不再有 q 的倍数左。我们可以用一个简单的循环天真地做到这一点:

while (p >= q) p -= q; // One liner, woohoo!

代码可能很短，但对于较大的 p 值和较小的 q 值，这可能需要很长时间。

比剥掉一个强 q一次会剥掉很多 q一次。请注意，我们实际上想要删除尽可能多的 q尽可能 - 即 floor(p/q)许多 q 's... 事实上，这是一种有效的技术。对于无符号整数，人们会期望 p % q == p - (p / q) * q . (请注意，无符号整数除法向下舍入。)

但这几乎感觉像是作弊，因为除法和余数运算是如此密切相关。 (事实上​​，通常如果硬件本身支持除法，它支持除法和计算余数运算，因为它们非常相关。)

假设我们无法进行除法，我们将如何找到 q 的倍数大于 1 剥离？在硬件中，固定移位操作很便宜(如果实际上不是免费的)并且在概念上表示乘以非负的 2 次幂。例如，将一个位串左移 3 相当于乘以 8(即 2^3)，例如5 十进制等效于“101”二进制。通过在右侧添加三个零(给出“101000”)以二进制形式移动“101”，结果是十进制的 50——八的五倍。

同样，移位操作作为软件操作非常便宜，您将很难快速找到不支持它们的 Controller 。 (一些架构，例如 ARM，甚至可以将移位与其他指令结合起来，使它们在很多时候“自由”。)

ARMed(无法抗拒)使用这些移位操作，我们可以进行如下操作:

找出我们可以相乘的两个最大幂 q通过并且仍然小于p .

从 2 的最大幂到最小幂，乘以 q按 2 的每个幂，如果小于 p从 p 的剩余部分减去它.

你剩下的就是剩下的。

为什么这样做？因为最后你会发现所有 2 的减幂实际上总和为 floor(p / q) !不要相信我的话，类似的知识已经为 very long time 所知。 .

打破 R 的答案:

#define HI (-1U-(-1U/2))

这有效地为您提供了一个仅设置了最高值位的无符号整数。

unsigned i;
for (i=0; !(HI & (q<<i)); i++);

这条线实际上找到了两个 q 的最高幂可以在溢出无符号整数之前相乘。这不是绝对必要的，但除了增加所需的执行时间外，它不会改变结果。

如果您不熟悉这一行中的 C-isms:

(q<<i)左移 i .回想一下，这相当于乘以 2^ i .

HI & (q<<i)执行按位与。自 HI仅填充其最高位，这只会在 (q<<i) 时导致非零值。大到足以导致最高位非零。再向左移动一次，就会出现整数溢出。

!(HI & (q<<i))当 (HI & (q<<i)) 时为“真”为零，否则为“假”。

do { if (p >= (q<<i)) p -= (q<<i); } while (i--);
这是一个简单的递减循环 do { .... } while (i--); .请注意，后递减用于 i所以循环执行，然后它检查是否 i不为零，则从 i 中减一，然后如果它之前的检查结果是 true它继续。这具有循环在 i 时执行其最后一次的属性。是 0。这很重要，因为我们可能需要删除 q 的未乘副本。 .
if (p >= (q<<i))检查 2^ i * q小于或等于 p .如果是， p -= (q<<i)剥离它。

剩下的就剩下了。