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>
75 bit_cast(
const _From& __from) noexcept
77 return __builtin_bit_cast(_To, __from);
83 template<
typename _Tp>
85 __rotl(_Tp __x,
int __s) noexcept
88 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
92 constexpr
unsigned __uNd = _Nd;
93 const unsigned __r = __s;
94 return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
96 const int __r = __s % _Nd;
100 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
102 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd));
105 template<
typename _Tp>
107 __rotr(_Tp __x,
int __s) noexcept
110 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
114 constexpr
unsigned __uNd = _Nd;
115 const unsigned __r = __s;
116 return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
118 const int __r = __s % _Nd;
122 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
124 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd));
127 template<
typename _Tp>
129 __countl_zero(_Tp __x) noexcept
132 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
137 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
138 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
139 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
141 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
143 constexpr
int __diff = _Nd_u - _Nd;
144 return __builtin_clz(__x) - __diff;
146 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
148 constexpr
int __diff = _Nd_ul - _Nd;
149 return __builtin_clzl(__x) - __diff;
151 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
153 constexpr
int __diff = _Nd_ull - _Nd;
154 return __builtin_clzll(__x) - __diff;
158 static_assert(_Nd <= (2 * _Nd_ull),
159 "Maximum supported integer size is 128-bit");
161 unsigned long long __high = __x >> _Nd_ull;
164 constexpr
int __diff = (2 * _Nd_ull) - _Nd;
165 return __builtin_clzll(__high) - __diff;
167 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
168 unsigned long long __low = __x & __max_ull;
169 return (_Nd - _Nd_ull) + __builtin_clzll(__low);
173 template<
typename _Tp>
175 __countl_one(_Tp __x) noexcept
177 return std::__countl_zero<_Tp>((_Tp)~__x);
180 template<
typename _Tp>
182 __countr_zero(_Tp __x) noexcept
185 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
190 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
191 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
192 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
194 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
195 return __builtin_ctz(__x);
196 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
197 return __builtin_ctzl(__x);
198 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
199 return __builtin_ctzll(__x);
202 static_assert(_Nd <= (2 * _Nd_ull),
203 "Maximum supported integer size is 128-bit");
205 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
206 unsigned long long __low = __x & __max_ull;
208 return __builtin_ctzll(__low);
209 unsigned long long __high = __x >> _Nd_ull;
210 return __builtin_ctzll(__high) + _Nd_ull;
214 template<
typename _Tp>
216 __countr_one(_Tp __x) noexcept
218 return std::__countr_zero((_Tp)~__x);
221 template<
typename _Tp>
223 __popcount(_Tp __x) noexcept
226 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
228 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
229 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
230 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
232 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
233 return __builtin_popcount(__x);
234 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
235 return __builtin_popcountl(__x);
236 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
237 return __builtin_popcountll(__x);
240 static_assert(_Nd <= (2 * _Nd_ull),
241 "Maximum supported integer size is 128-bit");
243 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
244 unsigned long long __low = __x & __max_ull;
245 unsigned long long __high = __x >> _Nd_ull;
246 return __builtin_popcountll(__low) + __builtin_popcountll(__high);
250 template<
typename _Tp>
252 __has_single_bit(_Tp __x) noexcept
253 {
return std::__popcount(__x) == 1; }
255 template<
typename _Tp>
257 __bit_ceil(_Tp __x) noexcept
260 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
261 if (__x == 0 || __x == 1)
263 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
268 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
269 if (!__builtin_is_constant_evaluated())
271 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
274 using __promoted_type = decltype(__x << 1);
275 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
282 const int __extra_exp =
sizeof(__promoted_type) /
sizeof(_Tp) / 2;
283 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
285 return (_Tp)1u << __shift_exponent;
288 template<
typename _Tp>
290 __bit_floor(_Tp __x) noexcept
295 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
298 template<
typename _Tp>
300 __bit_width(_Tp __x) noexcept
303 return _Nd - std::__countl_zero(__x);
308 #if __cplusplus > 201703L
310 #define __cpp_lib_bitops 201907L
313 template<
typename _Tp,
typename _Up = _Tp>
314 using _If_is_unsigned_integer
315 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
321 template<
typename _Tp>
322 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
323 rotl(_Tp __x,
int __s) noexcept
324 {
return std::__rotl(__x, __s); }
327 template<
typename _Tp>
328 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
329 rotr(_Tp __x,
int __s) noexcept
330 {
return std::__rotr(__x, __s); }
335 template<
typename _Tp>
336 constexpr _If_is_unsigned_integer<_Tp, int>
337 countl_zero(_Tp __x) noexcept
338 {
return std::__countl_zero(__x); }
341 template<
typename _Tp>
342 constexpr _If_is_unsigned_integer<_Tp, int>
343 countl_one(_Tp __x) noexcept
344 {
return std::__countl_one(__x); }
347 template<
typename _Tp>
348 constexpr _If_is_unsigned_integer<_Tp, int>
349 countr_zero(_Tp __x) noexcept
350 {
return std::__countr_zero(__x); }
353 template<
typename _Tp>
354 constexpr _If_is_unsigned_integer<_Tp, int>
355 countr_one(_Tp __x) noexcept
356 {
return std::__countr_one(__x); }
359 template<
typename _Tp>
360 constexpr _If_is_unsigned_integer<_Tp, int>
361 popcount(_Tp __x) noexcept
362 {
return std::__popcount(__x); }
366 #define __cpp_lib_int_pow2 202002L
369 template<
typename _Tp>
370 constexpr _If_is_unsigned_integer<_Tp, bool>
371 has_single_bit(_Tp __x) noexcept
372 {
return std::__has_single_bit(__x); }
375 template<
typename _Tp>
376 constexpr _If_is_unsigned_integer<_Tp>
377 bit_ceil(_Tp __x) noexcept
378 {
return std::__bit_ceil(__x); }
381 template<
typename _Tp>
382 constexpr _If_is_unsigned_integer<_Tp>
383 bit_floor(_Tp __x) noexcept
384 {
return std::__bit_floor(__x); }
387 template<
typename _Tp>
388 constexpr _If_is_unsigned_integer<_Tp>
389 bit_width(_Tp __x) noexcept
390 {
return std::__bit_width(__x); }
392 #define __cpp_lib_endian 201907L
397 little = __ORDER_LITTLE_ENDIAN__,
398 big = __ORDER_BIG_ENDIAN__,
399 native = __BYTE_ORDER__
405 _GLIBCXX_END_NAMESPACE_VERSION
409 #endif // _GLIBCXX_BIT
static constexpr _Tp max() noexcept
Properties of fundamental types.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.