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>
37 #include <ext/numeric_traits.h>
39 namespace std _GLIBCXX_VISIBILITY(default)
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 * @defgroup bit_manip Bit manipulation
47 * Utilities for examining and manipulating individual bits.
52 #if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
53 #define __cpp_lib_bit_cast 201806L
55 /// Create a value of type `To` from the bits of `from`.
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
70 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
71 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
73 // Variant for power of two _Nd which the compiler can
74 // easily pattern match.
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)); // rotr(x, -r)
88 template<typename _Tp>
90 __rotr(_Tp __x, int __s) noexcept
92 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
93 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
95 // Variant for power of two _Nd which the compiler can
96 // easily pattern match.
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)); // rotl(x, -r)
110 template<typename _Tp>
112 __countl_zero(_Tp __x) noexcept
114 using __gnu_cxx::__int_traits;
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;
139 else // (_Nd > _Nd_ull)
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
167 using __gnu_cxx::__int_traits;
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);
183 else // (_Nd > _Nd_ull)
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
208 using __gnu_cxx::__int_traits;
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);
221 else // (_Nd > _Nd_ull)
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
242 using __gnu_cxx::__int_traits;
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));
247 // If the shift exponent equals _Nd then the correct result is not
248 // representable as a value of _Tp, and so the result is undefined.
249 // Want that undefined behaviour to be detected in constant expressions,
250 // by UBSan, and by debug assertions.
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)
260 // If __x undergoes integral promotion then shifting by _Nd is
261 // not undefined. In order to make the shift undefined, so that
262 // it is diagnosed in constant expressions and by UBsan, we also
263 // need to "promote" the shift exponent to be too large for the
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
275 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
278 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
281 template<typename _Tp>
283 __bit_width(_Tp __x) noexcept
285 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
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>;
301 // [bit.rot], rotating
303 /// Rotate `x` to the left by `s` bits.
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); }
309 /// Rotate `x` to the right by `s` bits.
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); }
315 // [bit.count], counting
317 /// The number of contiguous zero bits, starting from the highest bit.
318 template<typename _Tp>
319 constexpr _If_is_unsigned_integer<_Tp, int>
320 countl_zero(_Tp __x) noexcept
321 { return std::__countl_zero(__x); }
323 /// The number of contiguous one bits, starting from the highest bit.
324 template<typename _Tp>
325 constexpr _If_is_unsigned_integer<_Tp, int>
326 countl_one(_Tp __x) noexcept
327 { return std::__countl_one(__x); }
329 /// The number of contiguous zero bits, starting from the lowest bit.
330 template<typename _Tp>
331 constexpr _If_is_unsigned_integer<_Tp, int>
332 countr_zero(_Tp __x) noexcept
333 { return std::__countr_zero(__x); }
335 /// The number of contiguous one bits, starting from the lowest bit.
336 template<typename _Tp>
337 constexpr _If_is_unsigned_integer<_Tp, int>
338 countr_one(_Tp __x) noexcept
339 { return std::__countr_one(__x); }
341 /// The number of bits set in `x`.
342 template<typename _Tp>
343 constexpr _If_is_unsigned_integer<_Tp, int>
344 popcount(_Tp __x) noexcept
345 { return std::__popcount(__x); }
347 // [bit.pow.two], integral powers of 2
349 #define __cpp_lib_int_pow2 202002L
351 /// True if `x` is a power of two, false otherwise.
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); }
357 /// The smallest power-of-two not less than `x`.
358 template<typename _Tp>
359 constexpr _If_is_unsigned_integer<_Tp>
360 bit_ceil(_Tp __x) noexcept
361 { return std::__bit_ceil(__x); }
363 /// The largest power-of-two not greater than `x`.
364 template<typename _Tp>
365 constexpr _If_is_unsigned_integer<_Tp>
366 bit_floor(_Tp __x) noexcept
367 { return std::__bit_floor(__x); }
369 /// The smallest integer greater than the base-2 logarithm of `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
392 #endif // _GLIBCXX_BIT