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