Mutually exclusive contiguous ranges from multiple bitfields

(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).

---

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.

---

I'll take a shot at your sub-problem, at least..

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.

Finding the lowest and highest set ("1") bits in a bitmask is a pretty solved problem; See, for example, ffs(3) in glibc, or see e.g. http://en.wikipedia.org/wiki/Bit_array#Find_first_one

Given the first and last indexes of a bitmap, call them i, and j, you can compute the bitmap that has all bits betweem i and j set using M = ((1 << i) - 1) & (~((1 << j) - 1)) (apologies for any off-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 xor M to find the holes and repeat.