bit/bitcount.hpp

• View this file on GitHub
• Last update: 2025-04-24 20:44:35+09:00
• Include: #include "bit/bitcount.hpp"

Depends on

• type_traits/integral.hpp

Required by

• convolution/convolution.hpp
• convolution/convolution_arb.hpp
• convolution/convolution_int.hpp
• convolution/multi_convolution_truncated.hpp
• data_structure/bit_vector.hpp
• data_structure/my_bitset.hpp
• data_structure/w_ary_tree.hpp
• data_structure/wavelet_matrix.hpp
• fps/fps_arb.hpp
• fps/fps_multivariate.hpp
• fps/fps_ntt_friendly.hpp
• fps/fps_sparsity_detector.hpp
• math_mod/comb_large.hpp
• 掃き出し (matrix/matrix_F2.hpp)
• 文字の一点更新が可能文字列に対する動的なローリングハッシュ (string/dynamic_rolling_hash.hpp)

Verified with

• verify/unit_test/bit_vector.test.cpp
• verify/unit_test/large_fact_arb_mod.test.cpp
• verify/unit_test/wavelet_matrix.test.cpp
• verify/yosupo_convolution/convolution_arbitrary.test.cpp
• verify/yosupo_convolution/convolution_multi_truncated.test.cpp
• verify/yosupo_convolution/convolution_ntt_friendly.test.cpp
• verify/yosupo_ds/ds_predecessor_problem.test.cpp
• verify/yosupo_fps/fps_composition.test.cpp
• verify/yosupo_fps/fps_composition_inv.test.cpp
• verify/yosupo_fps/fps_exp.test.cpp
• verify/yosupo_fps/fps_exp_arb.test.cpp
• verify/yosupo_fps/fps_inv.test.cpp
• verify/yosupo_fps/fps_inv_arb.test.cpp
• verify/yosupo_fps/fps_log.test.cpp
• verify/yosupo_fps/fps_log_arb.test.cpp
• verify/yosupo_fps/fps_multipoint_evaluation.test.cpp
• verify/yosupo_fps/fps_multipoint_evaluation_geometric.test.cpp
• verify/yosupo_fps/fps_pow.test.cpp
• verify/yosupo_fps/fps_product_of_polynomial_sequence.test.cpp
• verify/yosupo_fps/fps_sparse_exp.test.cpp
• verify/yosupo_fps/fps_sparse_inv.test.cpp
• verify/yosupo_fps/fps_sparse_log.test.cpp
• verify/yosupo_fps/fps_sparse_pow.test.cpp
• verify/yosupo_fps/fps_sprase_sqrt.test.cpp
• verify/yosupo_fps/fps_sqrt.test.cpp
• verify/yosupo_fps/poly_division.test.cpp
• verify/yosupo_fps/poly_interpolation.test.cpp
• verify/yosupo_fps/poly_interpolation_geometric.test.cpp
• verify/yosupo_fps/poly_inv.test.cpp
• verify/yosupo_fps/poly_root_finding.test.cpp
• verify/yosupo_fps/poly_sample_point_shift.test.cpp
• verify/yosupo_fps/poly_taylor_shift.test.cpp
• verify/yosupo_fps/poly_to_newton_basis.test.cpp
• verify/yosupo_linalg/matrix_det_f2.test.cpp
• verify/yosupo_linalg/matrix_inv_f2.test.cpp
• verify/yosupo_linalg/matrix_product_f2.test.cpp
• verify/yosupo_linalg/matrix_rank_F2.test.cpp
• verify/yosupo_linalg/solution_of_linear_equations_F2.test.cpp
• verify/yosupo_math/enumerate_bell_number.test.cpp
• verify/yosupo_math/enumerate_stirling_number_of_the_first_kind.test.cpp
• verify/yosupo_math/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/yosupo_math/many_factrials.test.cpp
• verify/yuki/yuki_1510.test.cpp

Code

#ifndef KK2_BIT_BITCOUNT_HPP
#define KK2_BIT_BITCOUNT_HPP 1

#include <cassert>

#include "../type_traits/integral.hpp"

namespace kk2 {

template <typename T> constexpr int ctz(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    if constexpr (sizeof(T) <= 4) {
        return __builtin_ctz(x);
    } else if constexpr (sizeof(T) <= 8) {
        return __builtin_ctzll(x);
    } else {
        if (x & 0xffffffffffffffff)
            return __builtin_ctzll((unsigned long long)(x & 0xffffffffffffffff));
        return 64 + __builtin_ctzll((unsigned long long)(x >> 64));
    }
}

template <typename T> constexpr int lsb(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    return ctz(x);
}

template <typename T> constexpr int clz(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    if constexpr (sizeof(T) <= 4) {
        return __builtin_clz(x);
    } else if constexpr (sizeof(T) <= 8) {
        return __builtin_clzll(x);
    } else {
        if (x >> 64) return __builtin_clzll((unsigned long long)(x >> 64));
        return 64 + __builtin_clzll((unsigned long long)(x & 0xffffffffffffffff));
    }
}

template <typename T> constexpr int msb(T x) {
    static_assert(is_integral<T>::value);
    assert(x != T(0));

    return sizeof(T) * 8 - 1 - clz(x);
}

template <typename T> constexpr int popcount(T x) {
    static_assert(is_integral<T>::value);

    if constexpr (sizeof(T) <= 4) {
        return __builtin_popcount(x);
    } else if constexpr (sizeof(T) <= 8) {
        return __builtin_popcountll(x);
    } else {
        return __builtin_popcountll((unsigned long long)(x >> 64))
               + __builtin_popcountll((unsigned long long)(x & 0xffffffffffffffff));
    }
}

}; // namespace kk2

#endif // KK2_BIT_BITCOUNT_HPP

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: type_traits/integral.hpp: line 4: #pragma once found in a non-first line

Back to top page