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