]>
Commit | Line | Data |
---|---|---|
f3e91052 JW |
1 | // <bit> -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2018-2019 Free Software Foundation, Inc. |
f3e91052 JW |
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 | template<typename _Tp> | |
44 | constexpr _Tp | |
45 | __rotl(_Tp __x, unsigned int __s) noexcept | |
46 | { | |
47 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
48 | const unsigned __sN = __s % _Nd; | |
4e4120a2 | 49 | return (__x << __sN) | (__x >> ((_Nd - __sN) % _Nd)); |
f3e91052 JW |
50 | } |
51 | ||
52 | template<typename _Tp> | |
53 | constexpr _Tp | |
54 | __rotr(_Tp __x, unsigned int __s) noexcept | |
55 | { | |
56 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
57 | const unsigned __sN = __s % _Nd; | |
4e4120a2 | 58 | return (__x >> __sN) | (__x << ((_Nd - __sN) % _Nd)); |
f3e91052 JW |
59 | } |
60 | ||
61 | template<typename _Tp> | |
62 | constexpr int | |
63 | __countl_zero(_Tp __x) noexcept | |
64 | { | |
337dc307 | 65 | constexpr auto _Nd = numeric_limits<_Tp>::digits; |
f3e91052 JW |
66 | |
67 | if (__x == 0) | |
337dc307 | 68 | return _Nd; |
f3e91052 | 69 | |
337dc307 JW |
70 | constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits; |
71 | constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits; | |
72 | constexpr auto _Nd_u = numeric_limits<unsigned>::digits; | |
f3e91052 | 73 | |
337dc307 | 74 | if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) |
f3e91052 | 75 | { |
337dc307 | 76 | constexpr int __diff = _Nd_u - _Nd; |
f3e91052 JW |
77 | return __builtin_clz(__x) - __diff; |
78 | } | |
337dc307 | 79 | else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) |
f3e91052 | 80 | { |
337dc307 | 81 | constexpr int __diff = _Nd_ul - _Nd; |
f3e91052 JW |
82 | return __builtin_clzl(__x) - __diff; |
83 | } | |
337dc307 | 84 | else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) |
f3e91052 | 85 | { |
337dc307 | 86 | constexpr int __diff = _Nd_ull - _Nd; |
f3e91052 JW |
87 | return __builtin_clzll(__x) - __diff; |
88 | } | |
337dc307 | 89 | else // (_Nd > _Nd_ull) |
f3e91052 | 90 | { |
337dc307 | 91 | static_assert(_Nd <= (2 * _Nd_ull), |
f3e91052 JW |
92 | "Maximum supported integer size is 128-bit"); |
93 | ||
337dc307 | 94 | unsigned long long __high = __x >> _Nd_ull; |
f3e91052 JW |
95 | if (__high != 0) |
96 | { | |
337dc307 | 97 | constexpr int __diff = (2 * _Nd_ull) - _Nd; |
f3e91052 JW |
98 | return __builtin_clzll(__high) - __diff; |
99 | } | |
337dc307 JW |
100 | constexpr auto __max_ull = numeric_limits<unsigned long long>::max(); |
101 | unsigned long long __low = __x & __max_ull; | |
102 | return (_Nd - _Nd_ull) + __builtin_clzll(__low); | |
f3e91052 JW |
103 | } |
104 | } | |
105 | ||
106 | template<typename _Tp> | |
107 | constexpr int | |
108 | __countl_one(_Tp __x) noexcept | |
109 | { | |
110 | if (__x == numeric_limits<_Tp>::max()) | |
111 | return numeric_limits<_Tp>::digits; | |
112 | return std::__countl_zero<_Tp>((_Tp)~__x); | |
113 | } | |
114 | ||
115 | template<typename _Tp> | |
116 | constexpr int | |
117 | __countr_zero(_Tp __x) noexcept | |
118 | { | |
337dc307 | 119 | constexpr auto _Nd = numeric_limits<_Tp>::digits; |
f3e91052 JW |
120 | |
121 | if (__x == 0) | |
337dc307 | 122 | return _Nd; |
f3e91052 | 123 | |
337dc307 JW |
124 | constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits; |
125 | constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits; | |
126 | constexpr auto _Nd_u = numeric_limits<unsigned>::digits; | |
f3e91052 | 127 | |
337dc307 | 128 | if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) |
f3e91052 | 129 | return __builtin_ctz(__x); |
337dc307 | 130 | else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) |
f3e91052 | 131 | return __builtin_ctzl(__x); |
337dc307 | 132 | else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) |
f3e91052 | 133 | return __builtin_ctzll(__x); |
337dc307 | 134 | else // (_Nd > _Nd_ull) |
f3e91052 | 135 | { |
337dc307 | 136 | static_assert(_Nd <= (2 * _Nd_ull), |
f3e91052 JW |
137 | "Maximum supported integer size is 128-bit"); |
138 | ||
337dc307 JW |
139 | constexpr auto __max_ull = numeric_limits<unsigned long long>::max(); |
140 | unsigned long long __low = __x & __max_ull; | |
f3e91052 JW |
141 | if (__low != 0) |
142 | return __builtin_ctzll(__low); | |
337dc307 JW |
143 | unsigned long long __high = __x >> _Nd_ull; |
144 | return __builtin_ctzll(__high) + _Nd_ull; | |
f3e91052 JW |
145 | } |
146 | } | |
147 | ||
148 | template<typename _Tp> | |
149 | constexpr int | |
150 | __countr_one(_Tp __x) noexcept | |
151 | { | |
152 | if (__x == numeric_limits<_Tp>::max()) | |
153 | return numeric_limits<_Tp>::digits; | |
154 | return std::__countr_zero((_Tp)~__x); | |
155 | } | |
156 | ||
157 | template<typename _Tp> | |
158 | constexpr int | |
159 | __popcount(_Tp __x) noexcept | |
160 | { | |
337dc307 | 161 | constexpr auto _Nd = numeric_limits<_Tp>::digits; |
f3e91052 JW |
162 | |
163 | if (__x == 0) | |
164 | return 0; | |
165 | ||
337dc307 JW |
166 | constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits; |
167 | constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits; | |
168 | constexpr auto _Nd_u = numeric_limits<unsigned>::digits; | |
f3e91052 | 169 | |
337dc307 | 170 | if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) |
f3e91052 | 171 | return __builtin_popcount(__x); |
337dc307 | 172 | else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) |
f3e91052 | 173 | return __builtin_popcountl(__x); |
337dc307 | 174 | else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) |
f3e91052 | 175 | return __builtin_popcountll(__x); |
337dc307 | 176 | else // (_Nd > _Nd_ull) |
f3e91052 | 177 | { |
337dc307 | 178 | static_assert(_Nd <= (2 * _Nd_ull), |
f3e91052 JW |
179 | "Maximum supported integer size is 128-bit"); |
180 | ||
337dc307 JW |
181 | constexpr auto __max_ull = numeric_limits<unsigned long long>::max(); |
182 | unsigned long long __low = __x & __max_ull; | |
183 | unsigned long long __high = __x >> _Nd_ull; | |
f3e91052 JW |
184 | return __builtin_popcountll(__low) + __builtin_popcountll(__high); |
185 | } | |
186 | } | |
187 | ||
188 | template<typename _Tp> | |
189 | constexpr bool | |
190 | __ispow2(_Tp __x) noexcept | |
191 | { return std::__popcount(__x) == 1; } | |
192 | ||
193 | template<typename _Tp> | |
194 | constexpr _Tp | |
195 | __ceil2(_Tp __x) noexcept | |
196 | { | |
197 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
2fb17d2d | 198 | if (__x == 0 || __x == 1) |
f3e91052 | 199 | return 1; |
2fb17d2d JW |
200 | const unsigned __n = _Nd - std::__countl_zero((_Tp)(__x - 1u)); |
201 | const _Tp __y_2 = (_Tp)1u << (__n - 1u); | |
202 | return __y_2 << 1u; | |
f3e91052 JW |
203 | } |
204 | ||
205 | template<typename _Tp> | |
206 | constexpr _Tp | |
207 | __floor2(_Tp __x) noexcept | |
208 | { | |
209 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
210 | if (__x == 0) | |
211 | return 0; | |
212 | return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1))); | |
213 | } | |
214 | ||
215 | template<typename _Tp> | |
216 | constexpr _Tp | |
217 | __log2p1(_Tp __x) noexcept | |
218 | { | |
219 | constexpr auto _Nd = numeric_limits<_Tp>::digits; | |
f3e91052 JW |
220 | return _Nd - std::__countl_zero(__x); |
221 | } | |
222 | ||
223 | #if __cplusplus > 201703L | |
224 | ||
f3e91052 JW |
225 | template<typename _Tp, typename _Up = _Tp> |
226 | using _If_is_unsigned_integer | |
47f79054 | 227 | = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>; |
f3e91052 JW |
228 | |
229 | #if ! __STRICT_ANSI__ | |
230 | // [bitops.rot], rotating | |
231 | ||
232 | template<typename _Tp> | |
233 | constexpr _If_is_unsigned_integer<_Tp> | |
234 | rotl(_Tp __x, unsigned int __s) noexcept | |
235 | { return std::__rotl(__x, __s); } | |
236 | ||
237 | template<typename _Tp> | |
238 | constexpr _If_is_unsigned_integer<_Tp> | |
239 | rotr(_Tp __x, unsigned int __s) noexcept | |
240 | { return std::__rotr(__x, __s); } | |
241 | ||
242 | // [bitops.count], counting | |
243 | ||
244 | template<typename _Tp> | |
245 | constexpr _If_is_unsigned_integer<_Tp, int> | |
246 | countl_zero(_Tp __x) noexcept | |
247 | { return std::__countl_zero(__x); } | |
248 | ||
249 | template<typename _Tp> | |
250 | constexpr _If_is_unsigned_integer<_Tp, int> | |
251 | countl_one(_Tp __x) noexcept | |
252 | { return std::__countl_one(__x); } | |
253 | ||
254 | template<typename _Tp> | |
255 | constexpr _If_is_unsigned_integer<_Tp, int> | |
256 | countr_zero(_Tp __x) noexcept | |
257 | { return std::__countr_zero(__x); } | |
258 | ||
259 | template<typename _Tp> | |
260 | constexpr _If_is_unsigned_integer<_Tp, int> | |
261 | countr_one(_Tp __x) noexcept | |
262 | { return std::__countr_one(__x); } | |
263 | ||
264 | template<typename _Tp> | |
265 | constexpr _If_is_unsigned_integer<_Tp, int> | |
266 | popcount(_Tp __x) noexcept | |
267 | { return std::__popcount(__x); } | |
268 | #endif | |
269 | ||
270 | // Integral power-of-two operations | |
271 | ||
272 | template<typename _Tp> | |
273 | constexpr _If_is_unsigned_integer<_Tp, bool> | |
274 | ispow2(_Tp __x) noexcept | |
275 | { return std::__ispow2(__x); } | |
276 | ||
277 | template<typename _Tp> | |
278 | constexpr _If_is_unsigned_integer<_Tp> | |
279 | ceil2(_Tp __x) noexcept | |
280 | { return std::__ceil2(__x); } | |
281 | ||
282 | template<typename _Tp> | |
283 | constexpr _If_is_unsigned_integer<_Tp> | |
284 | floor2(_Tp __x) noexcept | |
285 | { return std::__floor2(__x); } | |
286 | ||
287 | template<typename _Tp> | |
288 | constexpr _If_is_unsigned_integer<_Tp> | |
289 | log2p1(_Tp __x) noexcept | |
290 | { return std::__log2p1(__x); } | |
291 | ||
f3e91052 JW |
292 | #endif // C++2a |
293 | ||
294 | _GLIBCXX_END_NAMESPACE_VERSION | |
295 | } // namespace std | |
296 | ||
297 | #endif // C++14 | |
298 | #endif // _GLIBCXX_BIT |