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