This is an old revision of the document!

Chess - Programming - MSB (Most Significant Bit)

The Most Significant Bit (LSB) is the bit position of the last bit set in a value.

There are many ways to determine the MSB, but the goal is to do that as quickly as possible.

Due to the number of Chess positions possible, many millions, even a small saving for the lookup of the MSB can provide much further lookups in the same time.

Using de Bruijn for 32-bit

u32 msbDeBruijn32(u32 v) {

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

v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27];

} </code>