Differences

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

--- chess:programming:lsb_least_significant_bit [2021/10/30 11:37] – 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 159: / Line 188: @@
 ===== 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