在 C 语言中，查看一个数字是否可以被另一个数字整除的最佳方法是什么？

Question

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

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

有没有更快的？我知道，执行 130 % 13 将导致每 10 次执行 130 / 13。所以有 10 个循环，而只需要一个（我只是想知道 130 是否能被 13 整除）。

谢谢！

Answer 1

我知道做 130 % 13 会导致每 10 次做 130 / 13

胡言乱语。

%

在我用过的任何处理器上都没有这样做。它执行

130/13

一次，然后返回余数。

使用

%

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

Answer 2

对于两个任意数字，最好的检查方法是检查是否

a % b == 0

。根据硬件的不同，模运算符具有不同的性能，但您的编译器可以比您更好地解决这一问题。模运算符是通用的，您的编译器将找出为您运行的任何硬件发出的最佳指令序列。

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

唯一可能有用的优化是除数是否为 2 的幂。然后，您可以使用 & 屏蔽低位（除数 - 1）并检查结果是否为零。例如，要检查

a

是否能被 8 整除，

a & 7 == 0

是等效的。一个好的编译器会为你做这件事，所以坚持使用

%

。

Answer 3

%

，编译器应该自动为您选择它们。对于任意值（例如

13

），您不太可能做得更好。另外，“每 10 次做 130 / 13”是什么意思？它会

130 / 13

一次。这正是所需要的。

Answer 4

x

是常数，那么是：

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

0x4ec4ec4ec4ec4ec5

是 13 的

模乘法逆

（模 264），因此如果 ^a 确实是 13 的倍数，那么乘积将小于 (2

64

/13)。 （因为 a 是某个整数 ⁿ 的 13 倍，并且

n

必须适合 64 位字，这意味着它小于 2

64

。） 这只适用于

x

的奇数值。对于偶数（即 y>0 时 2

y

的倍数），您可以将此测试与按位与测试结合起来（^y 的最后

a

位应为零。如果它们除以

a

2

y

并继续乘法测试。） 仅当

x

是常数时才值得，因为计算乘法逆元比整数除法更昂贵。

---

编辑

：我还假设a和

x

未签名。

Answer 5

%

时，它只是执行除法指令，并自动生成余数。

但是

，请注意，如果其中一个数字为负数，% 将给出负余数。 如果你只关心余数为零，这不是问题， 但如果你碰巧正在寻找另一个余数，比如 1，它真的会让你陷入困境。

Answer 6

// 如果 a 能被 x 整除，则执行此操作

}