libstdc++
bit
Go to the documentation of this file.
1 // <bit> -*- C++ -*-
2 
3 // Copyright (C) 2018-2020 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  const int __r = __s % _Nd;
72  if (__r == 0)
73  return __x;
74  else if (__r > 0)
75  return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
76  else
77  return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
78  }
79 
80  template<typename _Tp>
81  constexpr _Tp
82  __rotr(_Tp __x, int __s) noexcept
83  {
84  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
85  const int __r = __s % _Nd;
86  if (__r == 0)
87  return __x;
88  else if (__r > 0)
89  return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
90  else
91  return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
92  }
93 
94  template<typename _Tp>
95  constexpr int
96  __countl_zero(_Tp __x) noexcept
97  {
98  using __gnu_cxx::__int_traits;
99  constexpr auto _Nd = __int_traits<_Tp>::__digits;
100 
101  if (__x == 0)
102  return _Nd;
103 
104  constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
105  constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
106  constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
107 
108  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
109  {
110  constexpr int __diff = _Nd_u - _Nd;
111  return __builtin_clz(__x) - __diff;
112  }
113  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
114  {
115  constexpr int __diff = _Nd_ul - _Nd;
116  return __builtin_clzl(__x) - __diff;
117  }
118  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
119  {
120  constexpr int __diff = _Nd_ull - _Nd;
121  return __builtin_clzll(__x) - __diff;
122  }
123  else // (_Nd > _Nd_ull)
124  {
125  static_assert(_Nd <= (2 * _Nd_ull),
126  "Maximum supported integer size is 128-bit");
127 
128  unsigned long long __high = __x >> _Nd_ull;
129  if (__high != 0)
130  {
131  constexpr int __diff = (2 * _Nd_ull) - _Nd;
132  return __builtin_clzll(__high) - __diff;
133  }
134  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
135  unsigned long long __low = __x & __max_ull;
136  return (_Nd - _Nd_ull) + __builtin_clzll(__low);
137  }
138  }
139 
140  template<typename _Tp>
141  constexpr int
142  __countl_one(_Tp __x) noexcept
143  {
144  if (__x == __gnu_cxx::__int_traits<_Tp>::__max)
145  return __gnu_cxx::__int_traits<_Tp>::__digits;
146  return std::__countl_zero<_Tp>((_Tp)~__x);
147  }
148 
149  template<typename _Tp>
150  constexpr int
151  __countr_zero(_Tp __x) noexcept
152  {
153  using __gnu_cxx::__int_traits;
154  constexpr auto _Nd = __int_traits<_Tp>::__digits;
155 
156  if (__x == 0)
157  return _Nd;
158 
159  constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
160  constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
161  constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
162 
163  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
164  return __builtin_ctz(__x);
165  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
166  return __builtin_ctzl(__x);
167  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
168  return __builtin_ctzll(__x);
169  else // (_Nd > _Nd_ull)
170  {
171  static_assert(_Nd <= (2 * _Nd_ull),
172  "Maximum supported integer size is 128-bit");
173 
174  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
175  unsigned long long __low = __x & __max_ull;
176  if (__low != 0)
177  return __builtin_ctzll(__low);
178  unsigned long long __high = __x >> _Nd_ull;
179  return __builtin_ctzll(__high) + _Nd_ull;
180  }
181  }
182 
183  template<typename _Tp>
184  constexpr int
185  __countr_one(_Tp __x) noexcept
186  {
187  if (__x == __gnu_cxx::__int_traits<_Tp>::__max)
188  return __gnu_cxx::__int_traits<_Tp>::__digits;
189  return std::__countr_zero((_Tp)~__x);
190  }
191 
192  template<typename _Tp>
193  constexpr int
194  __popcount(_Tp __x) noexcept
195  {
196  using __gnu_cxx::__int_traits;
197  constexpr auto _Nd = __int_traits<_Tp>::__digits;
198 
199  constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
200  constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
201  constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
202 
203  if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
204  return __builtin_popcount(__x);
205  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
206  return __builtin_popcountl(__x);
207  else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
208  return __builtin_popcountll(__x);
209  else // (_Nd > _Nd_ull)
210  {
211  static_assert(_Nd <= (2 * _Nd_ull),
212  "Maximum supported integer size is 128-bit");
213 
214  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
215  unsigned long long __low = __x & __max_ull;
216  unsigned long long __high = __x >> _Nd_ull;
217  return __builtin_popcountll(__low) + __builtin_popcountll(__high);
218  }
219  }
220 
221  template<typename _Tp>
222  constexpr bool
223  __has_single_bit(_Tp __x) noexcept
224  { return std::__popcount(__x) == 1; }
225 
226  template<typename _Tp>
227  constexpr _Tp
228  __bit_ceil(_Tp __x) noexcept
229  {
230  using __gnu_cxx::__int_traits;
231  constexpr auto _Nd = __int_traits<_Tp>::__digits;
232  if (__x == 0 || __x == 1)
233  return 1;
234  auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
235  // If the shift exponent equals _Nd then the correct result is not
236  // representable as a value of _Tp, and so the result is undefined.
237  // Want that undefined behaviour to be detected in constant expressions,
238  // by UBSan, and by debug assertions.
239 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
240  if (!__builtin_is_constant_evaluated())
241  {
242  __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
243  }
244 #endif
245  using __promoted_type = decltype(__x << 1);
246  if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
247  {
248  // If __x undergoes integral promotion then shifting by _Nd is
249  // not undefined. In order to make the shift undefined, so that
250  // it is diagnosed in constant expressions and by UBsan, we also
251  // need to "promote" the shift exponent to be too large for the
252  // promoted type.
253  const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
254  __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
255  }
256  return (_Tp)1u << __shift_exponent;
257  }
258 
259  template<typename _Tp>
260  constexpr _Tp
261  __bit_floor(_Tp __x) noexcept
262  {
263  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
264  if (__x == 0)
265  return 0;
266  return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
267  }
268 
269  template<typename _Tp>
270  constexpr _Tp
271  __bit_width(_Tp __x) noexcept
272  {
273  constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
274  return _Nd - std::__countl_zero(__x);
275  }
276 
277  /// @endcond
278 
279 #if __cplusplus > 201703L
280 
281 #define __cpp_lib_bitops 201907L
282 
283  /// @cond undoc
284  template<typename _Tp, typename _Up = _Tp>
285  using _If_is_unsigned_integer
286  = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
287  /// @endcond
288 
289  // [bit.rot], rotating
290 
291  /// Rotate `x` to the left by `s` bits.
292  template<typename _Tp>
293  [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
294  rotl(_Tp __x, int __s) noexcept
295  { return std::__rotl(__x, __s); }
296 
297  /// Rotate `x` to the right by `s` bits.
298  template<typename _Tp>
299  [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
300  rotr(_Tp __x, int __s) noexcept
301  { return std::__rotr(__x, __s); }
302 
303  // [bit.count], counting
304 
305  /// The number of contiguous zero bits, starting from the highest bit.
306  template<typename _Tp>
307  constexpr _If_is_unsigned_integer<_Tp, int>
308  countl_zero(_Tp __x) noexcept
309  { return std::__countl_zero(__x); }
310 
311  /// The number of contiguous one bits, starting from the highest bit.
312  template<typename _Tp>
313  constexpr _If_is_unsigned_integer<_Tp, int>
314  countl_one(_Tp __x) noexcept
315  { return std::__countl_one(__x); }
316 
317  /// The number of contiguous zero bits, starting from the lowest bit.
318  template<typename _Tp>
319  constexpr _If_is_unsigned_integer<_Tp, int>
320  countr_zero(_Tp __x) noexcept
321  { return std::__countr_zero(__x); }
322 
323  /// The number of contiguous one bits, starting from the lowest bit.
324  template<typename _Tp>
325  constexpr _If_is_unsigned_integer<_Tp, int>
326  countr_one(_Tp __x) noexcept
327  { return std::__countr_one(__x); }
328 
329  /// The number of bits set in `x`.
330  template<typename _Tp>
331  constexpr _If_is_unsigned_integer<_Tp, int>
332  popcount(_Tp __x) noexcept
333  { return std::__popcount(__x); }
334 
335  // [bit.pow.two], integral powers of 2
336 
337 #define __cpp_lib_int_pow2 202002L
338 
339  /// True if `x` is a power of two, false otherwise.
340  template<typename _Tp>
341  constexpr _If_is_unsigned_integer<_Tp, bool>
342  has_single_bit(_Tp __x) noexcept
343  { return std::__has_single_bit(__x); }
344 
345  /// The smallest power-of-two not less than `x`.
346  template<typename _Tp>
347  constexpr _If_is_unsigned_integer<_Tp>
348  bit_ceil(_Tp __x) noexcept
349  { return std::__bit_ceil(__x); }
350 
351  /// The largest power-of-two not greater than `x`.
352  template<typename _Tp>
353  constexpr _If_is_unsigned_integer<_Tp>
354  bit_floor(_Tp __x) noexcept
355  { return std::__bit_floor(__x); }
356 
357  /// The smallest integer greater than the base-2 logarithm of `x`.
358  template<typename _Tp>
359  constexpr _If_is_unsigned_integer<_Tp>
360  bit_width(_Tp __x) noexcept
361  { return std::__bit_width(__x); }
362 
363 #define __cpp_lib_endian 201907L
364 
365  /// Byte order
366  enum class endian
367  {
368  little = __ORDER_LITTLE_ENDIAN__,
369  big = __ORDER_BIG_ENDIAN__,
370  native = __BYTE_ORDER__
371  };
372 #endif // C++2a
373 
374  /// @}
375 
376 _GLIBCXX_END_NAMESPACE_VERSION
377 } // namespace std
378 
379 #endif // C++14
380 #endif // _GLIBCXX_BIT