给定两个包含范围[x1:x2]和[y1:y2],其中x1≤x2和y1≤y2,测试这两个范围是否有重叠的最有效方法是什么?

一个简单的实现如下:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

但是我希望有更有效的方法来计算这个。

就最少的操作而言,哪种方法是最有效的?


当前回答

我想问题是关于最快的代码,而不是最短的代码。最快的版本必须避免分支,所以我们可以这样写:

对于简单的例子:

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

或者,对于这种情况:

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};

其他回答

以下是我的看法:

int xmin = min(x1,x2)
  , xmax = max(x1,x2)
  , ymin = min(y1,y2)
  , ymax = max(y1,y2);

for (int i = xmin; i < xmax; ++i)
    if (ymin <= i && i <= ymax)
        return true;

return false;

除非您正在对数十亿个宽间距整数运行一些高性能的范围检查器,否则我们的版本应该执行类似的操作。我的观点是,这是微观优化。

如果你正在处理,给定两个范围[x1:x2]和[y1:y2],自然/反自然顺序范围同时存在:

自然顺序:x1 <= x2 && y1 <= y2或 反自然顺序:x1 >= x2 && y1 >= y2

然后你可能想用这个来检查:

它们重叠<=> (y2 - x1) * (x2 - y1) >= 0

其中只涉及四个操作:

2倍 一个乘法 一个比较

如果有人正在寻找计算实际重叠的一行程序:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

如果你想要少一些操作,但多一些变量:

bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations

反过来思考:如何使这两个范围不重叠?给定[x1, x2],则[y1, y2]应在[x1, x2]之外,即y1 < y2 < x1或x2 < y1 < y2,这等价于y2 < x1或x2 < y1。

因此,使两个范围重叠的条件是:不(y2 < x1或x2 < y1),这相当于y2 >= x1和x2 >= y1(与Simon接受的答案相同)。

这很容易扭曲正常人的大脑,所以我找到了一个更容易理解的视觉方法:

勒解释

如果两个范围“太胖”,无法放入正好是两者宽度之和的槽中,那么它们就会重叠。

对于范围[a1, a2]和[b1, b2],这将是:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}