Clarification on magic numbers

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Clarification on magic numbers

Postby matrix101 » 21 May 2015, 19:42

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
matrix101
 
Posts: 53
Joined: 02 Feb 2014, 12:46

Re: Clarification on magic numbers

Postby H.G.Muller » 24 May 2015, 11:52

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.
User avatar
H.G.Muller
 
Posts: 3080
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Clarification on magic numbers

Postby matrix101 » 28 May 2015, 15:05

Ok... How would I build my own bitscan routine?
matrix101
 
Posts: 53
Joined: 02 Feb 2014, 12:46

Re: Clarification on magic numbers

Postby H.G.Muller » 28 May 2015, 18:57

Code: Select all
Set b = ...;
while(b) {
  Set lowestBit = b & -b;
  b &= ~lowestBit;
  bitNr = MultiplyDeBruijnBitPosition[(uint32_t) (lowestBit * 0x077CB531U >> 27)];
  ...
}
User avatar
H.G.Muller
 
Posts: 3080
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Clarification on magic numbers

Postby matrix101 » 07 Jun 2015, 22:35

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.
matrix101
 
Posts: 53
Joined: 02 Feb 2014, 12:46

Re: Clarification on magic numbers

Postby H.G.Muller » 19 Jul 2015, 17:19

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.
User avatar
H.G.Muller
 
Posts: 3080
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest

cron