30 #define _GLIBCXX_BIT 1
32 #pragma GCC system_header
34 #if __cplusplus >= 201402L
45 template<
typename _Tp>
55 namespace std _GLIBCXX_VISIBILITY(default)
57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
68 #if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
69 #define __cpp_lib_bit_cast 201806L
78 template<
typename _To,
typename _From>
83 requires (
sizeof(_To) ==
sizeof(_From))
84 && __is_trivially_copyable(_To) && __is_trivially_copyable(_From)
87 return __builtin_bit_cast(_To, __from);
91 #if __cplusplus > 202002L
92 #define __cpp_lib_byteswap 202110L
101 template<
typename _Tp>
103 constexpr enable_if_t<is_integral<_Tp>::value, _Tp>
104 byteswap(_Tp __value) noexcept
106 if constexpr (
sizeof(_Tp) == 1)
108 #if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
111 if constexpr (
sizeof(_Tp) == 2)
112 return __builtin_bswap16(__value);
113 if constexpr (sizeof(_Tp) == 4)
114 return __builtin_bswap32(__value);
115 if constexpr (sizeof(_Tp) == 8)
116 return __builtin_bswap64(__value);
117 if constexpr (sizeof(_Tp) == 16)
118 #if __has_builtin(__builtin_bswap128)
119 return __builtin_bswap128(__value);
121 return (__builtin_bswap64(__value >> 64)
122 | (
static_cast<_Tp
>(__builtin_bswap64(__value)) << 64));
128 using _Up =
typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
129 size_t __diff = __CHAR_BIT__ * (
sizeof(_Tp) - 1);
130 _Up __mask1 =
static_cast<unsigned char>(~0);
131 _Up __mask2 = __mask1 << __diff;
133 for (
size_t __i = 0; __i <
sizeof(_Tp) / 2; ++__i)
135 _Up __byte1 = __val & __mask1;
136 _Up __byte2 = __val & __mask2;
137 __val = (__val ^ __byte1 ^ __byte2
138 ^ (__byte1 << __diff) ^ (__byte2 >> __diff));
139 __mask1 <<= __CHAR_BIT__;
140 __mask2 >>= __CHAR_BIT__;
141 __diff -= 2 * __CHAR_BIT__;
149 template<
typename _Tp>
151 __rotl(_Tp __x,
int __s) noexcept
154 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
158 constexpr
unsigned __uNd = _Nd;
159 const unsigned __r = __s;
160 return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
162 const int __r = __s % _Nd;
166 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
168 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd));
171 template<
typename _Tp>
173 __rotr(_Tp __x,
int __s) noexcept
176 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
180 constexpr
unsigned __uNd = _Nd;
181 const unsigned __r = __s;
182 return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
184 const int __r = __s % _Nd;
188 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
190 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd));
193 template<
typename _Tp>
195 __countl_zero(_Tp __x) noexcept
198 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
203 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
204 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
205 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
207 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
209 constexpr
int __diff = _Nd_u - _Nd;
210 return __builtin_clz(__x) - __diff;
212 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
214 constexpr
int __diff = _Nd_ul - _Nd;
215 return __builtin_clzl(__x) - __diff;
217 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
219 constexpr
int __diff = _Nd_ull - _Nd;
220 return __builtin_clzll(__x) - __diff;
224 static_assert(_Nd <= (2 * _Nd_ull),
225 "Maximum supported integer size is 128-bit");
227 unsigned long long __high = __x >> _Nd_ull;
230 constexpr
int __diff = (2 * _Nd_ull) - _Nd;
231 return __builtin_clzll(__high) - __diff;
233 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
234 unsigned long long __low = __x & __max_ull;
235 return (_Nd - _Nd_ull) + __builtin_clzll(__low);
239 template<
typename _Tp>
241 __countl_one(_Tp __x) noexcept
243 return std::__countl_zero<_Tp>((_Tp)~__x);
246 template<
typename _Tp>
248 __countr_zero(_Tp __x) noexcept
251 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
256 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
257 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
258 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
260 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
261 return __builtin_ctz(__x);
262 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
263 return __builtin_ctzl(__x);
264 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
265 return __builtin_ctzll(__x);
268 static_assert(_Nd <= (2 * _Nd_ull),
269 "Maximum supported integer size is 128-bit");
271 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
272 unsigned long long __low = __x & __max_ull;
274 return __builtin_ctzll(__low);
275 unsigned long long __high = __x >> _Nd_ull;
276 return __builtin_ctzll(__high) + _Nd_ull;
280 template<
typename _Tp>
282 __countr_one(_Tp __x) noexcept
284 return std::__countr_zero((_Tp)~__x);
287 template<
typename _Tp>
289 __popcount(_Tp __x) noexcept
292 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
294 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
295 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
296 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
298 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
299 return __builtin_popcount(__x);
300 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
301 return __builtin_popcountl(__x);
302 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
303 return __builtin_popcountll(__x);
306 static_assert(_Nd <= (2 * _Nd_ull),
307 "Maximum supported integer size is 128-bit");
309 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
310 unsigned long long __low = __x & __max_ull;
311 unsigned long long __high = __x >> _Nd_ull;
312 return __builtin_popcountll(__low) + __builtin_popcountll(__high);
316 template<
typename _Tp>
318 __has_single_bit(_Tp __x) noexcept
319 {
return std::__popcount(__x) == 1; }
321 template<
typename _Tp>
323 __bit_ceil(_Tp __x) noexcept
326 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
327 if (__x == 0 || __x == 1)
329 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
334 if (!std::__is_constant_evaluated())
336 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
339 using __promoted_type = decltype(__x << 1);
340 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
347 const int __extra_exp =
sizeof(__promoted_type) /
sizeof(_Tp) / 2;
348 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
350 return (_Tp)1u << __shift_exponent;
353 template<
typename _Tp>
355 __bit_floor(_Tp __x) noexcept
360 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
363 template<
typename _Tp>
365 __bit_width(_Tp __x) noexcept
368 return _Nd - std::__countl_zero(__x);
373 #if __cplusplus > 201703L
375 #define __cpp_lib_bitops 201907L
378 template<
typename _Tp,
typename _Up = _Tp>
379 using _If_is_unsigned_integer
380 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
386 template<
typename _Tp>
387 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
388 rotl(_Tp __x,
int __s) noexcept
389 {
return std::__rotl(__x, __s); }
392 template<
typename _Tp>
393 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
394 rotr(_Tp __x,
int __s) noexcept
395 {
return std::__rotr(__x, __s); }
400 template<
typename _Tp>
401 constexpr _If_is_unsigned_integer<_Tp, int>
402 countl_zero(_Tp __x) noexcept
403 {
return std::__countl_zero(__x); }
406 template<
typename _Tp>
407 constexpr _If_is_unsigned_integer<_Tp, int>
409 {
return std::__countl_one(__x); }
412 template<
typename _Tp>
413 constexpr _If_is_unsigned_integer<_Tp, int>
415 {
return std::__countr_zero(__x); }
418 template<
typename _Tp>
419 constexpr _If_is_unsigned_integer<_Tp, int>
421 {
return std::__countr_one(__x); }
424 template<
typename _Tp>
425 constexpr _If_is_unsigned_integer<_Tp, int>
427 {
return std::__popcount(__x); }
431 #define __cpp_lib_int_pow2 202002L
434 template<
typename _Tp>
435 constexpr _If_is_unsigned_integer<_Tp, bool>
437 {
return std::__has_single_bit(__x); }
440 template<
typename _Tp>
441 constexpr _If_is_unsigned_integer<_Tp>
443 {
return std::__bit_ceil(__x); }
446 template<
typename _Tp>
447 constexpr _If_is_unsigned_integer<_Tp>
449 {
return std::__bit_floor(__x); }
452 template<
typename _Tp>
453 constexpr _If_is_unsigned_integer<_Tp>
455 {
return std::__bit_width(__x); }
457 #define __cpp_lib_endian 201907L
468 little = __ORDER_LITTLE_ENDIAN__,
469 big = __ORDER_BIG_ENDIAN__,
470 native = __BYTE_ORDER__
476 _GLIBCXX_END_NAMESPACE_VERSION
constexpr _To bit_cast(const _From &__from) noexcept requires(sizeof(_To)
Create a value of type To from the bits of from.
constexpr _If_is_unsigned_integer< _Tp, bool > has_single_bit(_Tp __x) noexcept
True if x is a power of two, false otherwise.
constexpr _If_is_unsigned_integer< _Tp > bit_ceil(_Tp __x) noexcept
The smallest power-of-two not less than x.
constexpr _If_is_unsigned_integer< _Tp, int > popcount(_Tp __x) noexcept
The number of bits set in x.
constexpr _If_is_unsigned_integer< _Tp, int > countr_one(_Tp __x) noexcept
The number of contiguous one bits, starting from the lowest bit.
constexpr _If_is_unsigned_integer< _Tp > bit_floor(_Tp __x) noexcept
The largest power-of-two not greater than x.
constexpr _If_is_unsigned_integer< _Tp > bit_width(_Tp __x) noexcept
The smallest integer greater than the base-2 logarithm of x.
constexpr _If_is_unsigned_integer< _Tp, int > countl_one(_Tp __x) noexcept
The number of contiguous one bits, starting from the highest bit.
constexpr _If_is_unsigned_integer< _Tp, int > countr_zero(_Tp __x) noexcept
The number of contiguous zero bits, starting from the lowest bit.
endian
Byte order constants.
ISO C++ entities toplevel namespace is std.
GNU extensions for public use.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
Properties of fundamental types.
static constexpr _Tp max() noexcept