c# - 带溢出的简单区间/范围交集

Question

我正在编写一个物理内存管理器，它从 BIOS 获取一些未被关键系统数据使用的内存间隔。每个区间都有0 <= start <= 2^32 - 1和 0 <= length <= 2^32 .我已经过滤掉了零长度间隔。

给定两个区间 S 和 T，我想检测它们如何相交。例如，S 是否在 T 之前开始并在 T 之内结束(图片 a)？还是S在T之前开始，在T之后结束(图片c)？

你会认为解决方案很简单:

uint s_end = s_start + s_length;
uint t_end = t_start + t_length;

if (s_start < t_start)
    // S starts before T
else if (s_start < t_end)
    // S starts within T
else
    // S starts after T

if (s_end <= t_start)
    // S ends before T
else if (s_end <= t_end)
    // S ends within T
else
    // S ends after T

问题是溢出:我在技术上仅限于 32 位整数，并且间隔可以(并且经常)使用可用整数的整个范围。例如图b，t_end由于溢出而等于 0。甚至，如图 f t_start = t_end = s_start = 0同时 t_length != 0 .

如何在考虑溢出的情况下使这些区间相交条件起作用？

溢出搞砸了我的条件，但我真的不能为此使用 64 位整数(那将是最简单的)。我知道对我的条件进行一些巧妙的重组并使用加法和减法一定是可能的，但是在制作了无数的图表并思考了几个小时之后，我似乎无法全神贯注。

^{虽然我的问题是 32 位整数，但在此图像中我使用 4 位整数只是为了简化它。问题依旧。}

Answer 1

好的，问题是，如果您希望范围跨越所有 n 位，则任何基于开始/结束的计算都有可能溢出。

所以诀窍是对开始/结束计算不会溢出的地方进行线性变换，进行计算，然后再进行线性变换。

注意事项

在 we can safely call end() now 行下方，您可以调用排序检查(您的原始代码)，这将是安全的，因为在线性变换期间保留了排序。

此外，正如我在上一篇文章中指出的那样，有一种特殊的边界情况，即使您执行此转换，您也会溢出(跨越整条线) - 但您可以针对该特殊边界条件进行编码。

输出

5 11

代码

#include <iostream>

using type = uint8_t;

struct segment
{
    type start, length;
    type end() const { return start + length; }
};

static segment
intersect( segment s, segment t )
{
    type shift = std::min( s.start, t.start );

    // transform so we can safely call end()
    s.start -= shift;     // doesn't affect length
    t.start -= shift;     // doesn't affect length

    // we can safely call end() now ----------------------------------------------
    type u_start  = std::max( s.start, t.start );
    type u_end    = std::min( s.end(), t.end() );
    type u_length = u_end - u_start;

    segment u{ u_start, u_length };

    // transform back
    u.start += shift;

    return u;
}

int main()
{
    segment s{ 3, 13 }, t{ 5, 11 };
    segment u = intersect( s, t );

    std::cerr << uint32_t( u.start ) << " " << uint32_t( u.length ) << std::endl;

    return 0;
}