Differences

This shows you the differences between two versions of the page.

--- chess:programming:lsb_least_significant_bit [2021/10/30 11:13] – peter
+++ chess:programming:lsb_least_significant_bit [2021/10/30 13:11] (current) – peter
@@ Line 19: / Line 19: @@
 ----
-===== Using a Loop =====
+===== Using Bit-wise operations =====
 <code cpp>
-int getLSB(ulong v)
+ulong lsb = x & ~(x-1);
+</code>
+----
+===== Using Bit Manipulation =====
+<code cpp>
+UINT64 countTrailingZeros(UINT64 input)
 {
-  int lsb = 0;
+  if (input == 0)
-  while ((v >>= 1) != 0)
+    return 64;
-  {
-    lsb++;
+  UINT64 n = 0;
-  }
-  return lsb;
+  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>
-<WRAP info>
-**NOTE:**  This is very slow.
-</WRAP>
 ----
-===== Using Logs =====
+===== Using Builtin =====
+GCC has **<nowiki>__builtin_clz</nowiki>**.
 <code cpp>
-int lsb = (int)(Math.Log(v,2));
+lsb = __builtin_clz(pos);
 </code>
 ----
 ===== Using de Bruijn =====
@@ Line 72: / Line 87: @@
 }
 </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 Bit Manipulation =====
+===== Using Logs =====
 <code cpp>
-UINT64 countTrailingZeros(UINT64 input)
+int lsb = (int)(Math.Log(v,2));
-{
+</code>
-  if (input == 0)
-    return 64;
-  UINT64 n = 0;
+----
-  if ((input & 0xFFFFFFFF) == 0) { n = 32; input = input >> 32; }
+===== Using a Loop =====
-  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 cpp>
+int getLSB(ulong v)
+{
+  int lsb = 0;
+  while ((v >>= 1) != 0)
+  {
+    lsb++;
+  }
+  return lsb;
 }
 </code>
+<WRAP info>
+**NOTE:**  This is very slow.
+</WRAP>
 ----
@@ Line 130: / Line 159: @@
 </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 =====
-https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64?redirectedfrom=MSDN&view=msvc-160
 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