3 // Copyright (C) 2018-2021 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
26 * This is a Standard C++ Library header.
30 #define _GLIBCXX_BIT 1
32 #pragma GCC system_header
34 #if __cplusplus >= 201402L
36 #include <type_traits>
39 # include <ext/numeric_traits.h>
42 /// @cond undocumented
45 template<typename _Tp>
48 static constexpr int __digits = std::numeric_limits<_Tp>::digits;
49 static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
55 namespace std _GLIBCXX_VISIBILITY(default)
57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
60 * @defgroup bit_manip Bit manipulation
63 * Utilities for examining and manipulating individual bits.
68 #if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
69 #define __cpp_lib_bit_cast 201806L
71 /// Create a value of type `To` from the bits of `from`.
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
87 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
88 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
90 // Variant for power of two _Nd which the compiler can
91 // easily pattern match.
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)); // rotr(x, -r)
105 template<typename _Tp>
107 __rotr(_Tp __x, int __s) noexcept
109 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
110 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
112 // Variant for power of two _Nd which the compiler can
113 // easily pattern match.
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)); // rotl(x, -r)
127 template<typename _Tp>
129 __countl_zero(_Tp __x) noexcept
131 using __gnu_cxx::__int_traits;
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;
156 else // (_Nd > _Nd_ull)
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
184 using __gnu_cxx::__int_traits;
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);
200 else // (_Nd > _Nd_ull)
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
225 using __gnu_cxx::__int_traits;
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);
238 else // (_Nd > _Nd_ull)
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
259 using __gnu_cxx::__int_traits;
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));
264 // If the shift exponent equals _Nd then the correct result is not
265 // representable as a value of _Tp, and so the result is undefined.
266 // Want that undefined behaviour to be detected in constant expressions,
267 // by UBSan, and by debug assertions.
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)
277 // If __x undergoes integral promotion then shifting by _Nd is
278 // not undefined. In order to make the shift undefined, so that
279 // it is diagnosed in constant expressions and by UBsan, we also
280 // need to "promote" the shift exponent to be too large for the
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
292 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
295 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
298 template<typename _Tp>
300 __bit_width(_Tp __x) noexcept
302 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
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>;
318 // [bit.rot], rotating
320 /// Rotate `x` to the left by `s` bits.
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); }
326 /// Rotate `x` to the right by `s` bits.
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); }
332 // [bit.count], counting
334 /// The number of contiguous zero bits, starting from the highest bit.
335 template<typename _Tp>
336 constexpr _If_is_unsigned_integer<_Tp, int>
337 countl_zero(_Tp __x) noexcept
338 { return std::__countl_zero(__x); }
340 /// The number of contiguous one bits, starting from the highest bit.
341 template<typename _Tp>
342 constexpr _If_is_unsigned_integer<_Tp, int>
343 countl_one(_Tp __x) noexcept
344 { return std::__countl_one(__x); }
346 /// The number of contiguous zero bits, starting from the lowest bit.
347 template<typename _Tp>
348 constexpr _If_is_unsigned_integer<_Tp, int>
349 countr_zero(_Tp __x) noexcept
350 { return std::__countr_zero(__x); }
352 /// The number of contiguous one bits, starting from the lowest bit.
353 template<typename _Tp>
354 constexpr _If_is_unsigned_integer<_Tp, int>
355 countr_one(_Tp __x) noexcept
356 { return std::__countr_one(__x); }
358 /// The number of bits set in `x`.
359 template<typename _Tp>
360 constexpr _If_is_unsigned_integer<_Tp, int>
361 popcount(_Tp __x) noexcept
362 { return std::__popcount(__x); }
364 // [bit.pow.two], integral powers of 2
366 #define __cpp_lib_int_pow2 202002L
368 /// True if `x` is a power of two, false otherwise.
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); }
374 /// The smallest power-of-two not less than `x`.
375 template<typename _Tp>
376 constexpr _If_is_unsigned_integer<_Tp>
377 bit_ceil(_Tp __x) noexcept
378 { return std::__bit_ceil(__x); }
380 /// The largest power-of-two not greater than `x`.
381 template<typename _Tp>
382 constexpr _If_is_unsigned_integer<_Tp>
383 bit_floor(_Tp __x) noexcept
384 { return std::__bit_floor(__x); }
386 /// The smallest integer greater than the base-2 logarithm of `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