确定整数是否在具有已知值集的两个整数（包含）之间的最快方法
在C或C ++中是否有比x >= start && x <= end更快的方法来testing整数是否在两个整数之间？
更新 ：我的具体平台是iOS。 这是一个框模糊函数的一部分，它将像素限制在给定的正方形中的一个圆圈。
更新 ：尝试接受的答案后 ，我得到了一个数量级的加速在一个代码行，正常的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
相当惊人的如何减less或消除分支可以提供如此戏剧性的加速。
有一个古老的技巧，只有一个比较/分支。 它是否真的能够提高速度可能是一个值得商榷的问题，即使是这样，也可能太less了，但是当你只是从两个比较开始的时候，一个巨大改进的机会相当遥远。 代码如下所示：
// 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);
使用典型的现代计算机（即任何使用二进制补码的计算机），转换为无符号的操作实际上是一个nop – 只是相同位的查看方式的改变。
请注意，在典型情况下，您可以预先计算（推测）循环之外的upper-lower ，以便通常不会贡献任何显着的时间。 随着减less分支指令的数量，这也（一般）改善分支预测。 在这种情况下，无论数字是低于最低端还是高于最高端，都将采用相同的分支。
至于这是如何工作的，其基本思想是非常简单的：当被视为无符号数时，负数将大于以正数开始的任何数。
在实践中，这种方法将number和间隔转换为原点，并检查number是否在区间[0, D] ，其中D = upper - lower 。 如果number低于下限： 负数 ，如果高于上限： 大于D
很less能够做如此小规模的重要优化代码。 性能上的好处来自更高级别的代码的观察和修改。 你可能完全不需要进行范围testing，或者只做O（n）而不是O（n ^ 2）。 你也许可以重新排列testing，这样不平等的一方总是隐含的。 即使这个algorithm是理想的，当你看到这个代码如何进行1000万次的范围testing，并且你find了一个批量的方法，并且使用SSE并行地完成许多testing的时候，增益就更有可能出现。
这取决于您想要在相同的数据上执行testing的次数。
如果您一次执行testing，那么加速algorithm可能没有有意义的方法。
如果你正在做一个非常有限的一组值，那么你可以创build一个查找表。 执行索引可能会更加昂贵，但是如果您可以将整个表格放入caching中，则可以从代码中删除所有分支，这可以加快速度。
对于你的数据查找表将是128 ^ 3 = 2,097,152。 如果你可以控制三个variables中的一个，所以你考虑所有的start = N实例，那么工作集的大小就会下降到128^2 = 16432个字节，这在大多数现代的caching中都是适用的。
您仍然需要对实际代码进行基准testing，以查看无分支查找表是否比明显的比较快得多。
这个答案是报告接受答案的testing。 我对sorting的随机整数的大型向量执行了一个封闭的范围testing，令我惊讶的是（low <= num && num <= high）的基本方法实际上比上面接受的答案更快！ testing是在HP Pavilion g6（带有6GB RAM的AMD A6-3400APU）上完成的，以下是用于testing的核心代码：
int num = rand(); // num to compare in consecutive ranges. chrono::time_point<chrono::system_clock> start, end; auto start = chrono::system_clock::now(); int inBetween1{ 0 }; for (int i = 1; i < MaxNum; ++i) { if (randVec[i - 1] <= num && num <= randVec[i]) ++inBetween1; } auto end = chrono::system_clock::now(); chrono::duration<double> elapsed_s1 = end - start;
与以上所接受的答案相比较：
int inBetween2{ 0 }; for (int i = 1; i < MaxNum; ++i) { if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1])) ++inBetween2; }
注意randVec是一个sorting的向量。 对于任何MaxNum大小的第一种方法击败我的机器上的第二个！
是不可能只对整数执行按位操作？
由于它必须在0到128之间，如果第8位被设置（2 ^ 7），它是128或更多。 边缘情况将是一个痛苦，但是，因为你想要一个包容性的比较。
