Differences

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

--- chess:programming:msb_most_significant_bit [2021/10/30 12:12] – peter
+++ chess:programming:msb_most_significant_bit [2021/10/30 12:29] (current) – [Using Built-in for GCC] peter
@@ Line 34: / Line 34: @@
   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 40: / Line 86: @@
 ===== Using de Bruijn for 32-bit =====
+<code cpp>
 u32 msbDeBruijn32(u32 v)
 {
@@ Line 65: / Line 112: @@
 </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>
 ----
@@ Line 72: / Line 146: @@
 <code cpp>
 #include <intrin.h>
+unsigned BSR32(unsigned long x)
+{
+  bsr_idx_t idx;
+  _BitScanReverse(&idx, x); // ignore bool retval
+  return idx;
+}
-unsigned char _BitScanForward(
+unsigned BSR64(uint64_t x)
-   unsigned long * Index,
+{
-   unsigned long Mask
+  bsr_idx_t idx;
-);
+  _BitScanReverse64(&idx, x); // ignore bool retval
-unsigned char _BitScanForward64(
+  return idx;
-   unsigned long * Index,
+}
-   unsigned __int64 Mask
-);
 </code>
@@ Line 88: / Line 166: @@
 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