utility/popcount.cpp

• View this file on GitHub
• Last update: 2022-01-07 21:48:21+09:00

Depends on

• internal/enable_avx2.cpp
• utility/int_alias.cpp

Required by

• algorithm/ranked_subset_mobius_transform.cpp
• algorithm/ranked_subset_zeta_transform.cpp
• algorithm/subset_convolution.cpp

Verified with

• test/subset_convolution.test.cpp

Code

#pragma once
#include "../internal/enable_avx2.cpp"
#include "int_alias.cpp"

TARGET_AVX2 constexpr int 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 "internal/enable_avx2.cpp"

#ifdef ENABLE_AVX2
#define TARGET_AVX2 __attribute__((target("avx2")))
#else
#define TARGET_AVX2
#endif
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 4 "utility/popcount.cpp"

TARGET_AVX2 constexpr int 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