1 // -*- C++ -*- 2 //===------------------------------ bit ----------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===---------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP_BIT 11 #define _LIBCPP_BIT 12 13 /* 14 bit synopsis 15 16 namespace std { 17 18 // [bit.pow.two], integral powers of 2 19 template <class T> 20 constexpr bool has_single_bit(T x) noexcept; // C++20 21 template <class T> 22 constexpr T bit_ceil(T x); // C++20 23 template <class T> 24 constexpr T bit_floor(T x) noexcept; // C++20 25 template <class T> 26 constexpr T bit_width(T x) noexcept; // C++20 27 28 // [bit.rotate], rotating 29 template<class T> 30 constexpr T rotl(T x, unsigned int s) noexcept; // C++20 31 template<class T> 32 constexpr T rotr(T x, unsigned int s) noexcept; // C++20 33 34 // [bit.count], counting 35 template<class T> 36 constexpr int countl_zero(T x) noexcept; // C++20 37 template<class T> 38 constexpr int countl_one(T x) noexcept; // C++20 39 template<class T> 40 constexpr int countr_zero(T x) noexcept; // C++20 41 template<class T> 42 constexpr int countr_one(T x) noexcept; // C++20 43 template<class T> 44 constexpr int popcount(T x) noexcept; // C++20 45 46 // [bit.endian], endian 47 enum class endian { 48 little = see below, // C++20 49 big = see below, // C++20 50 native = see below // C++20 51 }; 52 53 } // namespace std 54 55 */ 56 57 #include <__config> 58 #include <__bits> 59 #include <__debug> 60 #include <limits> 61 #include <type_traits> 62 #include <version> 63 64 #if defined(__IBMCPP__) 65 #include "__support/ibm/support.h" 66 #endif 67 #if defined(_LIBCPP_COMPILER_MSVC) 68 #include <intrin.h> 69 #endif 70 71 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 72 #pragma GCC system_header 73 #endif 74 75 _LIBCPP_PUSH_MACROS 76 #include <__undef_macros> 77 78 _LIBCPP_BEGIN_NAMESPACE_STD 79 80 template<class _Tp> 81 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 82 _Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT 83 { 84 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotl requires an unsigned integer type"); 85 const unsigned int __dig = numeric_limits<_Tp>::digits; 86 if ((__cnt % __dig) == 0) 87 return __t; 88 return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); 89 } 90 91 template<class _Tp> 92 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 93 _Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT 94 { 95 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type"); 96 const unsigned int __dig = numeric_limits<_Tp>::digits; 97 if ((__cnt % __dig) == 0) 98 return __t; 99 return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); 100 } 101 102 template<class _Tp> 103 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 104 int __countr_zero(_Tp __t) _NOEXCEPT 105 { 106 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_zero requires an unsigned integer type"); 107 if (__t == 0) 108 return numeric_limits<_Tp>::digits; 109 110 if (sizeof(_Tp) <= sizeof(unsigned int)) 111 return __libcpp_ctz(static_cast<unsigned int>(__t)); 112 else if (sizeof(_Tp) <= sizeof(unsigned long)) 113 return __libcpp_ctz(static_cast<unsigned long>(__t)); 114 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 115 return __libcpp_ctz(static_cast<unsigned long long>(__t)); 116 else 117 { 118 int __ret = 0; 119 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 120 while (static_cast<unsigned long long>(__t) == 0uLL) 121 { 122 __ret += __ulldigits; 123 __t >>= __ulldigits; 124 } 125 return __ret + __libcpp_ctz(static_cast<unsigned long long>(__t)); 126 } 127 } 128 129 template<class _Tp> 130 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 131 int __countl_zero(_Tp __t) _NOEXCEPT 132 { 133 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); 134 if (__t == 0) 135 return numeric_limits<_Tp>::digits; 136 137 if (sizeof(_Tp) <= sizeof(unsigned int)) 138 return __libcpp_clz(static_cast<unsigned int>(__t)) 139 - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits); 140 else if (sizeof(_Tp) <= sizeof(unsigned long)) 141 return __libcpp_clz(static_cast<unsigned long>(__t)) 142 - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits); 143 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 144 return __libcpp_clz(static_cast<unsigned long long>(__t)) 145 - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits); 146 else 147 { 148 int __ret = 0; 149 int __iter = 0; 150 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 151 while (true) { 152 __t = __rotr(__t, __ulldigits); 153 if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits) 154 break; 155 __ret += __iter; 156 } 157 return __ret + __iter; 158 } 159 } 160 161 template<class _Tp> 162 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 163 int __countl_one(_Tp __t) _NOEXCEPT 164 { 165 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_one requires an unsigned integer type"); 166 return __t != numeric_limits<_Tp>::max() 167 ? __countl_zero(static_cast<_Tp>(~__t)) 168 : numeric_limits<_Tp>::digits; 169 } 170 171 template<class _Tp> 172 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 173 int __countr_one(_Tp __t) _NOEXCEPT 174 { 175 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_one requires an unsigned integer type"); 176 return __t != numeric_limits<_Tp>::max() 177 ? __countr_zero(static_cast<_Tp>(~__t)) 178 : numeric_limits<_Tp>::digits; 179 } 180 181 template<class _Tp> 182 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 183 int __popcount(_Tp __t) _NOEXCEPT 184 { 185 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__popcount requires an unsigned integer type"); 186 if (sizeof(_Tp) <= sizeof(unsigned int)) 187 return __libcpp_popcount(static_cast<unsigned int>(__t)); 188 else if (sizeof(_Tp) <= sizeof(unsigned long)) 189 return __libcpp_popcount(static_cast<unsigned long>(__t)); 190 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 191 return __libcpp_popcount(static_cast<unsigned long long>(__t)); 192 else 193 { 194 int __ret = 0; 195 while (__t != 0) 196 { 197 __ret += __libcpp_popcount(static_cast<unsigned long long>(__t)); 198 __t >>= numeric_limits<unsigned long long>::digits; 199 } 200 return __ret; 201 } 202 } 203 204 // integral log base 2 205 template<class _Tp> 206 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 207 unsigned __bit_log2(_Tp __t) _NOEXCEPT 208 { 209 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__bit_log2 requires an unsigned integer type"); 210 return numeric_limits<_Tp>::digits - 1 - __countl_zero(__t); 211 } 212 213 template <class _Tp> 214 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR 215 bool __has_single_bit(_Tp __t) _NOEXCEPT 216 { 217 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__has_single_bit requires an unsigned integer type"); 218 return __t != 0 && (((__t & (__t - 1)) == 0)); 219 } 220 221 #if _LIBCPP_STD_VER > 17 222 223 template<class _Tp> 224 _LIBCPP_INLINE_VISIBILITY constexpr 225 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp> 226 rotl(_Tp __t, unsigned int __cnt) noexcept 227 { 228 return __rotl(__t, __cnt); 229 } 230 231 template<class _Tp> 232 _LIBCPP_INLINE_VISIBILITY constexpr 233 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp> 234 rotr(_Tp __t, unsigned int __cnt) noexcept 235 { 236 return __rotr(__t, __cnt); 237 } 238 239 template<class _Tp> 240 _LIBCPP_INLINE_VISIBILITY constexpr 241 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int> 242 countl_zero(_Tp __t) noexcept 243 { 244 return __countl_zero(__t); 245 } 246 247 template<class _Tp> 248 _LIBCPP_INLINE_VISIBILITY constexpr 249 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int> 250 countl_one(_Tp __t) noexcept 251 { 252 return __countl_one(__t); 253 } 254 255 template<class _Tp> 256 _LIBCPP_INLINE_VISIBILITY constexpr 257 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int> 258 countr_zero(_Tp __t) noexcept 259 { 260 return __countr_zero(__t); 261 } 262 263 template<class _Tp> 264 _LIBCPP_INLINE_VISIBILITY constexpr 265 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int> 266 countr_one(_Tp __t) noexcept 267 { 268 return __countr_one(__t); 269 } 270 271 template<class _Tp> 272 _LIBCPP_INLINE_VISIBILITY constexpr 273 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, int> 274 popcount(_Tp __t) noexcept 275 { 276 return __popcount(__t); 277 } 278 279 template <class _Tp> 280 _LIBCPP_INLINE_VISIBILITY constexpr 281 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, bool> 282 has_single_bit(_Tp __t) noexcept 283 { 284 return __has_single_bit(__t); 285 } 286 287 template <class _Tp> 288 _LIBCPP_INLINE_VISIBILITY constexpr 289 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp> 290 bit_floor(_Tp __t) noexcept 291 { 292 return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t); 293 } 294 295 template <class _Tp> 296 _LIBCPP_INLINE_VISIBILITY constexpr 297 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp> 298 bit_ceil(_Tp __t) noexcept 299 { 300 if (__t < 2) return 1; 301 const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u)); 302 _LIBCPP_DEBUG_ASSERT(__libcpp_is_constant_evaluated() || __n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil"); 303 304 if constexpr (sizeof(_Tp) >= sizeof(unsigned)) 305 return _Tp{1} << __n; 306 else 307 { 308 const unsigned __extra = numeric_limits<unsigned>::digits - numeric_limits<_Tp>::digits; 309 const unsigned __retVal = 1u << (__n + __extra); 310 return (_Tp) (__retVal >> __extra); 311 } 312 } 313 314 template <class _Tp> 315 _LIBCPP_INLINE_VISIBILITY constexpr 316 _EnableIf<__libcpp_is_unsigned_integer<_Tp>::value, _Tp> 317 bit_width(_Tp __t) noexcept 318 { 319 return __t == 0 ? 0 : __bit_log2(__t) + 1; 320 } 321 322 enum class endian 323 { 324 little = 0xDEAD, 325 big = 0xFACE, 326 #if defined(_LIBCPP_LITTLE_ENDIAN) 327 native = little 328 #elif defined(_LIBCPP_BIG_ENDIAN) 329 native = big 330 #else 331 native = 0xCAFE 332 #endif 333 }; 334 335 #endif // _LIBCPP_STD_VER > 17 336 337 _LIBCPP_END_NAMESPACE_STD 338 339 _LIBCPP_POP_MACROS 340 341 #endif // _LIBCPP_BIT 342
Indexes created Thu Oct 22 00:27:13 UTC 2026