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