1// <bit> -*- C++ -*-
2
3// Copyright (C) 2018-2021 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file include/bit
26 * This is a Standard C++ Library header.
27 */
28
29#ifndef _GLIBCXX_BIT
30#define _GLIBCXX_BIT 1
31
32#pragma GCC system_header
33
34#if __cplusplus >= 201402L
35
36#include <type_traits>
37
38#if _GLIBCXX_HOSTED
39# include <ext/numeric_traits.h>
40#else
41# include <limits>
42/// @cond undocumented
43namespace __gnu_cxx
44{
45 template<typename _Tp>
46 struct __int_traits
47 {
48 static constexpr int __digits = std::numeric_limits<_Tp>::digits;
49 static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
50 };
51}
52/// @endcond
53#endif
54
55namespace std _GLIBCXX_VISIBILITY(default)
56{
57_GLIBCXX_BEGIN_NAMESPACE_VERSION
58
59 /**
60 * @defgroup bit_manip Bit manipulation
61 * @ingroup numerics
62 *
63 * Utilities for examining and manipulating individual bits.
64 *
65 * @{
66 */
67
68#if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
69#define __cpp_lib_bit_cast 201806L
70
71 /// Create a value of type `To` from the bits of `from`.
72 template<typename _To, typename _From>
73 [[nodiscard]]
74 constexpr _To
75 bit_cast(const _From& __from) noexcept
76 {
77 return __builtin_bit_cast(_To, __from);
78 }
79#endif
80
81 /// @cond undoc
82
83 template<typename _Tp>
84 constexpr _Tp
85 __rotl(_Tp __x, int __s) noexcept
86 {
87 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
88 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
89 {
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));
95 }
96 const int __r = __s % _Nd;
97 if (__r == 0)
98 return __x;
99 else if (__r > 0)
100 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
101 else
102 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
103 }
104
105 template<typename _Tp>
106 constexpr _Tp
107 __rotr(_Tp __x, int __s) noexcept
108 {
109 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
110 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
111 {
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));
117 }
118 const int __r = __s % _Nd;
119 if (__r == 0)
120 return __x;
121 else if (__r > 0)
122 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
123 else
124 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
125 }
126
127 template<typename _Tp>
128 constexpr int
129 __countl_zero(_Tp __x) noexcept
130 {
131 using __gnu_cxx::__int_traits;
132 constexpr auto _Nd = __int_traits<_Tp>::__digits;
133
134 if (__x == 0)
135 return _Nd;
136
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;
140
141 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
142 {
143 constexpr int __diff = _Nd_u - _Nd;
144 return __builtin_clz(__x) - __diff;
145 }
146 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
147 {
148 constexpr int __diff = _Nd_ul - _Nd;
149 return __builtin_clzl(__x) - __diff;
150 }
151 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
152 {
153 constexpr int __diff = _Nd_ull - _Nd;
154 return __builtin_clzll(__x) - __diff;
155 }
156 else // (_Nd > _Nd_ull)
157 {
158 static_assert(_Nd <= (2 * _Nd_ull),
159 "Maximum supported integer size is 128-bit");
160
161 unsigned long long __high = __x >> _Nd_ull;
162 if (__high != 0)
163 {
164 constexpr int __diff = (2 * _Nd_ull) - _Nd;
165 return __builtin_clzll(__high) - __diff;
166 }
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);
170 }
171 }
172
173 template<typename _Tp>
174 constexpr int
175 __countl_one(_Tp __x) noexcept
176 {
177 return std::__countl_zero<_Tp>((_Tp)~__x);
178 }
179
180 template<typename _Tp>
181 constexpr int
182 __countr_zero(_Tp __x) noexcept
183 {
184 using __gnu_cxx::__int_traits;
185 constexpr auto _Nd = __int_traits<_Tp>::__digits;
186
187 if (__x == 0)
188 return _Nd;
189
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;
193
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)
201 {
202 static_assert(_Nd <= (2 * _Nd_ull),
203 "Maximum supported integer size is 128-bit");
204
205 constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
206 unsigned long long __low = __x & __max_ull;
207 if (__low != 0)
208 return __builtin_ctzll(__low);
209 unsigned long long __high = __x >> _Nd_ull;
210 return __builtin_ctzll(__high) + _Nd_ull;
211 }
212 }
213
214 template<typename _Tp>
215 constexpr int
216 __countr_one(_Tp __x) noexcept
217 {
218 return std::__countr_zero((_Tp)~__x);
219 }
220
221 template<typename _Tp>
222 constexpr int
223 __popcount(_Tp __x) noexcept
224 {
225 using __gnu_cxx::__int_traits;
226 constexpr auto _Nd = __int_traits<_Tp>::__digits;
227
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;
231
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)
239 {
240 static_assert(_Nd <= (2 * _Nd_ull),
241 "Maximum supported integer size is 128-bit");
242
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);
247 }
248 }
249
250 template<typename _Tp>
251 constexpr bool
252 __has_single_bit(_Tp __x) noexcept
253 { return std::__popcount(__x) == 1; }
254
255 template<typename _Tp>
256 constexpr _Tp
257 __bit_ceil(_Tp __x) noexcept
258 {
259 using __gnu_cxx::__int_traits;
260 constexpr auto _Nd = __int_traits<_Tp>::__digits;
261 if (__x == 0 || __x == 1)
262 return 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())
270 {
271 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
272 }
273#endif
274 using __promoted_type = decltype(__x << 1);
275 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
276 {
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
281 // promoted type.
282 const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
283 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
284 }
285 return (_Tp)1u << __shift_exponent;
286 }
287
288 template<typename _Tp>
289 constexpr _Tp
290 __bit_floor(_Tp __x) noexcept
291 {
292 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
293 if (__x == 0)
294 return 0;
295 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
296 }
297
298 template<typename _Tp>
299 constexpr _Tp
300 __bit_width(_Tp __x) noexcept
301 {
302 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
303 return _Nd - std::__countl_zero(__x);
304 }
305
306 /// @endcond
307
308#if __cplusplus > 201703L
309
310#define __cpp_lib_bitops 201907L
311
312 /// @cond undoc
313 template<typename _Tp, typename _Up = _Tp>
314 using _If_is_unsigned_integer
315 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
316 /// @endcond
317
318 // [bit.rot], rotating
319
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); }
325
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); }
331
332 // [bit.count], counting
333
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); }
339
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); }
345
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); }
351
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); }
357
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); }
363
364 // [bit.pow.two], integral powers of 2
365
366#define __cpp_lib_int_pow2 202002L
367
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); }
373
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); }
379
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); }
385
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); }
391
392#define __cpp_lib_endian 201907L
393
394 /// Byte order
395 enum class endian
396 {
397 little = __ORDER_LITTLE_ENDIAN__,
398 big = __ORDER_BIG_ENDIAN__,
399 native = __BYTE_ORDER__
400 };
401#endif // C++2a
402
403 /// @}
404
405_GLIBCXX_END_NAMESPACE_VERSION
406} // namespace std
407
408#endif // C++14
409#endif // _GLIBCXX_BIT
410