3 // Copyright (C) 2018 Free Software Foundation, Inc.
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)
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.
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.
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/>.
26 * This is a Standard C++ Library header.
30 #define _GLIBCXX_BIT 1
32 #pragma GCC system_header
34 #if __cplusplus >= 201402L
36 #include <type_traits>
39 namespace std _GLIBCXX_VISIBILITY(default)
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
43 template<typename _Tp>
45 __rotl(_Tp __x, unsigned int __s) noexcept
47 constexpr auto _Nd = numeric_limits<_Tp>::digits;
48 const unsigned __sN = __s % _Nd;
49 return (__x << __sN) | (__x >> ((-__sN) % _Nd));
52 template<typename _Tp>
54 __rotr(_Tp __x, unsigned int __s) noexcept
56 constexpr auto _Nd = numeric_limits<_Tp>::digits;
57 const unsigned __sN = __s % _Nd;
58 return (__x >> __sN) | (__x << ((-__sN) % _Nd));
61 template<typename _Tp>
63 __countl_zero(_Tp __x) noexcept
65 using __limits = numeric_limits<_Tp>;
68 return __limits::digits;
70 using __limits_ull = numeric_limits<unsigned long long>;
71 using __limits_ul = numeric_limits<unsigned long>;
72 using __limits_u = numeric_limits<unsigned>;
74 if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits)
76 constexpr int __diff = __limits_u::digits - __limits::digits;
77 return __builtin_clz(__x) - __diff;
79 else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits)
81 constexpr int __diff = __limits_ul::digits - __limits::digits;
82 return __builtin_clzl(__x) - __diff;
84 else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits)
86 constexpr int __diff = __limits_ull::digits - __limits::digits;
87 return __builtin_clzll(__x) - __diff;
89 else // (__limits::digits > __limits_ull::digits)
91 static_assert(__limits::digits <= (2 * __limits_ull::digits),
92 "Maximum supported integer size is 128-bit");
94 unsigned long long __high = __x >> __limits_ull::digits;
98 = (2 * __limits_ull::digits) - __limits::digits;
99 return __builtin_clzll(__high) - __diff;
101 unsigned long long __low = __x & __limits_ull::max();
102 return (__limits::digits - __limits_ull::digits)
103 + __builtin_clzll(__low);
107 template<typename _Tp>
109 __countl_one(_Tp __x) noexcept
111 if (__x == numeric_limits<_Tp>::max())
112 return numeric_limits<_Tp>::digits;
113 return std::__countl_zero<_Tp>((_Tp)~__x);
116 template<typename _Tp>
118 __countr_zero(_Tp __x) noexcept
120 using __limits = numeric_limits<_Tp>;
123 return __limits::digits;
125 using __limits_ull = numeric_limits<unsigned long long>;
126 using __limits_ul = numeric_limits<unsigned long>;
127 using __limits_u = numeric_limits<unsigned>;
129 if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits)
130 return __builtin_ctz(__x);
131 else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits)
132 return __builtin_ctzl(__x);
133 else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits)
134 return __builtin_ctzll(__x);
135 else // (__limits::digits > __limits_ull::digits)
137 static_assert(__limits::digits <= (2 * __limits_ull::digits),
138 "Maximum supported integer size is 128-bit");
140 unsigned long long __low = __x & __limits_ull::max();
142 return __builtin_ctzll(__low);
143 unsigned long long __high = __x >> __limits_ull::digits;
144 return __builtin_ctzll(__high) + __limits_ull::digits;
148 template<typename _Tp>
150 __countr_one(_Tp __x) noexcept
152 if (__x == numeric_limits<_Tp>::max())
153 return numeric_limits<_Tp>::digits;
154 return std::__countr_zero((_Tp)~__x);
157 template<typename _Tp>
159 __popcount(_Tp __x) noexcept
161 using __limits = numeric_limits<_Tp>;
166 using __limits_ull = numeric_limits<unsigned long long>;
167 using __limits_ul = numeric_limits<unsigned long>;
168 using __limits_u = numeric_limits<unsigned>;
170 if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_u::digits)
171 return __builtin_popcount(__x);
172 else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ul::digits)
173 return __builtin_popcountl(__x);
174 else if _GLIBCXX17_CONSTEXPR (__limits::digits <= __limits_ull::digits)
175 return __builtin_popcountll(__x);
176 else // (__limits::digits > __limits_ull::digits)
178 static_assert(__limits::digits <= (2 * __limits_ull::digits),
179 "Maximum supported integer size is 128-bit");
181 unsigned long long __low = __x & __limits_ull::max();
182 unsigned long long __high = __x >> __limits_ull::digits;
183 return __builtin_popcountll(__low) + __builtin_popcountll(__high);
187 template<typename _Tp>
189 __ispow2(_Tp __x) noexcept
190 { return std::__popcount(__x) == 1; }
192 template<typename _Tp>
194 __ceil2(_Tp __x) noexcept
196 constexpr auto _Nd = numeric_limits<_Tp>::digits;
199 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x - 1u)));
202 template<typename _Tp>
204 __floor2(_Tp __x) noexcept
206 constexpr auto _Nd = numeric_limits<_Tp>::digits;
209 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
212 template<typename _Tp>
214 __log2p1(_Tp __x) noexcept
216 constexpr auto _Nd = numeric_limits<_Tp>::digits;
219 return _Nd - std::__countl_zero(__x);
222 #if __cplusplus > 201703L
224 template<typename _Tp, typename _Up, bool = is_integral_v<_Tp>>
225 struct _If_is_unsigned_integer_type { };
227 template<typename _Up>
228 struct _If_is_unsigned_integer_type<bool, _Up, true> { };
230 template<typename _Tp, typename _Up>
231 struct _If_is_unsigned_integer_type<_Tp, _Up, true>
232 : enable_if<is_same_v<_Tp, make_unsigned_t<_Tp>>, _Up> { };
234 template<typename _Tp, typename _Up = _Tp>
235 using _If_is_unsigned_integer
236 = typename _If_is_unsigned_integer_type<remove_cv_t<_Tp>, _Up>::type;
238 #if ! __STRICT_ANSI__
239 // [bitops.rot], rotating
241 template<typename _Tp>
242 constexpr _If_is_unsigned_integer<_Tp>
243 rotl(_Tp __x, unsigned int __s) noexcept
244 { return std::__rotl(__x, __s); }
246 template<typename _Tp>
247 constexpr _If_is_unsigned_integer<_Tp>
248 rotr(_Tp __x, unsigned int __s) noexcept
249 { return std::__rotr(__x, __s); }
251 // [bitops.count], counting
253 template<typename _Tp>
254 constexpr _If_is_unsigned_integer<_Tp, int>
255 countl_zero(_Tp __x) noexcept
256 { return std::__countl_zero(__x); }
258 template<typename _Tp>
259 constexpr _If_is_unsigned_integer<_Tp, int>
260 countl_one(_Tp __x) noexcept
261 { return std::__countl_one(__x); }
263 template<typename _Tp>
264 constexpr _If_is_unsigned_integer<_Tp, int>
265 countr_zero(_Tp __x) noexcept
266 { return std::__countr_zero(__x); }
268 template<typename _Tp>
269 constexpr _If_is_unsigned_integer<_Tp, int>
270 countr_one(_Tp __x) noexcept
271 { return std::__countr_one(__x); }
273 template<typename _Tp>
274 constexpr _If_is_unsigned_integer<_Tp, int>
275 popcount(_Tp __x) noexcept
276 { return std::__popcount(__x); }
279 // Integral power-of-two operations
281 template<typename _Tp>
282 constexpr _If_is_unsigned_integer<_Tp, bool>
283 ispow2(_Tp __x) noexcept
284 { return std::__ispow2(__x); }
286 template<typename _Tp>
287 constexpr _If_is_unsigned_integer<_Tp>
288 ceil2(_Tp __x) noexcept
289 { return std::__ceil2(__x); }
291 template<typename _Tp>
292 constexpr _If_is_unsigned_integer<_Tp>
293 floor2(_Tp __x) noexcept
294 { return std::__floor2(__x); }
296 template<typename _Tp>
297 constexpr _If_is_unsigned_integer<_Tp>
298 log2p1(_Tp __x) noexcept
299 { return std::__log2p1(__x); }
301 #if ! __STRICT_ANSI__
302 enum class byte : unsigned char;
305 rotl(byte __x, unsigned int __s) noexcept
306 { return (byte)std::__rotl((unsigned char)__x, __s); }
309 rotr(byte __x, unsigned int __s) noexcept
310 { return (byte)std::__rotr((unsigned char)__x, __s); }
313 countl_zero(byte __x) noexcept
314 { return std::__countl_zero((unsigned char)__x); }
317 countl_one(byte __x) noexcept
318 { return std::__countl_one((unsigned char)__x); }
321 countr_zero(byte __x) noexcept
322 { return std::__countr_zero((unsigned char)__x); }
325 countr_one(byte __x) noexcept
326 { return std::__countr_one((unsigned char)__x); }
329 popcount(byte __x) noexcept
330 { return std::__popcount((unsigned char)__x); }
333 ispow2(byte __x) noexcept
334 { return std::__ispow2((unsigned char)__x); }
337 ceil2(byte __x) noexcept
338 { return (byte)std::__ceil2((unsigned char)__x); }
341 floor2(byte __x) noexcept
342 { return (byte)std::__floor2((unsigned char)__x); }
345 log2p1(byte __x) noexcept
346 { return (byte)std::__log2p1((unsigned char)__x); }
351 _GLIBCXX_END_NAMESPACE_VERSION
355 #endif // _GLIBCXX_BIT