c++ - 来自多个位域的互斥连续范围

Question

(这不是CS课的作业，即使看起来像)

我使用位域来表示 0 到 22 之间的范围。例如，作为输入，我有几个不同的范围(顺序无关紧要)。我将 . 用于 0 并将 X 用于 1 以提高可读性。

.....XXXXX..............
..XXXX..................
.....XXXXXXXXXXXXXXX....
........XXXXXXX.........
XXXXXXXXXXXXXXXXXXXXXXXX

位域范围的数量通常低于 10，但可能会高达 100。我想根据该输入计算互斥的连续范围，如下所示:

XX......................
..XXX...................
.....X..................
......XX................
........XX..............
..........XXXXX.........
...............XXXXX....
....................XXXX

(同样，输出顺序无关紧要，它们只需要互斥且连续，即它们不能有空洞。.....XXX....... XXXXX.... 必须分成两个单独的范围)。

我尝试了几种算法，但它们最终都变得相当复杂和不优雅。对我有很大帮助的是一种方法来检测 .....XXX.....XXXXX.... 有一个洞和一种方法来确定其中一个的索引钻孔中的钻头。

编辑:位域范围表示 map 上的缩放级别。它们旨在用于为 Mapnik(OpenStreetMap 使用的瓦片渲染系统)输出 XML 样式表。

Answer 1

我假设您在评论中提到的解决方案是这样的:

从左侧或右侧开始(因此索引 = 0)，扫描设置了哪些位(最多 100 次操作)。命名集合 x。同时设置一个变量block=0。

在 index=1 处，重复并存储以设置 y。如果 x XOR y = 0，则两者是相同的集合，因此转到索引 = 2。如果 x XOR y = z != 0，则范围 [block, index) 是连续的。现在设置 x = y，block = index，然后继续。

如果您有 100 个长度为 22 的位数组，这需要大约 2200 次操作。

这是最佳解决方案，因为无法进一步减少操作——在每个阶段，如果另一个集合与您的集合不匹配，您的范围就会被打破，因此要检查范围是否被打破，您必须检查所有 100 位。