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 Bit Manipulation

int msbPerformanceJunkie32(u32 x)
{
  static const unsigned int bval[] =
    { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };
  unsigned int r = 0;
  if (x & 0xFFFF0000) 
  {
    r += 16 / 1;
    x >>= 16 / 1;
  }
  if (x & 0x0000FF00) 
  {
    r += 16 / 2;
    x >>= 16 / 2;
  }
  if (x & 0x000000F0) 
  {
    r += 16 / 4;
    x >>= 16 / 4;
  }
  return r + bval[x];
}

Using Built-in for GCC

unsigned BSR64(uint64_t x) 
{
  return 63-__builtin_clzll(x);
}

NOTE: Depending on architecture, the built-in functions include:

__builtin_clz
__builtin_clzl
__builtin_clzll

The returned value is undefined for 0 inputs.
- See https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Using Built-in for Microsoft Compiler

#ifdef MICROSOFT_COMPILER
u32 msbNative32(u32 val)
{
  unsigned long result;
  _BitScanReverse(&result, val);
  return result;
}
 
u32 msbNative64(u64 val)
{
  unsigned long result;
  _BitScanReverse64(&result, val);
  return result;
}
#endif // MICROSOFT_COMPILER

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];
}

NOTE: This is very fast.

The De Bruijn lookup table needs to be pre-calculated.
See: https://www.chessprogramming.org/De_Bruijn_Sequence_Generator.

Using a Loop

unsigned int msbLoop32(u32 x)
{
  int r = 0;
  if (x < 1) return 0;
  while (x >>= 1) r++;
  return r;
}
 
unsigned int msbLoop64(u64 x)
{
  int r = 0;
  if (x < 1) return 0;
  while (x >>= 1) r++;
  return r;
}

NOTE: This is very slow.

Using MS C++ Compiler Built-in

#include <intrin.h>
unsigned BSR32(unsigned long x)
{
  bsr_idx_t idx;
  _BitScanReverse(&idx, x); // ignore bool retval
  return idx;
}
 
unsigned BSR64(uint64_t x) 
{
  bsr_idx_t idx;
  _BitScanReverse64(&idx, x); // ignore bool retval
  return idx;
}

References

https://www.chessprogramming.org/De_Bruijn_Sequence_Generator.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64?redirectedfrom=MSDN&view=msvc-160

Wiki

Table of Contents