确定整数是否在具有已知值集的两个整数（包括）之间的最快方法

Question

确定整数是否在具有已知值集的两个整数（包括）之间的最快方法是否有比x >= start && x <= endC或C ++ 更快的方法来测试整数是否在两个整数之间？

Answer 1

只用一个比较/分支就可以做到这一点。它是否能真正提高速度可能会受到质疑，即使它确实如此，它可能太少注意或不关心，但当你只是开始两次比较时，巨大改进的可能性非常小。代码如下：

// use a < for an inclusive lower bound and exclusive upper bound

// use <= for an inclusive lower bound and inclusive upper bound

// alternatively, if the upper bound is inclusive and you can pre-calculate

//  upper-lower, simply add + 1 to upper-lower and use the < operator.

    if ((unsigned)(number-lower) <= (upper-lower))

        in_range(number);

对于典型的现代计算机（即使用二进制补码的任何东西），转换为无符号实际上是一个不必要的 - 只是改变了相同位的查看方式。

请注意，在典型情况下，您可以upper-lower在（假定的）循环之外预先计算，因此通常不会贡献任何重要时间。随着减少分支指令的数量，这也（通常）改进了分支预测。在这种情况下，无论数字是低于底端还是高于范围的顶端，都会采用相同的分支。

至于它是如何工作的，基本思路非常简单：当被视为无符号数时，负数将大于以正数开头的任何数字。

在实践中，此方法将number间隔转换为原点，并检查是否number在区间中[0, D]，在哪里D = upper - lower。如果number低于下限：负，如果高于上限：大于D。

Answer 2

能够对如此小规模的代码进行重要优化是很少见的。从更高级别观察和修改代码可以获得巨大的性能提升。您可以完全消除对范围测试的需要，或者仅执行O（n）而不是O（n ^ 2）。您可以重新排序测试，以便始终隐含不平等的一面。即使算法是理想的，当您看到此代码如何进行1000万次范围测试并且您找到一种方法来批量处理并使用SSE并行执行多个测试时，更有可能获得增益。

Answer 3

这取决于您希望对同一数据执行测试的次数。

如果您一次执行测试，可能没有一种有意义的方法来加速算法。

如果您为一组非常有限的值执行此操作，则可以创建查找表。执行索引可能会更昂贵，但如果您可以将整个表放在缓存中，那么您可以从代码中删除所有分支，这样可以加快速度。

对于您的数据，查找表将是128 ^ 3 = 2,097,152。如果您可以控制三个变量中的一个，那么您可以同时考虑所有实例start = N，那么工作集的大小将下降到128^2 = 16432字节，这应该适合大多数现代缓存。

您仍然需要对实际代码进行基准测试，以查看无分支查找表是否比明显的比较快得多。