30 #define _GLIBCXX_BIT 1
32 #pragma GCC system_header
34 #if __cplusplus >= 201402L
39 namespace std _GLIBCXX_VISIBILITY(default)
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
52 #if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
53 #define __cpp_lib_bit_cast 201806L
56 template<
typename _To,
typename _From>
58 bit_cast(
const _From& __from) noexcept
60 return __builtin_bit_cast(_To, __from);
66 template<
typename _Tp>
68 __rotl(_Tp __x,
int __s) noexcept
71 const int __r = __s % _Nd;
75 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
77 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd));
80 template<
typename _Tp>
82 __rotr(_Tp __x,
int __s) noexcept
85 const int __r = __s % _Nd;
89 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
91 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd));
94 template<
typename _Tp>
96 __countl_zero(_Tp __x) noexcept
99 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
104 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
105 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
106 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
108 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
110 constexpr
int __diff = _Nd_u - _Nd;
111 return __builtin_clz(__x) - __diff;
113 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
115 constexpr
int __diff = _Nd_ul - _Nd;
116 return __builtin_clzl(__x) - __diff;
118 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
120 constexpr
int __diff = _Nd_ull - _Nd;
121 return __builtin_clzll(__x) - __diff;
125 static_assert(_Nd <= (2 * _Nd_ull),
126 "Maximum supported integer size is 128-bit");
128 unsigned long long __high = __x >> _Nd_ull;
131 constexpr
int __diff = (2 * _Nd_ull) - _Nd;
132 return __builtin_clzll(__high) - __diff;
134 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
135 unsigned long long __low = __x & __max_ull;
136 return (_Nd - _Nd_ull) + __builtin_clzll(__low);
140 template<
typename _Tp>
142 __countl_one(_Tp __x) noexcept
144 return std::__countl_zero<_Tp>((_Tp)~__x);
147 template<
typename _Tp>
149 __countr_zero(_Tp __x) noexcept
152 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
157 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
158 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
159 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
161 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
162 return __builtin_ctz(__x);
163 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
164 return __builtin_ctzl(__x);
165 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
166 return __builtin_ctzll(__x);
169 static_assert(_Nd <= (2 * _Nd_ull),
170 "Maximum supported integer size is 128-bit");
172 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
173 unsigned long long __low = __x & __max_ull;
175 return __builtin_ctzll(__low);
176 unsigned long long __high = __x >> _Nd_ull;
177 return __builtin_ctzll(__high) + _Nd_ull;
181 template<
typename _Tp>
183 __countr_one(_Tp __x) noexcept
185 return std::__countr_zero((_Tp)~__x);
188 template<
typename _Tp>
190 __popcount(_Tp __x) noexcept
193 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
195 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
196 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
197 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
199 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
200 return __builtin_popcount(__x);
201 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
202 return __builtin_popcountl(__x);
203 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
204 return __builtin_popcountll(__x);
207 static_assert(_Nd <= (2 * _Nd_ull),
208 "Maximum supported integer size is 128-bit");
210 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
211 unsigned long long __low = __x & __max_ull;
212 unsigned long long __high = __x >> _Nd_ull;
213 return __builtin_popcountll(__low) + __builtin_popcountll(__high);
217 template<
typename _Tp>
219 __has_single_bit(_Tp __x) noexcept
220 {
return std::__popcount(__x) == 1; }
222 template<
typename _Tp>
224 __bit_ceil(_Tp __x) noexcept
227 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
228 if (__x == 0 || __x == 1)
230 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
235 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
236 if (!__builtin_is_constant_evaluated())
238 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
241 using __promoted_type = decltype(__x << 1);
242 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
249 const int __extra_exp =
sizeof(__promoted_type) /
sizeof(_Tp) / 2;
250 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
252 return (_Tp)1u << __shift_exponent;
255 template<
typename _Tp>
257 __bit_floor(_Tp __x) noexcept
262 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
265 template<
typename _Tp>
267 __bit_width(_Tp __x) noexcept
270 return _Nd - std::__countl_zero(__x);
275 #if __cplusplus > 201703L
277 #define __cpp_lib_bitops 201907L
280 template<
typename _Tp,
typename _Up = _Tp>
281 using _If_is_unsigned_integer
282 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
288 template<
typename _Tp>
289 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
290 rotl(_Tp __x,
int __s) noexcept
291 {
return std::__rotl(__x, __s); }
294 template<
typename _Tp>
295 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
296 rotr(_Tp __x,
int __s) noexcept
297 {
return std::__rotr(__x, __s); }
302 template<
typename _Tp>
303 constexpr _If_is_unsigned_integer<_Tp, int>
304 countl_zero(_Tp __x) noexcept
305 {
return std::__countl_zero(__x); }
308 template<
typename _Tp>
309 constexpr _If_is_unsigned_integer<_Tp, int>
310 countl_one(_Tp __x) noexcept
311 {
return std::__countl_one(__x); }
314 template<
typename _Tp>
315 constexpr _If_is_unsigned_integer<_Tp, int>
316 countr_zero(_Tp __x) noexcept
317 {
return std::__countr_zero(__x); }
320 template<
typename _Tp>
321 constexpr _If_is_unsigned_integer<_Tp, int>
322 countr_one(_Tp __x) noexcept
323 {
return std::__countr_one(__x); }
326 template<
typename _Tp>
327 constexpr _If_is_unsigned_integer<_Tp, int>
328 popcount(_Tp __x) noexcept
329 {
return std::__popcount(__x); }
333 #define __cpp_lib_int_pow2 202002L
336 template<
typename _Tp>
337 constexpr _If_is_unsigned_integer<_Tp, bool>
338 has_single_bit(_Tp __x) noexcept
339 {
return std::__has_single_bit(__x); }
342 template<
typename _Tp>
343 constexpr _If_is_unsigned_integer<_Tp>
344 bit_ceil(_Tp __x) noexcept
345 {
return std::__bit_ceil(__x); }
348 template<
typename _Tp>
349 constexpr _If_is_unsigned_integer<_Tp>
350 bit_floor(_Tp __x) noexcept
351 {
return std::__bit_floor(__x); }
354 template<
typename _Tp>
355 constexpr _If_is_unsigned_integer<_Tp>
356 bit_width(_Tp __x) noexcept
357 {
return std::__bit_width(__x); }
359 #define __cpp_lib_endian 201907L
364 little = __ORDER_LITTLE_ENDIAN__,
365 big = __ORDER_BIG_ENDIAN__,
366 native = __BYTE_ORDER__
372 _GLIBCXX_END_NAMESPACE_VERSION
ISO C++ entities toplevel namespace is std.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.