什么是最快的除数测试？假设有一个低端字节序的体系结构和一个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
最佳答案
找出除法指令的替代方案(包括x86/x64上的模数)非常好，因为它们的速度很慢。比大多数人意识到的要慢(甚至慢得多)。那些建议使用“％n”(其中n是变量)的人给出了愚蠢的建议，因为它总是会导致使用除法指令。另一方面，“％c”(其中c是常数)将允许编译器确定其指令集中可用的最佳算法。有时，这将是除法指令，但在很多时候却不是。
TorbjörnGranlund在this document中显示，无符号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需要先完成整个序列，然后才能开始另一个序列。我怀疑桑迪布里奇也是如此。
以K10为例，这意味着在32位除法(45)所需的周期内，可以发出相同数量(45)的乘法，并且倒数第二个和最后一个将完成一个和两个除法完成后的时钟周期。可以用45次乘法执行很多工作。
有趣的是，随着K8-K9到K10的演进，div的效率降低了:32位和64位从39到45和71到77个时钟周期。
Granlund在gmplib.org上和斯德哥尔摩的page上的Royal Institute of Technology包含更多的功能，其中一些功能已合并到gcc编译器中。
关于c++ - 快速的除数测试(乘2,3,4,5，..，16)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6896533/