utility/countr_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
• container/dual_segment_tree.cpp
• container/lazy_segment_tree.cpp
• container/segment_tree_beats.cpp
• internal/modulo_transform.cpp

Verified with

• test/convolution_arbitrary_mod.test.cpp
• test/convolution_mod.test.cpp
• test/dual_segment_tree.test.cpp
• test/lazy_segment_tree.test.cpp
• test/segment_tree_beats.test.cpp

Code

#pragma once
#include <array>
#include "../internal/enable_avx2.cpp"
#include "int_alias.cpp"

constexpr int countr_zero(u64 x) {
    if (x == 0) return 64;
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    constexpr std::array<int, 64> table = {0,  1,  2,  7,  3,  13, 8,  27, 4,  33, 14, 36, 9,  49, 28, 19,
                                             5,  25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57,
                                             63, 6,  12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56,
                                             62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58};
    return table[(x & (~x + 1)) * 0x218A7A392DD9ABF >> 58 & 0x3F];
#endif
}

#line 2 "utility/countr_zero.cpp"
#include <array>
#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 5 "utility/countr_zero.cpp"

constexpr int countr_zero(u64 x) {
    if (x == 0) return 64;
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    constexpr std::array<int, 64> table = {0,  1,  2,  7,  3,  13, 8,  27, 4,  33, 14, 36, 9,  49, 28, 19,
                                             5,  25, 34, 17, 15, 53, 37, 55, 10, 46, 50, 39, 29, 42, 20, 57,
                                             63, 6,  12, 26, 32, 35, 48, 18, 24, 16, 52, 54, 45, 38, 41, 56,
                                             62, 11, 31, 47, 23, 51, 44, 40, 61, 30, 22, 43, 60, 21, 59, 58};
    return table[(x & (~x + 1)) * 0x218A7A392DD9ABF >> 58 & 0x3F];
#endif
}

Back to top page