other/popcount.cpp

• View this file on GitHub
• Last update: 2020-03-10 16:21:51+09:00

Depends on

• other/int_alias.cpp

Required by

• Bit Vector (data_structure/bit_vector.cpp)
• Wavelet Matrix (data_structure/wavelet_matrix.cpp)

Verified with

• test/wavelet_matrix.quantile.test.cpp
• test/wavelet_matrix.rangefreq.test.cpp
• test/wavelet_matrix.select.test.cpp

Code

#pragma once

#include "other/int_alias.cpp"

usize popcount(u64 x) {
#ifdef __GNUC__
  return __builtin_popcountll(x);
#else
  x -= x >> 1 & 0x5555555555555555;
  x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
  x = x + (x >> 4) & 0x0F0F0F0F0F0F0F0F;
  return x * 0x0101010101010101 >> 56 & 0x7f;
#endif
}

#line 2 "other/popcount.cpp"

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 4 "other/popcount.cpp"

usize popcount(u64 x) {
#ifdef __GNUC__
  return __builtin_popcountll(x);
#else
  x -= x >> 1 & 0x5555555555555555;
  x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
  x = x + (x >> 4) & 0x0F0F0F0F0F0F0F0F;
  return x * 0x0101010101010101 >> 56 & 0x7f;
#endif
}

Back to top page