Clarification on magic numbers

[matrix101]

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

[H.G.Muller]

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.

[matrix101]

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

[H.G.Muller]

Code: Select all

Set b = ...;
while(b) {
  Set lowestBit = b & -b;
  b &= ~lowestBit;
  bitNr = MultiplyDeBruijnBitPosition[(uint32_t) (lowestBit * 0x077CB531U >> 27)];
  ...
}


[matrix101]

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.

[H.G.Muller]

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.