Differences

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

--- chess:programming:msb_most_significant_bit [2021/10/30 12:08] – created peter
+++ chess:programming:msb_most_significant_bit [2021/10/30 12:29] (current) – [Using Built-in for GCC] peter
@@ Line 6: / Line 6: @@
   * Due to the number of Chess positions possible, many millions, even a small saving for the lookup of the MSB can provide much further lookups in the same time.
+----
+===== Using Bit Manipulation =====
+<code cpp>
+int msbPerformanceJunkie32(u32 x)
+{
+  static const unsigned int bval[] =
+    { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 };
+  unsigned int r = 0;
+  if (x & 0xFFFF0000)
+  {
+    r += 16 / 1;
+    x >>= 16 / 1;
+  }
+  if (x & 0x0000FF00)
+  {
+    r += 16 / 2;
+    x >>= 16 / 2;
+  }
+  if (x & 0x000000F0)
+  {
+    r += 16 / 4;
+    x >>= 16 / 4;
+  }
+  return r + bval[x];
+}
+</code>
+----
+===== Using Built-in for GCC =====
+<code cpp>
+unsigned BSR64(uint64_t x)
+{
+  return 63-__builtin_clzll(x);
+}
+</code>
+<WRAP info>
+**NOTE:**  Depending on architecture, the built-in functions include:
+  * <nowiki>__builtin_clz</nowiki>
+  * <nowiki>__builtin_clzl</nowiki>
+  * <nowiki>__builtin_clzll</nowiki>
+  * The returned value is undefined for 0 inputs.
+    * See https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
+</WRAP>
+----
+===== Using Built-in for Microsoft Compiler =====
+<code cpp>
+#ifdef MICROSOFT_COMPILER
+u32 msbNative32(u32 val)
+{
+  unsigned long result;
+  _BitScanReverse(&result, val);
+  return result;
+}
+u32 msbNative64(u64 val)
+{
+  unsigned long result;
+  _BitScanReverse64(&result, val);
+  return result;
+}
+#endif // MICROSOFT_COMPILER
+</code>
 ----
@@ Line 11: / Line 86: @@
 ===== Using de Bruijn for 32-bit =====
+<code cpp>
 u32 msbDeBruijn32(u32 v)
 {
@@ Line 28: / Line 104: @@
 }
 </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 a Loop =====
+<code cpp>
+unsigned int msbLoop32(u32 x)
+{
+  int r = 0;
+  if (x < 1) return 0;
+  while (x >>= 1) r++;
+  return r;
+}
+unsigned int msbLoop64(u64 x)
+{
+  int r = 0;
+  if (x < 1) return 0;
+  while (x >>= 1) r++;
+  return r;
+}
+</code>
+<WRAP info>
+**NOTE:**  This is very slow.
+</WRAP>
+----
+===== Using MS C++ Compiler Built-in =====
+<code cpp>
+#include <intrin.h>
+unsigned BSR32(unsigned long x)
+{
+  bsr_idx_t idx;
+  _BitScanReverse(&idx, x); // ignore bool retval
+  return idx;
+}
+unsigned BSR64(uint64_t x)
+{
+  bsr_idx_t idx;
+  _BitScanReverse64(&idx, x); // ignore bool retval
+  return idx;
+}
+</code>
+----
+===== References =====
+https://www.chessprogramming.org/De_Bruijn_Sequence_Generator.
+http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
+https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
+https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64?redirectedfrom=MSDN&view=msvc-160