快速整除测试（2、3、4、5、..、16）？

Question

最快的可分性测试是什么？比如说，给定一个小端架构和一个 32 位有符号整数：如何快速计算出一个数字可以被 2、3、4、5、… 整除 16？

警告：给定的代码仅为示例。每条线都是独立的！在许多没有 DIV 硬件（如许多 ARM）的处理器上，使用模运算的明显解决方案很慢。一些编译器也无法进行此类优化（例如，如果除数是函数的参数或依赖于某些东西）。

 Divisible_by_1 = do();
Divisible_by_2 = if (!(number & 1)) do();
Divisible_by_3 = ?
Divisible_by_4 = ?
Divisible_by_5 = ?
Divisible_by_6 = ?
Divisible_by_7 = ?
Divisible_by_8 = ?
Divisible_by_9 = ?
Divisible_by_10 = ?
Divisible_by_11 = ?
Divisible_by_12 = ?
Divisible_by_13 = ?
Divisible_by_14 = ?
Divisible_by_15 = ?
Divisible_by_16 = if(!number & 0x0000000F) do();

和特殊情况：

 Divisible_by_2k = if(number & (tk-1)) do();  //tk=2**k=(2*2*2*...) k times

原文由 psihodelia 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

找出除法指令的替代方案（包括 x86/x64 上的模数）并不是一个坏主意，因为它们非常慢。比大多数人意识到的要慢（甚至慢得多）。那些建议 n 是变量的“% n”的人给出了愚蠢的建议，因为它总是会导致使用除法指令。另一方面，“% c”（其中 c 是一个常数）将允许编译器确定其曲目中可用的最佳算法。有时它会是除法指令，但很多时候不会。

在 本文档 中，Torbjörn Granlund 显示无符号 32 位 mults:divs 所需的时钟周期比在 Sandybridge 上为 4:26 (6.5x)，在 K10 上为 3:45 (15x)。对于 64 位，相应的比率为 4:92 (23x) 和 5:77 (14.4x)。

“L”列表示延迟。 “T”列表示吞吐量。这与处理器并行处理多条指令的能力有关。 Sandybridge 可以每隔一个周期发出一个 32 位乘法，或者每个周期发出一个 64 位乘法。对于 K10，相应的吞吐量是相反的。对于分区，K10 需要完成整个序列才能开始另一个序列。我怀疑 Sandybridge 也是如此。

以 K10 为例，这意味着在 32 位除法 (45) 所需的周期内，可以发出相同数量 (45) 的乘法，并且其中的倒数第二个和最后一个将完成一和二除法完成后的时钟周期。 45次乘法可以完成很多工作。

值得注意的是，随着从 K8-K9 到 K10 的演进，div 的效率变得更低了：从 39 到 45 以及 71 到 77 个时钟周期（对于 32 位和 64 位）。

Granlund 在 gmplib.org 和斯德哥尔摩 皇家理工学院 的 页面 包含更多好东西，其中一些已被纳入 gcc 编译器。

原文由 Olof Forshell 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

在每种情况下（包括可被 2 整除）：

 if (number % n == 0) do();

使用低位掩码进行与操作只是混淆，使用现代编译器不会比以可读方式编写代码快。

如果您必须测试所有案例，您可以通过将一些案例放在 if 中来提高性能：如果被 2 整除已经失败，那么测试被 4 整除是没有意义的，因为例子。

原文由 James Kanze 发布，翻译遵循 CC BY-SA 3.0 许可协议