6

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

我可以看到它正在完成的一种方法是通过递归算法不断划分直到你不能再划分，但这似乎并不有效。

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

4

4 回答 4

14

快速版本是：取决于硬件、优化器、是否被常数除（pdf）、是否有异常需要检查（例如，以 0 为模）、是否以及如何处理负数（这很可怕C++ 的问题）等...

R 为无符号整数提供了一个简洁明了的答案，但除非您精通 C，否则很难理解。

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

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

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

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

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

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

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

武装（无法抗拒）这些移位操作，我们可以进行如下操作：

  1. 找出我们可以乘以q但仍小于的 2 的最大幂p。
  2. 从 2 的最大幂到最小的幂，乘以q2 的每个幂，如果它小于剩下的p，则从剩下的 中减去p。
  3. 你剩下的就是剩下的了。

为什么这行得通？因为最后你会发现所有的 2 的减幂实际上总和为floor(p / q)！不要相信我的话，类似的知识已经知道很长时间了。

分解R的答案：

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

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

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

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

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

  1. (q<<i)是左位移位i。回想一下，这相当于乘以 2^ i。
  2. HI & (q<<i)执行按位与。由于HI仅填充了其最高位，因此只有在(q<<i)大到足以导致最高位非零时才会导致非零值。再向左移动一次，就会出现整数溢出。
  3. !(HI & (q<<i))(HI & (q<<i))为零时为“真”，否则为“假”。

do { if (p >= (q<<i)) p -= (q<<i); } while (i--);

这是一个简单的递减循环do { .... } while (i--);。请注意，使用后递减，i因此循环执行，然后它检查是否i不为零，然后从 中减去 1 i，然后如果其先前的检查导致true它继续。这具有循环执行其最后一次i为 0 时的属性。这很重要，因为我们可能需要剥离q.

if (p >= (q<<i))检查 2^ i*q是否小于或等于p. 如果是，则将其p -= (q<<i)剥离。

剩下的就剩下了。

于 2013-06-26T19:50:49.420 回答
5

虽然大多数 C 实现在具有除法指令的硬件上运行，但余数运算可以大致像这样执行，用于计算p%q，假设无符号值：

#define HI (-1U-(-1U/2))
unsigned i;
for (i=0; !(HI & (q<<i)); i++);
do { if (p >= (q<<i)) p -= (q<<i); } while (i--);

得到的余数在p.

于 2013-06-26T19:05:52.653 回答
2

正如R.. 建议的那样，除了使用移位的硬件指令和实现之外，还有倒数乘法。

当 的右侧%是一个常量时，可以使用这种技术，这在编译时是已知的。
倒数乘法用于实现除法，但使用它%很容易，基于公式a%b == a-(a/b)*b。

于 2013-06-26T19:27:06.287 回答
0

根据优化器的智能，有一个以 2 为模的快捷方式。例如，a % 32可以实现为a & 31. 一般来说，a % (2^N) == a & (2^N -1). 与除法相比，这快如闪电。大多数除法器（曾经的硬件）需要至少 1 个周期来计算结果的每一位，而逻辑与只是几个周期的操作（在流水线中）。

编辑：这仅在a未签名时才有效！

于 2013-07-01T16:38:49.067 回答