Winboard Forum

Good day to all,

I have a question related to perfect hashing. I`m interested maybe at some point implementing a hashing function, but before that I need to know the basics.

For example, http://en.wikipedia.org/wiki/De_Bruijn_sequence

Sadly, I don`t understand De Bruijn sequence. But even so, say these numbers aren`t related right?

Code: Select all

unsigned int v;   
int r;           
static const int MultiplyDeBruijnBitPosition[32] =
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];


My question is why are these exact numbers chosen to do the multiplication ( Does it relate to magic square? ) I wasn`t able to search any information on the net.

Thanks

The trick is in the multiplier 0x077CB531U, which in binary is 00000111011111001011010100110001. The special property of this 'De Bruijn number' is that every sub-string of 5 consecutive bits is different. This makes it possible to determine by how many bits the constant is shifted to the left, by just looking at the uppermost 5 bits. E.g. if it is not shifted at all, the upper 5 bits are 00000 = 0. Shifting it by 1 bit, makes this 00001 = 1, by 2 bits 00011 = 3, shifting it 31 bit makes this 10000 = 16.

The array then just is a lookup table to get the shift from the observed 5 bits. So the first element is 0, the 2nd element is 1, and the 3rd element is 2, the 17th element (i.e. a[16]) is 31 (because a shift of 31 bits caused 16 to appear there, and counting of array elements starts at 0 in C, rather than 1).

The idea is then that multiplying by a number that has just a single non-zero bit is equivalent to a shift.

Ok... How would I build my own bitscan routine?

Thank you for your effort, but I became confused about other things when trying to implement the bitscan routine...
For example, I don`t understand x ^ x-1. I know it results all bits set including and below the LS1B but what does x-1 do to x? Is it 00001111 - 00000001 assuming x is just random 8-bit unsigned value.

x & x-1 is a trick to use the carry-propagation logic of the CPU's adder unit to quickly find the lowest set bit. The idea is that in binary subtraction of 1 you will change all trailing 0 into 1, and the 1 before it to 0. Like:

100000
000001
______ -
011111

(similar to 1000 - 1 = 0999 in decimal). Eveything above the lowest non-zero digits is left unchanged, and is thus cleared by the XOR operation.