给定两个包含范围[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;

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

我相信min(upper(A),upper(B))>=max(lower(A),lower(B))将是一个很好的解决方案,不仅因为它的简单性,而且因为它超越了两个范围的可扩展性。

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

对于简单的例子:

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);
};

你已经有了最有效的表示——这是需要检查的最小值,除非你确定x1 < x2等,然后使用其他人提供的解决方案。

你可能应该注意到,一些编译器实际上会为你优化它——只要这4个表达式中的任何一个返回true就返回。如果其中一个返回true,那么最终结果也会返回true——因此可以跳过其他检查。

值域重叠是什么意思?这意味着存在一个在两个范围内的数C,即。

x1 <= C <= x2

and

y1 <= C <= y2

为了避免混淆,考虑范围为: [x1:x2]和[y1:y2]

现在,如果我们可以假设范围是构造良好的(因此x1 <= x2和y1 <= y2),那么就足以进行测试

x1 <= y2 && y1 <= x2

OR

(StartA <= EndB)和(EndA >= StartB)