cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:warning: Bit Utils
(library/util/bit_utils.hpp)

Bit Utils

Depends on

Code

#ifndef SUISEN_BIT_UTILS
#define SUISEN_BIT_UTILS

#ifdef _MSC_VER
#  include <intrin.h>
#else
#  include <x86intrin.h>
#endif
#include "library/type_traits/type_traits.hpp"
namespace suisen {
    template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
    __attribute__((target("popcnt"))) constexpr int popcount(const T x) { return _mm_popcnt_u32(x); }
    template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
    __attribute__((target("popcnt"))) constexpr int popcount(const T x) { return _mm_popcnt_u64(x); }
    template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
    constexpr int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bitnum_v<T>; }
    template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
    constexpr int count_lz(const T x) { return x ? __builtin_clzll(x) : suisen::bitnum_v<T>; }
    template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
    constexpr int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bitnum_v<T>; }
    template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
    constexpr int count_tz(const T x) { return x ? __builtin_ctzll(x) : suisen::bitnum_v<T>; }
    template <typename T> constexpr int floor_log2(const T x) { return suisen::bitnum_v<T> -1 - count_lz(x); }
    template <typename T> constexpr int ceil_log2(const T x) { return floor_log2(x) + ((x & -x) != x); }
    template <typename T> constexpr int kth_bit(const T x, const unsigned int k) { return (x >> k) & 1; }
    template <typename T> constexpr int parity(const T x) { return popcount(x) & 1; }
}
#endif // SUISEN_BIT_UTILS
#line 1 "library/util/bit_utils.hpp"



#ifdef _MSC_VER
#  include <intrin.h>
#else
#  include <x86intrin.h>
#endif
#line 1 "library/type_traits/type_traits.hpp"



#include <limits>
#include <iostream>
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

#line 10 "library/util/bit_utils.hpp"
namespace suisen {
    template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
    __attribute__((target("popcnt"))) constexpr int popcount(const T x) { return _mm_popcnt_u32(x); }
    template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
    __attribute__((target("popcnt"))) constexpr int popcount(const T x) { return _mm_popcnt_u64(x); }
    template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
    constexpr int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bitnum_v<T>; }
    template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
    constexpr int count_lz(const T x) { return x ? __builtin_clzll(x) : suisen::bitnum_v<T>; }
    template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
    constexpr int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bitnum_v<T>; }
    template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
    constexpr int count_tz(const T x) { return x ? __builtin_ctzll(x) : suisen::bitnum_v<T>; }
    template <typename T> constexpr int floor_log2(const T x) { return suisen::bitnum_v<T> -1 - count_lz(x); }
    template <typename T> constexpr int ceil_log2(const T x) { return floor_log2(x) + ((x & -x) != x); }
    template <typename T> constexpr int kth_bit(const T x, const unsigned int k) { return (x >> k) & 1; }
    template <typename T> constexpr int parity(const T x) { return popcount(x) & 1; }
}
Back to top page