<commit_before>#pragma once
#include "base/assert.hpp"

#include <cstdint>
#include <limits>
#include <type_traits>

namespace bits
{
  // Count the number of 1 bits. Implementation: see Hacker's delight book.
  inline uint32_t PopCount(uint32_t x) noexcept
  {
    x -= ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x += (x >> 8);
    x += (x >> 16);
    return x & 0x3F;
  }

  inline uint32_t PopCount(uint8_t x) noexcept
  {
    return PopCount(static_cast<uint32_t>(x));
  }

  // Count the number of 1 bits in array p, length n bits.
  // There is a better implementation at hackersdelight.org
  inline uint32_t PopCount(uint32_t const * p, uint32_t n)
  {
    uint32_t s = 0;
    for (uint32_t i = 0; i < n; i += 31)
    {
      uint32_t lim = (n < i + 31 ? n : i + 31);
      uint32_t s8 = 0;
      uint32_t x = 0;
      for (uint32_t j = i; j < lim; ++j)
      {
        x = p[j];
        x -= ((x >> 1) & 0x55555555);
        x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
        x = (x + (x >> 4)) & 0x0F0F0F0F;
        s8 += x;
      }
      x = (s8 & 0x00FF00FF) + ((s8 >> 8) & 0x00FF00FF);
      x = (x & 0x0000ffff) + (x >> 16);
      s += x;
    }
    return s;
  }

  static const int SELECT1_ERROR = -1;

  template <typename T> unsigned int select1(T x, unsigned int i)
  {
    // TODO: Fast implementation of select1.
    ASSERT(i > 0 && i <= sizeof(T) * 8, (i));
    for (unsigned int j = 0; j < sizeof(T) * 8; x >>= 1, ++j)
      if (x & 1)
        if (--i == 0)
          return j;
    return static_cast<unsigned int>(SELECT1_ERROR);
  }

  inline uint32_t PopCount(uint64_t x) noexcept
  {
    x = (x & 0x5555555555555555) + ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
    x = (x & 0x3333333333333333) + ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
    x = (x & 0x0F0F0F0F0F0F0F0F) + ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
    x = (x & 0x00FF00FF00FF00FF) + ((x & 0xFF00FF00FF00FF00) >> 8);
    x = (x & 0x0000FFFF0000FFFF) + ((x & 0xFFFF0000FFFF0000) >> 16);
    x = x + (x >> 32);
    return static_cast<uint32_t>(x);
  }

  inline uint8_t CeilLog(uint64_t x) noexcept
  {
#define CHECK_RSH(x, msb, offset) \
    if (x >> offset)              \
    {                             \
      x >>= offset;               \
      msb += offset;              \
    }

    uint8_t msb = 0;
    CHECK_RSH(x, msb, 32);
    CHECK_RSH(x, msb, 16);<commit_msg>[base] Fixed PopCount64.<commit_after>#pragma once
#include "base/assert.hpp"

#include <cstdint>
#include <limits>
#include <type_traits>

namespace bits
{
  // Count the number of 1 bits. Implementation: see Hacker's delight book.
  inline uint32_t PopCount(uint32_t x) noexcept
  {
    x -= ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x += (x >> 8);
    x += (x >> 16);
    return x & 0x3F;
  }

  inline uint32_t PopCount(uint8_t x) noexcept
  {
    return PopCount(static_cast<uint32_t>(x));
  }

  // Count the number of 1 bits in array p, length n bits.
  // There is a better implementation at hackersdelight.org
  inline uint32_t PopCount(uint32_t const * p, uint32_t n)
  {
    uint32_t s = 0;
    for (uint32_t i = 0; i < n; i += 31)
    {
      uint32_t lim = (n < i + 31 ? n : i + 31);
      uint32_t s8 = 0;
      uint32_t x = 0;
      for (uint32_t j = i; j < lim; ++j)
      {
        x = p[j];
        x -= ((x >> 1) & 0x55555555);
        x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
        x = (x + (x >> 4)) & 0x0F0F0F0F;
        s8 += x;
      }
      x = (s8 & 0x00FF00FF) + ((s8 >> 8) & 0x00FF00FF);
      x = (x & 0x0000ffff) + (x >> 16);
      s += x;
    }
    return s;
  }

  static const int SELECT1_ERROR = -1;

  template <typename T> unsigned int select1(T x, unsigned int i)
  {
    // TODO: Fast implementation of select1.
    ASSERT(i > 0 && i <= sizeof(T) * 8, (i));
    for (unsigned int j = 0; j < sizeof(T) * 8; x >>= 1, ++j)
      if (x & 1)
        if (--i == 0)
          return j;
    return static_cast<unsigned int>(SELECT1_ERROR);
  }

  inline uint32_t PopCount(uint64_t x) noexcept
  {
    x = x - ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = (x * 0x0101010101010101) >> 56;
    return static_cast<uint32_t>(x);
  }

  inline uint8_t CeilLog(uint64_t x) noexcept
  {
#define CHECK_RSH(x, msb, offset) \
    if (x >> offset)              \
    {                             \
      x >>= offset;               \
      msb += offset;              \
    }

    uint8_t msb = 0;
    CHECK_RSH(x, msb, 32);
    CHECK_RSH(x, msb, 16);
{'fraction_non_alphanumeric': 0.15659047212134158, 'fraction_numerical': 0.10510574663533433, 'mean_word_length': 2.0581319399085567, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 91, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 19, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5672731', 'n_tokens_mistral': 2256, 'n_tokens_neox': 1898, 'n_words': 517}