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

Which is the best way, in C, to see if a number is divisible by another?

提问by Joseph

Which is the best way, in C, to see if a number is divisible by another? I use this:

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

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

Is there anyway which is faster? I know that doing, i.e, 130 % 13 will result into doing 130 / 13 per 10 times. So there are 10 cycles when just one is needed (I just want to know if 130 is divisible by 13).

无论如何，哪个更快？我知道这样做，即 130 % 13 会导致每 10 次做 130 / 13。所以当只需要一个循环时有 10 个循环（我只想知道 130 是否可以被 13 整除）。

Thanks!

谢谢！

回答by Rob?

I know that doing, i.e, 130 % 13 will result into doing 130 / 13 per 10 times

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

Balderdash. %does no such thing on any processor I've ever used. It does 130/13once, and returns the remainder.

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

Use %. If your application runs too slowly, profile it and fix whatever is too slow.

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

回答by Hoa Long Tam

For two arbitrary numbers, the best way to check is to check whether a % b == 0. The modulus operator has different performance based on the hardware, but your compiler can figure this out much better than you can. The modulus operator is universal, and your compiler will figure out the best sequence of instructions to emit for whatever hardware you're running on.

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

If one of the numbers is a constant, your compiler might optimize by doing some combination of bit shifts and subtractions (mostly for powers of two), since hardware div/mod is slower than addition or subtraction, but on modern processors the latency (already only a few nanoseconds) is hidden by tons of other performance tricks, so you needn't worry about it. No hardware computes modulus by repeated division (some old processors did division by repeated bit shifts and subtraction, but they still used specialized hardware for this, so it's still faster to have the hardware do it than to try to emulate it in software). Most modern ISAs actually compute both division and remainder in one instruction.

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

The only optimization that mightbe useful is if the divisor is a power of two. Then you can use &to mask the low-order bits (by divisor - 1) and check the result against zero. For example, to check if ais divisible by 8, a & 7 == 0is equivalent. A good compiler will do this for you, so stick with just stick with %.

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

回答by bdonlan

In the general case, using the modulo operator is likely to be the fastest method available. There are exceptions, particularly if you are interested in whether numbers are divisible by powers of two (in which case bitwise operations are available), but the compiler should choose them automatically for you if you just use %. You are unlikely to be able to do any better for arbitrary values such as 13.

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

Also, what do you mean by "doing 130 / 13 per 10 times"? It does 130 / 13once. Which is exactly what is required.

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

回答by finnw

If xis a constant, then yes:

如果x是常数，则是：

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

0x4ec4ec4ec4ec4ec5is the modular multiplicative inverseof 13 (modulo 2⁶⁴), so if ais really a multiple of 13 then the product will be less than (2⁶⁴/13). (Because a is 13 times some integer n, and nmust have fit into a 64-bit word which implies that it was less than 2⁶⁴.)

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

This only works for odd values of x. For even numbers (i.e. multiples of 2^yfor y>0) you can combine this test with a bitwise-AND test (the last ybits of ashould be zero. If they are then divide aby 2^yand proceed with the multiplication test.)

这仅适用于 的奇数值x。对于偶数（即2的倍数^Ÿ你可以用位与测试这个测试结合起来，Y> 0）（最后y的位a应该是零。如果他们再除以a2 ^Ÿ与乘法测试继续进行。）

This is only worthwhile if xis a constant, because computing the multiplicative inverse is more expensive than integer division.

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

---

---

Edit: I am also assuming aand xare unsigned.

编辑：我也假设a并且x未签名。

回答by Mike Dunlavey

When the machine does %it just does a division instruction, and that automatically generates a remainder.

当机器这样做时，%它只执行除法指令，然后自动生成余数。

However, be aware that if one of the numbers is negative, %will give a negative remainder. If you only care about a remainder of zero, this is not a problem, but if you happen to be looking for another remainder, like 1, it can really trip you up.

但是，请注意，如果其中一个数字为负，%则余数为负。如果您只关心 0 的余数，这不是问题，但是如果您碰巧正在寻找另一个余数，例如 1，它真的会让您失望。