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
72 template<
typename _To,
typename _From>
77 return __builtin_bit_cast(_To, __from);
81 #if __cplusplus > 202002L
82 #define __cpp_lib_byteswap 202110L
85 template<
typename _Tp>
87 constexpr enable_if_t<is_integral<_Tp>::value, _Tp>
88 byteswap(_Tp __value) noexcept
90 if constexpr (
sizeof(_Tp) == 1)
92 #if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
95 if constexpr (
sizeof(_Tp) == 2)
96 return __builtin_bswap16(__value);
97 if constexpr (sizeof(_Tp) == 4)
98 return __builtin_bswap32(__value);
99 if constexpr (sizeof(_Tp) == 8)
100 return __builtin_bswap64(__value);
101 if constexpr (sizeof(_Tp) == 16)
102 #if __has_builtin(__builtin_bswap128)
103 return __builtin_bswap128(__value);
105 return (__builtin_bswap64(__value >> 64)
106 | (
static_cast<_Tp
>(__builtin_bswap64(__value)) << 64));
112 using _Up =
typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
113 size_t __diff = __CHAR_BIT__ * (
sizeof(_Tp) - 1);
114 _Up __mask1 =
static_cast<unsigned char>(~0);
115 _Up __mask2 = __mask1 << __diff;
117 for (
size_t __i = 0; __i <
sizeof(_Tp) / 2; ++__i)
119 _Up __byte1 = __val & __mask1;
120 _Up __byte2 = __val & __mask2;
121 __val = (__val ^ __byte1 ^ __byte2
122 ^ (__byte1 << __diff) ^ (__byte2 >> __diff));
123 __mask1 <<= __CHAR_BIT__;
124 __mask2 >>= __CHAR_BIT__;
125 __diff -= 2 * __CHAR_BIT__;
133 template<
typename _Tp>
135 __rotl(_Tp __x,
int __s) noexcept
138 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
142 constexpr
unsigned __uNd = _Nd;
143 const unsigned __r = __s;
144 return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
146 const int __r = __s % _Nd;
150 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
152 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd));
155 template<
typename _Tp>
157 __rotr(_Tp __x,
int __s) noexcept
160 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
164 constexpr
unsigned __uNd = _Nd;
165 const unsigned __r = __s;
166 return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
168 const int __r = __s % _Nd;
172 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
174 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd));
177 template<
typename _Tp>
179 __countl_zero(_Tp __x) noexcept
182 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
187 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
188 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
189 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
191 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
193 constexpr
int __diff = _Nd_u - _Nd;
194 return __builtin_clz(__x) - __diff;
196 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
198 constexpr
int __diff = _Nd_ul - _Nd;
199 return __builtin_clzl(__x) - __diff;
201 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
203 constexpr
int __diff = _Nd_ull - _Nd;
204 return __builtin_clzll(__x) - __diff;
208 static_assert(_Nd <= (2 * _Nd_ull),
209 "Maximum supported integer size is 128-bit");
211 unsigned long long __high = __x >> _Nd_ull;
214 constexpr
int __diff = (2 * _Nd_ull) - _Nd;
215 return __builtin_clzll(__high) - __diff;
217 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
218 unsigned long long __low = __x & __max_ull;
219 return (_Nd - _Nd_ull) + __builtin_clzll(__low);
223 template<
typename _Tp>
225 __countl_one(_Tp __x) noexcept
227 return std::__countl_zero<_Tp>((_Tp)~__x);
230 template<
typename _Tp>
232 __countr_zero(_Tp __x) noexcept
235 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
240 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
241 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
242 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
244 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
245 return __builtin_ctz(__x);
246 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
247 return __builtin_ctzl(__x);
248 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
249 return __builtin_ctzll(__x);
252 static_assert(_Nd <= (2 * _Nd_ull),
253 "Maximum supported integer size is 128-bit");
255 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
256 unsigned long long __low = __x & __max_ull;
258 return __builtin_ctzll(__low);
259 unsigned long long __high = __x >> _Nd_ull;
260 return __builtin_ctzll(__high) + _Nd_ull;
264 template<
typename _Tp>
266 __countr_one(_Tp __x) noexcept
268 return std::__countr_zero((_Tp)~__x);
271 template<
typename _Tp>
273 __popcount(_Tp __x) noexcept
276 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
278 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
279 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
280 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
282 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
283 return __builtin_popcount(__x);
284 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
285 return __builtin_popcountl(__x);
286 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
287 return __builtin_popcountll(__x);
290 static_assert(_Nd <= (2 * _Nd_ull),
291 "Maximum supported integer size is 128-bit");
293 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
294 unsigned long long __low = __x & __max_ull;
295 unsigned long long __high = __x >> _Nd_ull;
296 return __builtin_popcountll(__low) + __builtin_popcountll(__high);
300 template<
typename _Tp>
302 __has_single_bit(_Tp __x) noexcept
303 {
return std::__popcount(__x) == 1; }
305 template<
typename _Tp>
307 __bit_ceil(_Tp __x) noexcept
310 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
311 if (__x == 0 || __x == 1)
313 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
318 if (!std::__is_constant_evaluated())
320 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
323 using __promoted_type = decltype(__x << 1);
324 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
331 const int __extra_exp =
sizeof(__promoted_type) /
sizeof(_Tp) / 2;
332 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
334 return (_Tp)1u << __shift_exponent;
337 template<
typename _Tp>
339 __bit_floor(_Tp __x) noexcept
344 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
347 template<
typename _Tp>
349 __bit_width(_Tp __x) noexcept
352 return _Nd - std::__countl_zero(__x);
357 #if __cplusplus > 201703L
359 #define __cpp_lib_bitops 201907L
362 template<
typename _Tp,
typename _Up = _Tp>
363 using _If_is_unsigned_integer
364 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
370 template<
typename _Tp>
371 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
372 rotl(_Tp __x,
int __s) noexcept
373 {
return std::__rotl(__x, __s); }
376 template<
typename _Tp>
377 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
378 rotr(_Tp __x,
int __s) noexcept
379 {
return std::__rotr(__x, __s); }
384 template<
typename _Tp>
385 constexpr _If_is_unsigned_integer<_Tp, int>
387 {
return std::__countl_zero(__x); }
390 template<
typename _Tp>
391 constexpr _If_is_unsigned_integer<_Tp, int>
393 {
return std::__countl_one(__x); }
396 template<
typename _Tp>
397 constexpr _If_is_unsigned_integer<_Tp, int>
399 {
return std::__countr_zero(__x); }
402 template<
typename _Tp>
403 constexpr _If_is_unsigned_integer<_Tp, int>
405 {
return std::__countr_one(__x); }
408 template<
typename _Tp>
409 constexpr _If_is_unsigned_integer<_Tp, int>
411 {
return std::__popcount(__x); }
415 #define __cpp_lib_int_pow2 202002L
418 template<
typename _Tp>
419 constexpr _If_is_unsigned_integer<_Tp, bool>
421 {
return std::__has_single_bit(__x); }
424 template<
typename _Tp>
425 constexpr _If_is_unsigned_integer<_Tp>
427 {
return std::__bit_ceil(__x); }
430 template<
typename _Tp>
431 constexpr _If_is_unsigned_integer<_Tp>
433 {
return std::__bit_floor(__x); }
436 template<
typename _Tp>
437 constexpr _If_is_unsigned_integer<_Tp>
439 {
return std::__bit_width(__x); }
441 #define __cpp_lib_endian 201907L
446 little = __ORDER_LITTLE_ENDIAN__,
447 big = __ORDER_BIG_ENDIAN__,
448 native = __BYTE_ORDER__
454 _GLIBCXX_END_NAMESPACE_VERSION
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 > rotl(_Tp __x, int __s) noexcept
Rotate x to the left by s bits.
constexpr _To bit_cast(const _From &__from) noexcept
Create a value of type To from the bits of from.
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, int > countl_zero(_Tp __x) noexcept
The number of contiguous zero bits, starting from the highest 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.
constexpr _If_is_unsigned_integer< _Tp > rotr(_Tp __x, int __s) noexcept
Rotate x to the right by s bits.
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