Table of Contents

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. 

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.

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.

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