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

问题描述

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

Is there a faster way than x >= start && x <= end in C or C++ to test if an integer is between two integers?

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

UPDATE: My specific platform is iOS. This is part of a box blur function that restricts pixels to a circle in a given square.

更新:在尝试了接受的答案后，我得到了一个数量级的加速一行代码超过了正常的 x >= start &&x <=结束方式.

UPDATE: After trying the accepted answer, I got an order of magnitude speedup on the one line of code over doing it the normal x >= start && x <= end way.

UPDATE:这是使用 XCode 汇编器的前后代码:

UPDATE: Here is the after and before code with assembler from 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

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

Pretty amazing how reducing or eliminating branching can provide such a dramatic speed up.

推荐答案

有一个古老的技巧可以只用一个比较/分支来做到这一点.它是否真的会提高速度可能是值得商榷的，即使它确实如此，也可能太少引起注意或关心，但是当您只开始进行两次比较时，大幅提高的机会非常渺茫.代码如下:

There's an old trick to do this with only one comparison/branch. Whether it'll really improve speed may be open to question, and even if it does, it's probably too little to notice or care about, but when you're only starting with two comparisons, the chances of a huge improvement are pretty remote. The code looks like:

// 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 —— 只是对相同位的看法发生了变化.

With a typical, modern computer (i.e., anything using twos complement), the conversion to unsigned is really a nop -- just a change in how the same bits are viewed.

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

Note that in a typical case, you can pre-compute upper-lower outside a (presumed) loop, so that doesn't normally contribute any significant time. Along with reducing the number of branch instructions, this also (generally) improves branch prediction. In this case, the same branch is taken whether the number is below the bottom end or above the top end of the range.

至于它的工作原理，基本思想非常简单:当被视为无符号数时，负数将大于任何以正数开始的数.

As to how this works, the basic idea is pretty simple: a negative number, when viewed as an unsigned number, will be larger than anything that started out as a positive number.

在实践中，这个方法将number和区间转换到原点，并检查number是否在区间[0, D]，其中 D = 上 - 下.如果number低于下限:负，如果高于上限:大于D.