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.

ulong i = 18;   // (10010)

NOTE: The LSB would be the 2 (or 1 if we are counting position from 0).

Using Bit-wise operations

ulong lsb = x & ~(x-1);

Using Bit Manipulation

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

Using Builtin

GCC has __builtin_clz.

lsb = __builtin_clz(pos);

Using de Bruijn

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

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 Logs

int lsb = (int)(Math.Log(v,2));

Using a Loop

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

NOTE: This is very slow.

Using MS C++ Compiler Built-in

#include <intrin.h>
 
unsigned char _BitScanForward(
   unsigned long * Index,
   unsigned long Mask
);
unsigned char _BitScanForward64(
   unsigned long * Index,
   unsigned __int64 Mask
);

Using .NET Core 3.0

.NET Core 3.0 introduced hardware intrinsics:

ulong value = 18;
ulong result = System.Runtime.Intrinsics.X86.Bmi1.X64.TrailingZeroCount(value);

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

int result2 = System.Numerics.BitOperations.TrailingZeroCount(value);

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

TODO

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;

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.