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 #include <ext/numeric_traits.h>
38 
39 namespace std _GLIBCXX_VISIBILITY(default)
40 {
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42 
43  /**
44  * @defgroup bit_manip Bit manipulation
45  * @ingroup numerics
46  *
47  * Utilities for examining and manipulating individual bits.
48  *
49  * @{
50  */
51 
52 #if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
53 #define __cpp_lib_bit_cast 201806L
54 
55  /// Create a value of type `To` from the bits of `from`.
56  template<typename _To, typename _From>
57  constexpr _To
58  bit_cast(const _From& __from) noexcept
59  {
60  return __builtin_bit_cast(_To, __from);
61  }
62 #endif
63 
64  /// @cond undoc
65 
66  template<typename _Tp>
67  constexpr _Tp
68  __rotl(_Tp __x, int __s) noexcept
69  {
70  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
71  if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
72  {
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));
78  }
79  const int __r = __s % _Nd;
80  if (__r == 0)
81  return __x;
82  else if (__r > 0)
83  return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
84  else
85  return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
86  }
87 
88  template<typename _Tp>
89  constexpr _Tp
90  __rotr(_Tp __x, int __s) noexcept
91  {
92  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
93  if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
94  {
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));
100  }
101  const int __r = __s % _Nd;
102  if (__r == 0)
103  return __x;
104  else if (__r > 0)
105  return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
106  else
107  return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
108  }
109 
110  template<typename _Tp>
111  constexpr int
112  __countl_zero(_Tp __x) noexcept
113  {
114  using __gnu_cxx::__int_traits;
115  constexpr auto _Nd = __int_traits<_Tp>::__digits;
116 
117  if (__x == 0)
118  return _Nd;
119 
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;
123 
124  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
125  {
126  constexpr int __diff = _Nd_u - _Nd;
127  return __builtin_clz(__x) - __diff;
128  }
129  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
130  {
131  constexpr int __diff = _Nd_ul - _Nd;
132  return __builtin_clzl(__x) - __diff;
133  }
134  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
135  {
136  constexpr int __diff = _Nd_ull - _Nd;
137  return __builtin_clzll(__x) - __diff;
138  }
139  else // (_Nd > _Nd_ull)
140  {
141  static_assert(_Nd <= (2 * _Nd_ull),
142  "Maximum supported integer size is 128-bit");
143 
144  unsigned long long __high = __x >> _Nd_ull;
145  if (__high != 0)
146  {
147  constexpr int __diff = (2 * _Nd_ull) - _Nd;
148  return __builtin_clzll(__high) - __diff;
149  }
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);
153  }
154  }
155 
156  template<typename _Tp>
157  constexpr int
158  __countl_one(_Tp __x) noexcept
159  {
160  return std::__countl_zero<_Tp>((_Tp)~__x);
161  }
162 
163  template<typename _Tp>
164  constexpr int
165  __countr_zero(_Tp __x) noexcept
166  {
167  using __gnu_cxx::__int_traits;
168  constexpr auto _Nd = __int_traits<_Tp>::__digits;
169 
170  if (__x == 0)
171  return _Nd;
172 
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;
176 
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)
184  {
185  static_assert(_Nd <= (2 * _Nd_ull),
186  "Maximum supported integer size is 128-bit");
187 
188  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
189  unsigned long long __low = __x & __max_ull;
190  if (__low != 0)
191  return __builtin_ctzll(__low);
192  unsigned long long __high = __x >> _Nd_ull;
193  return __builtin_ctzll(__high) + _Nd_ull;
194  }
195  }
196 
197  template<typename _Tp>
198  constexpr int
199  __countr_one(_Tp __x) noexcept
200  {
201  return std::__countr_zero((_Tp)~__x);
202  }
203 
204  template<typename _Tp>
205  constexpr int
206  __popcount(_Tp __x) noexcept
207  {
208  using __gnu_cxx::__int_traits;
209  constexpr auto _Nd = __int_traits<_Tp>::__digits;
210 
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;
214 
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)
222  {
223  static_assert(_Nd <= (2 * _Nd_ull),
224  "Maximum supported integer size is 128-bit");
225 
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);
230  }
231  }
232 
233  template<typename _Tp>
234  constexpr bool
235  __has_single_bit(_Tp __x) noexcept
236  { return std::__popcount(__x) == 1; }
237 
238  template<typename _Tp>
239  constexpr _Tp
240  __bit_ceil(_Tp __x) noexcept
241  {
242  using __gnu_cxx::__int_traits;
243  constexpr auto _Nd = __int_traits<_Tp>::__digits;
244  if (__x == 0 || __x == 1)
245  return 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())
253  {
254  __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
255  }
256 #endif
257  using __promoted_type = decltype(__x << 1);
258  if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
259  {
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
264  // promoted type.
265  const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
266  __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
267  }
268  return (_Tp)1u << __shift_exponent;
269  }
270 
271  template<typename _Tp>
272  constexpr _Tp
273  __bit_floor(_Tp __x) noexcept
274  {
275  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
276  if (__x == 0)
277  return 0;
278  return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
279  }
280 
281  template<typename _Tp>
282  constexpr _Tp
283  __bit_width(_Tp __x) noexcept
284  {
285  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
286  return _Nd - std::__countl_zero(__x);
287  }
288 
289  /// @endcond
290 
291 #if __cplusplus > 201703L
292 
293 #define __cpp_lib_bitops 201907L
294 
295  /// @cond undoc
296  template<typename _Tp, typename _Up = _Tp>
297  using _If_is_unsigned_integer
298  = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
299  /// @endcond
300 
301  // [bit.rot], rotating
302 
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); }
308 
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); }
314 
315  // [bit.count], counting
316 
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); }
322 
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); }
328 
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); }
334 
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); }
340 
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); }
346 
347  // [bit.pow.two], integral powers of 2
348 
349 #define __cpp_lib_int_pow2 202002L
350 
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); }
356 
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); }
362 
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); }
368 
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); }
374 
375 #define __cpp_lib_endian 201907L
376 
377  /// Byte order
378  enum class endian
379  {
380  little = __ORDER_LITTLE_ENDIAN__,
381  big = __ORDER_BIG_ENDIAN__,
382  native = __BYTE_ORDER__
383  };
384 #endif // C++2a
385 
386  /// @}
387 
388 _GLIBCXX_END_NAMESPACE_VERSION
389 } // namespace std
390 
391 #endif // C++14
392 #endif // _GLIBCXX_BIT