StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>No shrinkwrapped solution I'm afraid, but an alternative algorithm.</p> <p>Store your items in a bitvector - O(n) if you know the maximum item at the start and preallocate the vector.</p> <p>Translate that vector into a vector of transition point flags - exclusive-or the bitvector with a bitshifted version of itself. Slightly fiddly at the word boundaries, but still O(n). Logically, you get a new key at the old max + 1 (the transition back to zeros after all your keys are exhausted), so it's a good idea to allow for that in the preallocation of the vector.</p> <p>Then, iterate through the bitvector finding the set bits. The first set bit indicates the start of a range, the second the end, the third the start of the next range and so on. The following bit-fiddling function (assuming 32 bit int) may be useful...</p> <pre><code>int Low_Bit_No (unsigned int p) { if (p == 0) return -1; // No bits set int l_Result = 31; unsigned int l_Range = 0xffffffff; unsigned int l_Mask = 0x0000ffff; if (p & l_Mask) { l_Result -= 16; } else { l_Mask ^= l_Range; } l_Range &= l_Mask; l_Mask &= 0x00ff00ff; if (p & l_Mask) { l_Result -= 8; } else { l_Mask ^= l_Range; } l_Range &= l_Mask; l_Mask &= 0x0f0f0f0f; if (p & l_Mask) { l_Result -= 4; } else { l_Mask ^= l_Range; } l_Range &= l_Mask; l_Mask &= 0x33333333; if (p & l_Mask) { l_Result -= 2; } else { l_Mask ^= l_Range; } l_Mask &= 0x55555555; if (p & l_Mask) { l_Result -= 1; } return l_Result; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload