bits.h

Go to the documentation of this file.

#pragma once
 
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
 
#if defined(_MSC_VER) && !defined(__clang__)
#include <intrin.h>
#endif
 
/* ============================================================================
 * Power-of-Two Operations
 * ============================================================================
 */
 
static inline bool is_power_of_two(size_t n) {
  return n && !(n & (n - 1));
}
 
static inline size_t next_power_of_two(size_t n) {
  if (n == 0)
    return 1;
  n--;
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  if (sizeof(size_t) > 4) {
    n |= n >> 32;
  }
  return n + 1;
}
 
/* ============================================================================
 * Leading/Trailing Zero Detection
 * ============================================================================
 */
 
static inline int find_first_set_bit(uint64_t mask) {
#if defined(__GNUC__) || defined(__clang__)
  // GCC/Clang builtin (fast hardware instruction on modern CPUs)
  if (mask == 0)
    return 64;
  return __builtin_ctzll(mask);
#elif defined(_MSC_VER) && defined(_M_X64)
  // Microsoft Visual C++ x64 intrinsic
  unsigned long index;
  if (_BitScanForward64(&index, mask)) {
    return (int)index;
  }
  return 64; // No bits set
#elif defined(_MSC_VER)
  // MSVC x86 fallback
  unsigned long index;
  if (_BitScanForward(&index, (unsigned long)mask)) {
    return (int)index;
  }
  if (_BitScanForward(&index, (unsigned long)(mask >> 32))) {
    return 32 + (int)index;
  }
  return 64; // No bits set
#else
  // De Bruijn sequence fallback: O(1) with ~4-5 CPU cycles
  // Portable and production-tested (used in LLVM, GCC)
  if (mask == 0)
    return 64;
 
  static const int debruijn_table[64] = {0,  1,  2,  53, 3,  7,  54, 27, 4,  38, 41, 8,  34, 55, 48, 28,
                                         62, 5,  39, 46, 44, 42, 22, 9,  24, 35, 59, 56, 49, 18, 29, 11,
                                         63, 52, 6,  26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
                                         51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12};
 
  // Isolate rightmost bit and hash using De Bruijn multiplication
  return debruijn_table[((mask & -mask) * 0x022fdd63cc95386dULL) >> 58];
#endif
}
 
/* ============================================================================
 * Bit Counting Operations
 * ============================================================================
 */
 
static inline int count_set_bits(uint64_t x) {
#if defined(__GNUC__) || defined(__clang__)
  return __builtin_popcountll(x);
#elif defined(_MSC_VER) && defined(_M_X64)
  return (int)__popcnt64(x);
#else
  // Software fallback
  int count = 0;
  while (x) {
    count += x & 1;
    x >>= 1;
  }
  return count;
#endif
}