utility/countl_zero.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/convolution_arbitrary_mod.cpp
• algorithm/convolution_int.cpp
• algorithm/convolution_mod.cpp
• algorithm/ranked_subset_mobius_transform.cpp
• algorithm/ranked_subset_zeta_transform.cpp
• algorithm/subset_convolution.cpp
• container/dual_segment_tree.cpp
• container/fenwick_tree.cpp
• container/integer_hash_table.cpp
• container/lazy_segment_tree.cpp
• container/segment_tree.cpp
• container/segment_tree_beats.cpp
• container/sparse_table.cpp
• math/prime_sieve.cpp
• utility/auto_realloc.cpp
• utility/bit_width.cpp
• utility/ceil_log2.cpp

Verified with

• test/convolution_arbitrary_mod.test.cpp
• test/convolution_mod.test.cpp
• test/dual_segment_tree.test.cpp
• test/fenwick_tree.test.cpp
• test/heavy_light_decomposition.test.cpp
• test/integer_hash_table.test.cpp
• test/integer_hash_table_verbose.test.cpp
• test/larsch.test.cpp
• test/lazy_segment_tree.test.cpp
• test/prime_sieve.test.cpp
• test/segment_tree.test.cpp
• test/segment_tree_beats.test.cpp
• test/sparse_table.test.cpp
• test/subset_convolution.test.cpp

Code

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

TARGET_AVX2 constexpr int countl_zero(u64 x) {
#ifdef __GNUC__
    return x == 0 ? 64 : __builtin_clzll(x);
#else
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return 64 - countr_zero(~x);
#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/countl_zero.cpp"

TARGET_AVX2 constexpr int countl_zero(u64 x) {
#ifdef __GNUC__
    return x == 0 ? 64 : __builtin_clzll(x);
#else
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return 64 - countr_zero(~x);
#endif
}

Back to top page