S
Steven G. Johnson
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,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
n = ~n;
return bar[(a * (n & (-n))) >> 27];
}
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 -
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,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
n = ~n;
return bar[(a * (n & (-n))) >> 27];
}
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 -