Bitsets, Popcount (__builtin_popcount) & O(N/64) Word-Level Parallelism

SWAR (SIMD Within A Register) & Tree-Reduction Popcount

How do you count the number of set bits (Hamming weight / population count) inside a 64-bit word $x$ in $O(\log_2 64) = 6$ steps without hardware POPCNT? Treat the 64-bit integer as 64 parallel 1-bit accumulators and apply a divide-and-conquer parallel tree reduction:

1. Pairwise 2-bit sums: Subtract the even bits shifted right by 1 from each 2-bit pair: x = x - ((x >> 1) & 0x5555555555555555ULL) (since $2b_1 + b_0 - b_1 = b_1 + b_0$).
2. Nibble 4-bit sums: Add adjacent 2-bit pairs: x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL).
3. Byte 8-bit sums: Add adjacent 4-bit nibbles and mask: x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL (no overflow can occur since each byte holds at most $8 < 15$).
4. Horizontal Multiply Reduction: Multiply by the magic constant 0x0101010101010101ULL ($\sum_{k=0}^7 2^{8k}$), which sums all 8 byte-lanes into the top byte (bits 56..63), then shift right by 56: (x * 0x0101010101010101ULL) >> 56!

Bitset Representations Across Systems & Analytics Engines

Visualizing SWAR Parallel Popcount & Multi-Word Bitshift Carry

Fast Set-Bit Iteration via TZCNT + BLSR

Production Implementation: Dynamic 64-Bit Word-Parallel Bitset Engine

#include <bit>
#include <cstdint>
#include <vector>

class DynamicBitset64 {
  std::size_t num_bits_;
  std::vector<std::uint64_t> words_;

  void mask_tail() noexcept {
    const std::size_t rem = num_bits_ & 63;
    if (rem != 0 && !words_.empty()) {
      words_.back() &= (1ULL << rem) - 1ULL;
    }
  }

public:
  explicit DynamicBitset64(std::size_t num_bits)
      : num_bits_(num_bits), words_((num_bits + 63) / 64, 0ULL) {}

  void set(std::size_t i) noexcept {
    words_[i >> 6] |= (1ULL << (i & 63));
  }

  bool test(std::size_t i) const noexcept {
    return (words_[i >> 6] & (1ULL << (i & 63))) != 0;
  }

  // O(N / 64) word-parallel shift-OR: this |= (this << shift)
  // Accelerates 0-1 Subset Sum DP by 64x!
  void shift_left_or(std::size_t shift) noexcept {
    const std::size_t word_shift = shift >> 6;
    const std::size_t bit_shift = shift & 63;
    if (word_shift >= words_.size()) return;

    if (bit_shift == 0) {
      for (std::size_t i = words_.size() - 1; i >= word_shift; --i) {
        words_[i] |= words_[i - word_shift];
        if (i == word_shift) break;
      }
    } else {
      const std::size_t inv_shift = 64 - bit_shift;
      for (std::size_t i = words_.size() - 1; i > word_shift; --i) {
        words_[i] |= (words_[i - word_shift] << bit_shift)
                   | (words_[i - word_shift - 1] >> inv_shift);
      }
      words_[word_shift] |= (words_[0] << bit_shift);
    }
    mask_tail();
  }

  // O(N / 64) hardware popcount
  std::size_t count() const noexcept {
    std::size_t total = 0;
    for (std::uint64_t w : words_) {
      total += static_cast<std::size_t>(std::popcount(w));
    }
    return total;
  }

  // Iterate all set bit indices in O(N/64 + k) time using TZCNT + BLSR
  template <typename Callback>
  void for_each_set_bit(Callback&& cb) const {
    for (std::size_t block = 0; block < words_.size(); ++block) {
      std::uint64_t w = words_[block];
      while (w != 0) {
        const int bit = std::countr_zero(w);
        cb((block << 6) + static_cast<std::size_t>(bit));
        w &= (w - 1);
      }
    }
  }
};