Mutually exclusive contiguous ranges from multiple bitfields

Question

(This is not a CS class homework, even if it looks like one)

I use bit fields to represent ranges from 0 to 22. As an input, I have several different ranges, for example (order doesn't matter). I have used . for 0 and X for 1 for better readability.

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

The number of bitfield ranges is usually less than 10, but can reach 100. From this input I want to calculate mutually exclusive adjacent ranges, for example:

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

(again, the order of the output does not matter, they just have to be mutually exclusive and adjacent, i.e. they cannot have holes in them. .....XXX.......XXXXX.... must be divided into two separate ranges).

I tried several algorithms, but all of them turned out to be quite complex and uncontrollable. What really helped me was a way to find that .....XXX.......XXXXX.... has a hole and a way to determine the index of one of the bits in the hole.

Edit: The range of bit fields is the scale levels on the map. They are intended to be used to output XML stylesheets for Mapnik (a tile rendering system that, among other things, is used by OpenStreetMap).

Answer 1

I assume that the solution you mentioned in the comment looks something like this:

Start with the left or right (so index = 0) and scan which bits are set (up to 100 operations). The name given by x. Also set the variable block = 0.

With index = 1, repeat and save to set y. If x XOR y = 0, both are the same sets, so go to index = 2. If it is x XOR y = z! = 0, then the range [block, index) is adjacent. Now set x = y, block = index and continue.

If you have 100 bitmaps with a length of 22 each, this takes approximately 2200 operations.

This is the optimal solution, because the operation cannot be reduced further - at each stage your range is broken if another set does not match your set, therefore, to check if the range is damaged, you must check all 100 bits.

Answer 2

I will take a picture of your sub-problem, at least.

What would help me a lot is a way to find that .....XXX.......XXXXX.... has a hole and a way to determine the index of one of the bits in the hole.

Searching for the bits with the smallest and highest ("1") in the bitmask - the problem has been quite resolved; See, for example, ffs(3) in glibc, or see for example http://en.wikipedia.org/wiki/Bit_array#Find_first_one

Given the first and last bitmap indices, name them i and j , you can calculate a bitmap having all the bits between Betweem i and j using M = ((1 << i) - 1) & (~((1 << j) - 1)) (apologies for any off-for-one errors).

You can then check to see if the original bitmap has a hole by comparing it to M If it does not match, you can take the xor M input to find the holes and repeat.