c++ - 快速整除测试(2、3、4、5、..、16)？

Question

最快的整除测试是什么？比如说，给定一个 little-endian 架构和一个 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

Answer 1

在所有情况下(包括可被 2 整除):

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

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

如果你必须测试所有的情况，你可以通过将一些情况放在 if 中来提高性能:如果被 2 整除，那么测试被 4 整除是没有意义的例如，已经失败了。