多个位域中互斥的连续范围
（这不是 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.... 有一个洞的方法以及一种确定其中一个的索引的方法孔中的钻头。
编辑：位域范围表示地图上的缩放级别。它们旨在用于输出 Mapnik（OpenStreetMap 使用的图块渲染系统）的 XML 样式表。
(This is not a CS class homework, even if it looks like one)
I'm using bitfields to represent ranges between 0 and 22. As an input, I have several different ranges, for example (order doesn't matter). I used . for 0 and X for 1 for better readability.
.....XXXXX..............
..XXXX..................
.....XXXXXXXXXXXXXXX....
........XXXXXXX.........
XXXXXXXXXXXXXXXXXXXXXXXX
The number of bitfield ranges is typically below 10, but can potentially become as high as 100. From that input, I want to calculate the mutually exclusive, contiguous ranges, like this:
XX......................
..XXX...................
.....X..................
......XX................
........XX..............
..........XXXXX.........
...............XXXXX....
....................XXXX
(again, the output order doesn't matter, they just need to be mutually exclusive and contiguous, i.e. they can't have holes in them. .....XXX.......XXXXX.... must be split up in two individual ranges).
I tried a couple of algorithms, but all of them ended up being rather complex and unelegant. What would help me immensely is a way to detect that .....XXX.......XXXXX.... has a hole and a way to determine the index of one of the bits in the hole.
Edit: The bitfield range represent zoomlevels on a map. They are intended to be used for outputting XML stylesheets for Mapnik (the tile rendering system that is, among others, used by OpenStreetMap).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我假设您在评论中提到的解决方案是这样的：
从左侧或右侧开始（因此索引 = 0），然后扫描设置了哪些位（最多 100 次操作）。命名集合 x。同时设置变量块=0。
在索引 = 1 处，重复并存储以设置 y。如果 x XOR y = 0，则两者是相同的集合，因此继续索引=2。如果 x XOR y = z != 0，则范围 [block, index) 是连续的。现在设置 x = y，块 = 索引，然后继续。
如果有 100 个位数组，每个位数组长度为 22，则需要执行 2200 次操作。
这是一个最佳解决方案，因为操作无法进一步减少 - 在每个阶段，如果另一组与您的组不匹配，您的范围就会被破坏，因此要检查范围是否被破坏，您必须检查所有 100 位。
I'm assuming the solution you're mentioning in the comment is something like this:
Start at the left or right (so index = 0), and scan which bits are set (upto 100 operations). Name that set x. Also set a variable block=0.
At index=1, repeat and store to set y. If x XOR y = 0, both are identical sets, so move on to index=2. If it x XOR y = z != 0, then range [block, index) is contiguous. Now set x = y, block = index, and continue.
If you have 100 bit-arrays of length 22 each, this takes something on the order of 2200 operations.
This is an optimum solution because the operation cannot be reduced further -- at each stage, your range is broken if another set doesn't match your set, so to check if the range is broken you must check all 100 bits.
至少我会尝试解决你的子问题..
找到位掩码中的最低和最高设置（“1”）位是一个很好的方法
解决了问题；例如，参见 glibc 中的
ffs(3)，或者参见例如 http://en.wikipedia.org/wiki/Bit_array#Find_first_one
给定第一个位图的最后一个索引，称为
i和j，您可以计算设置了
i和j之间所有位的位图使用 M = ((1 << i) - 1) & (~((1 << j) - 1)) （对任何问题表示歉意
相差一误差）。
然后，您可以通过将原始位图与
M。如果不匹配，可以通过输入异或M来查找孔并重复。
I'll take a shot at your sub-problem, at least..
Finding the lowest and highest set ("1") bits in a bitmask is a pretty
solved problem; See, for example,
ffs(3)in glibc, or seee.g. http://en.wikipedia.org/wiki/Bit_array#Find_first_one
Given the first and last indexes of a bitmap, call them
i, andj,you can compute the bitmap that has all bits betweem
iandjsetusing
M = ((1 << i) - 1) & (~((1 << j) - 1))(apologies for anyoff-by-one-errors).
You can then test if the original bitmap has a hole by comparing it to
M. If it doesn't match, you can take the input xorMto find theholes and repeat.