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 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
75 constexpr
unsigned __uNd = _Nd;
76 const unsigned __r = __s;
77 return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
79 const int __r = __s % _Nd;
83 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
85 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd));
88 template<
typename _Tp>
90 __rotr(_Tp __x,
int __s) noexcept
93 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
97 constexpr
unsigned __uNd = _Nd;
98 const unsigned __r = __s;
99 return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
101 const int __r = __s % _Nd;
105 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
107 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd));
110 template<
typename _Tp>
112 __countl_zero(_Tp __x) noexcept
115 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
120 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
121 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
122 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
124 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
126 constexpr
int __diff = _Nd_u - _Nd;
127 return __builtin_clz(__x) - __diff;
129 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
131 constexpr
int __diff = _Nd_ul - _Nd;
132 return __builtin_clzl(__x) - __diff;
134 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
136 constexpr
int __diff = _Nd_ull - _Nd;
137 return __builtin_clzll(__x) - __diff;
141 static_assert(_Nd <= (2 * _Nd_ull),
142 "Maximum supported integer size is 128-bit");
144 unsigned long long __high = __x >> _Nd_ull;
147 constexpr
int __diff = (2 * _Nd_ull) - _Nd;
148 return __builtin_clzll(__high) - __diff;
150 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
151 unsigned long long __low = __x & __max_ull;
152 return (_Nd - _Nd_ull) + __builtin_clzll(__low);
156 template<
typename _Tp>
158 __countl_one(_Tp __x) noexcept
160 return std::__countl_zero<_Tp>((_Tp)~__x);
163 template<
typename _Tp>
165 __countr_zero(_Tp __x) noexcept
168 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
173 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
174 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
175 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
177 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
178 return __builtin_ctz(__x);
179 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
180 return __builtin_ctzl(__x);
181 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
182 return __builtin_ctzll(__x);
185 static_assert(_Nd <= (2 * _Nd_ull),
186 "Maximum supported integer size is 128-bit");
188 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
189 unsigned long long __low = __x & __max_ull;
191 return __builtin_ctzll(__low);
192 unsigned long long __high = __x >> _Nd_ull;
193 return __builtin_ctzll(__high) + _Nd_ull;
197 template<
typename _Tp>
199 __countr_one(_Tp __x) noexcept
201 return std::__countr_zero((_Tp)~__x);
204 template<
typename _Tp>
206 __popcount(_Tp __x) noexcept
209 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
211 constexpr
auto _Nd_ull = __int_traits<unsigned long long>::__digits;
212 constexpr
auto _Nd_ul = __int_traits<unsigned long>::__digits;
213 constexpr
auto _Nd_u = __int_traits<unsigned>::__digits;
215 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
216 return __builtin_popcount(__x);
217 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
218 return __builtin_popcountl(__x);
219 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
220 return __builtin_popcountll(__x);
223 static_assert(_Nd <= (2 * _Nd_ull),
224 "Maximum supported integer size is 128-bit");
226 constexpr
auto __max_ull = __int_traits<unsigned long long>::__max;
227 unsigned long long __low = __x & __max_ull;
228 unsigned long long __high = __x >> _Nd_ull;
229 return __builtin_popcountll(__low) + __builtin_popcountll(__high);
233 template<
typename _Tp>
235 __has_single_bit(_Tp __x) noexcept
236 {
return std::__popcount(__x) == 1; }
238 template<
typename _Tp>
240 __bit_ceil(_Tp __x) noexcept
243 constexpr
auto _Nd = __int_traits<_Tp>::__digits;
244 if (__x == 0 || __x == 1)
246 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
251 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
252 if (!__builtin_is_constant_evaluated())
254 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
257 using __promoted_type = decltype(__x << 1);
258 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
265 const int __extra_exp =
sizeof(__promoted_type) /
sizeof(_Tp) / 2;
266 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
268 return (_Tp)1u << __shift_exponent;
271 template<
typename _Tp>
273 __bit_floor(_Tp __x) noexcept
278 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
281 template<
typename _Tp>
283 __bit_width(_Tp __x) noexcept
286 return _Nd - std::__countl_zero(__x);
291 #if __cplusplus > 201703L
293 #define __cpp_lib_bitops 201907L
296 template<
typename _Tp,
typename _Up = _Tp>
297 using _If_is_unsigned_integer
298 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
304 template<
typename _Tp>
305 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
306 rotl(_Tp __x,
int __s) noexcept
307 {
return std::__rotl(__x, __s); }
310 template<
typename _Tp>
311 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
312 rotr(_Tp __x,
int __s) noexcept
313 {
return std::__rotr(__x, __s); }
318 template<
typename _Tp>
319 constexpr _If_is_unsigned_integer<_Tp, int>
320 countl_zero(_Tp __x) noexcept
321 {
return std::__countl_zero(__x); }
324 template<
typename _Tp>
325 constexpr _If_is_unsigned_integer<_Tp, int>
326 countl_one(_Tp __x) noexcept
327 {
return std::__countl_one(__x); }
330 template<
typename _Tp>
331 constexpr _If_is_unsigned_integer<_Tp, int>
332 countr_zero(_Tp __x) noexcept
333 {
return std::__countr_zero(__x); }
336 template<
typename _Tp>
337 constexpr _If_is_unsigned_integer<_Tp, int>
338 countr_one(_Tp __x) noexcept
339 {
return std::__countr_one(__x); }
342 template<
typename _Tp>
343 constexpr _If_is_unsigned_integer<_Tp, int>
344 popcount(_Tp __x) noexcept
345 {
return std::__popcount(__x); }
349 #define __cpp_lib_int_pow2 202002L
352 template<
typename _Tp>
353 constexpr _If_is_unsigned_integer<_Tp, bool>
354 has_single_bit(_Tp __x) noexcept
355 {
return std::__has_single_bit(__x); }
358 template<
typename _Tp>
359 constexpr _If_is_unsigned_integer<_Tp>
360 bit_ceil(_Tp __x) noexcept
361 {
return std::__bit_ceil(__x); }
364 template<
typename _Tp>
365 constexpr _If_is_unsigned_integer<_Tp>
366 bit_floor(_Tp __x) noexcept
367 {
return std::__bit_floor(__x); }
370 template<
typename _Tp>
371 constexpr _If_is_unsigned_integer<_Tp>
372 bit_width(_Tp __x) noexcept
373 {
return std::__bit_width(__x); }
375 #define __cpp_lib_endian 201907L
380 little = __ORDER_LITTLE_ENDIAN__,
381 big = __ORDER_BIG_ENDIAN__,
382 native = __BYTE_ORDER__
388 _GLIBCXX_END_NAMESPACE_VERSION
ISO C++ entities toplevel namespace is std.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.