April 10, 2007

Shift Registers and De Bruijn Sequences

I tell ya' - everything time you think you've got a novel idea, turns out somebody's been there already... doesn't even seem to matter how small it might be.

For example: I have this minor function I wrote ages ago, which I had recently rewritten/had to re-derive. Its purpose was fairly mundane - I wanted to compute the (integer) log base 2 for a power of 2 integer value. Pretty simple and esoteric problem, but it pops up fairly often in graphics/sound programming (especially 3d stuff).

There are lots of solutions, and its not really a significant performance bottleneck or anything, but I always thought my solution was rather novel. The code looks like this : (link)

The idea is pretty simple, but clever (er... if I do say so myself, I suppose :)).

Very (very) briefly: multiplying by a power of 2 is the same as left-shifting by that power (determining that power being the log we're looking for). Therefore, we can construct a bit pattern that uniquely encodes the possible patterns sequence 0 - 31, such that any 5 bit sequence is uniquely of that range. Then multiplying by a power of two number puts a unique sequence into the top 5 bits of the result, which we can then shift down and use a table to "reverse" into our result. We need the table, because of course the encoding isn't linear with respect to the domain.

There are a number of constants you could use to fulfill this criteria, and I always thought of it as a compression/huffman tree encoding problem. The current constant I computed is 0x04ad19df.

Turns out not only is this a well known idea, but, further, its actually a special class of space filling curves (amongst other things) know as De Bruijn sequences. See the great "Bit Twiddling Hacks" page by Sean Eron Anderson for more information. The constant they computed, which of course also uses a different table, is 0x077CB531.

Results are the same.

Ah, well. Time to move on, I think..... :)


Anonymous said...
This comment has been removed by a blog administrator.
new laptop battery said...

Thanks from specialize in laptop battery,laptop AC adapters. All our products are brand new, with the excellent service from our laptop battery of customer service team.
Thanks for your info. The most convenient and cheap replacement battery online shop in uk. We specialize in laptop batteries, laptop AC adapters.

All our laptop AC adapter are brand new, with the excellent service from our customer service team.

the most convenient and usa battery online shop in usa.
You can find some battery and adapter from here is very cool.

We specialize in laptop batteries,laptop AC adapters. All of batteries are brand new, with the excellent service from our customer service team, you can feel free to purchase on laptop battery!
Here is cheap laptop ac adapter online shop in uk. We specialize in batteries. All our au battery are brand new, with the excellent service from our customer service team.