4

在 C 语言中，查看一个数是否可​​被另一个数整除的最佳方法是什么？我用这个：

if (!(a % x)) {
// this will be executed if a is divisible by x
}

反正有哪个更快吗？我知道做，即 130 % 13 将导致每 10 次做 130 / 13。所以有 10 个周期只需要一个（我只想知道 130 是否可以被 13 整除）。

谢谢！

4

5 回答 5

28

我知道做，即 130 % 13 将导致每 10 次做 130 / 13

梦呓。%在我用过的任何处理器上都没有这样的事情。它执行130/13一次，并返回剩余部分。

使用%. 如果您的应用程序运行太慢，请对其进行分析并修复太慢的问题。

于 2011-05-25T19:35:19.137 回答
8

对于两个任意数，最好的检查方法是检查是否a % b == 0. 模运算符根据硬件具有不同的性能，但是您的编译器可以比您更好地解决这个问题。模数运算符是通用的，您的编译器将为您运行的任何硬件找出最佳指令序列。

如果其中一个数字是常数，您的编译器可能会通过位移和减法的某种组合进行优化（主要针对 2 的幂），因为硬件 div/mod 比加法或减法慢，但在现代处理器上延迟（已经仅几纳秒）被大量其他性能技巧所隐藏，因此您不必担心。没有硬件通过重复除法计算模数（一些旧处理器通过重复位移和减法进行除法，但他们仍然为此使用专门的硬件，因此让硬件完成它仍然比尝试在软件中模拟它更快）。大多数现代 ISA 实际上在一条指令中计算除法和余数。

唯一可能有用的优化是除数是否为 2 的幂。然后，您可以使用&屏蔽低位（通过除数 - 1）并检查结果是否为零。例如，检查是否a可以被 8 整除，a & 7 == 0是等价的。一个好的编译器会为你做这件事，所以坚持坚持使用%.

于 2011-05-25T19:49:48.367 回答
6

在一般情况下，使用模运算符可能是最快的方法。有例外，特别是如果您对数字是否可以被 2 的幂整除感兴趣（在这种情况下可以使用按位运算），但如果您只使用%. 对于任意值，您不太可能做得更好，例如13.

另外，“每 10 次做 130 / 13”是什么意思？它做130 / 13一次。这正是所需要的。

于 2011-05-25T19:36:07.407 回答
3

如果x是一个常数，那么是的：

if (a * 0x4ec4ec4ec4ec4ec5 < 0x13b13b13b13b13b2) {
    // this will be executed if a is divisible by 13
}

0x4ec4ec4ec4ec4ec5是 13 的模乘逆（模 2 64），所以如果a真的是 13 的倍数，那么乘积将小于 (2 64 /13)。（因为 a 是某个 integer 的 13 倍n，并且n必须适合 64 位字，这意味着它小于 2 64。）

这仅适用于 的奇数值x。对于偶数（即y>0的 2 yy的倍数），您可以将此测试与按位与测试相结合（最后一位a应该为零。如果它们被除以a2 y并继续进行乘法测试。）

这仅在 是一个常数时才值得x，因为计算乘法逆比比整数除法更昂贵。

编辑：我也在假设a并且x没有签名。

于 2011-05-25T19:57:11.017 回答
0

当机器执行%除法指令时，它会自动生成余数。

但是，请注意，如果其中一个数字为负数，%则余数为负数。如果你只关心余数为零，这不是问题，但如果你碰巧在寻找另一个余数，比如 1，它真的会让你绊倒。

于 2011-05-25T23:02:22.857 回答