This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/util/bit_utils.hpp"
#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; } }