Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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 =====

<code cpp>
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];
}
</code>

----

===== Using Built-in for GCC =====

<code cpp>
unsigned BSR64(uint64_t x) 
{
  return 63-__builtin_clzll(x);
}
</code>

<WRAP info>
**NOTE:**  Depending on architecture, the built-in functions include:

  * <nowiki>__builtin_clz</nowiki>
  * <nowiki>__builtin_clzl</nowiki>
  * <nowiki>__builtin_clzll</nowiki>


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

</WRAP>

----

===== Using Built-in for Microsoft Compiler =====

<code cpp>
#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
</code>

----

===== Using de Bruijn for 32-bit =====

<code cpp>
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>

<WRAP info>
**NOTE:**  This is very fast.

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

</WRAP>

----

===== Using a Loop =====

<code cpp>
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;
}
</code>

<WRAP info>
**NOTE:**  This is very slow.
</WRAP>


----

===== Using MS C++ Compiler Built-in =====

<code cpp>
#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;
}
</code>

----

===== 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