测试两个整数范围是否重叠的最有效方法是什么?

范围重叠意味着什么?这意味着有一些数字c在这两个范围内,即。

x1 <= C <= x2

和

y1 <= C <= y2

现在,如果允许我们假设范围是格式良好的(这样x1<=x2和y1<=y2),那么就足以测试

x1 <= y2 && y1 <= x2

给定两个范围[x1,x2],[y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

这很容易扭曲正常的人脑,所以我发现了一种更容易理解的视觉方法:

Le解释

如果两个范围是“too fat” to fit in a slot that is exactly the sum of the width of both,then they overlap.

对于范围 [a1,a2] and [b1,b2] this would be:。

/**
*我们正在测试:
*最大点-最小点<w1+w2
**
如果最大值(a2,b2)-最小值(a1,b1)和lt;(a2-a1)+(b2-b1){
//太胖了——它们重叠了!
}
< /代码> 
更容易理解的方法:




LE解释

如果有两个范围“太肥”要放入正好是两个宽度之和的槽中,则它们会重叠。

适用范围[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!
}

很好的回答来自 Simon 但对我来说,考虑反例比较容易。

两个范围何时不重叠?当其中一个开始于另一个结束之后,它们不会重叠:

dont_overlap = x2 < y1 || x1 > y2

现在,当它们重叠时很容易表达:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

从开始的最大值减去范围的最小值似乎可以做到这一点。如果结果小于或等于零,我们有一个重叠。这很好地显示了它:

我想问题是关于最快的代码,而不是最短的代码。最快的版本必须避免分支,因此我们可以编写如下内容:

对于简单情况:

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

return x2 >= y1 && x1 <= y2;

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

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

然后您可以使用此项检查:

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

只有在哪里 四 涉及操作:

• 两次减法
• 一次乘法
• 一个比较

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

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

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

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 or x2 < y1 < y2 相当于 y2 < x1 or x2 < y1 .

因此,使两个范围重叠的条件是: not(y2 < x1 or x2 < y1) ,相当于 y2 >= x1 and x2 >= y1 (西蒙的回答也是如此)。

这是我的版本:

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;

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