libstdc++
bit
Go to the documentation of this file.
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
43 namespace __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 
55 namespace 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  {
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  {
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  {
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  {
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
static constexpr _Tp max() noexcept
Definition: limits:321
Properties of fundamental types.
Definition: limits:312
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits&lt;integer-type&gt;.