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 - LSB (Least Significant Bit) ======

The least significant bit (LSB) is the bit position of the __first__ bit set in a value.

There are many ways to determine the LSB, 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 LSB can provide much further lookups in the same time.

----

<code>
ulong i = 18;   // (10010)
</code>

<WRAP info>
**NOTE:**  The LSB would be the 2 (or 1 if we are counting position from 0).
</WRAP>

----

===== Using Bit-wise operations =====

<code cpp>
ulong lsb = x & ~(x-1);
</code>

----

===== Using Bit Manipulation =====

<code cpp>
UINT64 countTrailingZeros(UINT64 input)
{
  if (input == 0) 
    return 64;

  UINT64 n = 0;

  if ((input & 0xFFFFFFFF) == 0) { n = 32; input = input >> 32; }
  if ((input & 0xFFFF) == 0) { n = n + 16; input = input >> 16; }
  if ((input & 0xFF) == 0) { n = n + 8; input = input >> 8; }
  if ((input & 0xF) == 0) { n = n + 4; input = input >> 4; }
  if ((input & 3) == 0) { n = n + 2; input = input >> 2; }
  if ((input & 1) == 0) { ++n; }

  return n;
}
</code>

----

===== Using Builtin =====

GCC has **<nowiki>__builtin_clz</nowiki>**.

<code cpp>
lsb = __builtin_clz(pos);
</code>

----



===== Using de Bruijn =====

<code cpp>
const UINT64 DeBruijnSequence = 0x37E84A99DAE458FULL;

int MultiplyDeBruijnBitPosition[] =
{
  0, 1, 17, 2, 18, 50, 3, 57,
  47, 19, 22, 51, 29, 4, 33, 58,
  15, 48, 20, 27, 25, 23, 52, 41,
  54, 30, 38, 5, 43, 34, 59, 8,
  63, 16, 49, 56, 46, 21, 28, 32,
  14, 26, 24, 40, 53, 37, 42, 7,
  62, 55, 45, 31, 13, 39, 36, 6,
  61, 44, 12, 35, 60, 11, 10, 9,
};


// Will return zero for b = 0.
int BitScanForward(ulong b)
{
  Debug.Assert(b > 0, "Target number should not be zero");
  return multiplyDeBruijnBitPosition[((ulong)((long)b & -(long)b) * DeBruijnSequence) >> 58];
}
</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 Logs =====

<code cpp>
int lsb = (int)(Math.Log(v,2));
</code>

----

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

<code cpp>
int getLSB(ulong v)
{
  int lsb = 0;
  while ((v >>= 1) != 0) 
  {
    lsb++;
  }
  return lsb;
}
</code>

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

----

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

<code cpp>
#include <intrin.h>

unsigned char _BitScanForward(
   unsigned long * Index,
   unsigned long Mask
);
unsigned char _BitScanForward64(
   unsigned long * Index,
   unsigned __int64 Mask
);
</code>

----

===== Using .NET Core 3.0 =====
 
.NET Core 3.0 introduced hardware intrinsics:

<code cpp>
ulong value = 18;
ulong result = System.Runtime.Intrinsics.X86.Bmi1.X64.TrailingZeroCount(value);
</code>

Alternatively, the new **System.Numerics.Bitoperations** methods also use hardware intrinsics:

<code cpp>
int result2 = System.Numerics.BitOperations.TrailingZeroCount(value);
</code>

----

===== Using the integer log base 2 of an integer with an 64-bit IEEE float =====

TODO

<code cpp>
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
</code>

<WRAP info>
**NOTE:**  The code above loads a 64-bit (IEEE-754 floating-point) double with a 32-bit integer (with no padding bits) by storing the integer in the mantissa while the exponent is set to 2^52.

  * From this newly minted double, 2^52 (expressed as a double) is subtracted, which sets the resulting exponent to the log base 2 of the input value, v.
  * All that is left is shifting the exponent bits into position (20 bits right) and subtracting the bias, 0x3FF (which is 1023 decimal).
  * This technique only takes 5 operations, but many CPUs are slow at manipulating doubles, and the endianess of the architecture must be accommodated. 

</WRAP>

----

===== References =====

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

https://www.chessprogramming.org/De_Bruijn_Sequence_Generator

https://en.wikipedia.org/wiki/Bit_numbering

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