testing两个重叠整数范围的最有效方法是什么？
给定两个包含整数范围[x1：x2]和[y1：y2]，其中x1≤x2和y1≤y2，testing两个范围是否有重叠的最有效方法是什么？
一个简单的实现如下：
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); } 但我希望有更有效的方法来计算这个。
在最less的操作方面，哪种方法是最有效率的。
这些范围重叠是什么意思？ 这意味着在这两个范围内存在一些数字C，即
x1 <= C <= x2
和
y1 <= C <= y2
现在，如果我们可以假设范围是良构的（所以x1 <= x2且y1 <= y2），那么testing就足够了
x1 <= y2 && y1 <= x2
给定两个范围[x1，x2]，[y1，y2]
def is_overlapping(x1,x2,y1,y2): return max(x1,y1) <= min(x2,y2)
这可以很容易地扭曲一个正常的人类大脑，所以我发现一个更容易理解的视觉方法：
解释
当我用这种方式进行可视化时，我发现它更容易理解。 如果两个范围“太胖”以至于不能恰好是两者的宽度的总和，则它们重叠。
对于范围[x1, x2]和[y1, y2]这将是：
/** * we are testing for: * max point - min point < w1 + w2 **/ if max(x2, y2) - min(x1, y1) < (x2 - x1) + (y2 - y1) { // too fat -- they overlap! }
来自西蒙的伟大答案，但对我来说，思考逆向案例更容易。
2个范围何时不重叠？ 当其中一个开始后另一个结束时它们不重叠：
dont_overlap = x2 < y1 || x1 > y2
现在很容易expression，当他们重叠：
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等，然后使用别人提供的解决scheme，否则这是最低限度的需要检查。
你可能应该注意到一些编译器会为你优化它 – 只要这4个expression式中的任何一个返回true就返回。 如果返回true，那么最终的结果也是如此 – 所以其他检查可以被跳过。
这是我的版本：
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;
除非你在数十亿宽间隔的整数上运行一些高性能的范围检查器，否则我们的版本应该类似地执行。 我的观点是，这是微观优化。
