c++ - 确定整数是否在具有已知值集的两个整数(包括)之间的最快方法

Question

有没有比 x >= start && x <= end 更快的方法？在 C 或 C++ 中测试一个整数是否介于两个整数之间？

更新:我的特定平台是 iOS。这是框模糊功能的一部分，该功能将像素限制为给定正方形中的圆形。

更新:尝试 accepted answer 之后，我在一行代码上的速度比正常的 x >= start && x <= end 提高了一个数量级。方式。

更新:这是使用 XCode 汇编程序的前后代码:

新方式

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

老路

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

减少或消除分支如何提供如此显着的加速，真是令人惊讶。

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 = 上 - 下。如果 number 低于下限:negative，如果高于上限:大于 D。