On Sun, 09 Mar 2008 10:40:50 -0700, Steven G. Johnson wrote:

> Here is a little algorithm I came across whose implementation is

> amusingly obscure: what simple function does the following C code

> compute, and why?

>

> #include <stdint.h>

> unsigned foo(uint32_t n)

> {

> const uint32_t a = 0x05f66a47;

> static const unsigned bar[32] =

>

{0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,2 2,14,20,18,11,5,30,13,17,10,29,9,8,7};

> n = ~n;

> return bar[(a * (n & (-n))) >> 27];

n = ~n;

n = a * (n & -n);

return bar[n >> 27];

You're assuming that the multiplication (a * (n & (-n))) will take place

in 32 bits. This is not the case when int or unsigned int has more than

32 bits. Store the result in n to be sure.

> }

>

> To save you the trouble of compiling and running it yourself, here is

> what it produces for n = 0,1,2,...,31:

>

> 0 -> 0, 1 -> 1, 2 -> 0, 3 -> 2, 4 -> 0, 5 -> 1, 6 -> 0, 7 -> 3, 8 -> 0,

> 9 -> 1, 10 -> 0, 11 -> 2, 12 -> 0, 13 -> 1, 14 -> 0, 15 -> 4, 16 -> 0,

> 17 -> 1, 18 -> 0, 19 -> 2, 20 -> 0, 21 -> 1, 22 -> 0, 23 -> 3, 24 -

>> 0, 25 -> 1, 26 -> 0, 27 -> 2, 28 -> 0, 29 -> 1, 30 -> 0, 31 -> 5

This looks like the number of consecutive bits set, starting from the

least significant.

(~n) & (-~n) can be written as (n + 1) & ~n. It is the value of the

lowest bit that is not set. The multiplication by 0x05f66a47 happens to

produce unique values in bits 27-31 for the first 32 powers of two (I'm

not seeing how this value was obtained), so after extracting those bits,

you can use a lookup table to find the result.