1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // TODO: __builtin_ctzg is available since Clang 19 and GCC 14. When support for older versions is dropped, we can 10 // refactor this code to exclusively use __builtin_ctzg. 11 12 #ifndef _LIBCPP___BIT_COUNTR_H 13 #define _LIBCPP___BIT_COUNTR_H 14 15 #include <__bit/rotate.h> 16 #include <__concepts/arithmetic.h> 17 #include <__config> 18 #include <limits> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 # pragma GCC system_header 22 #endif 23 24 _LIBCPP_PUSH_MACROS 25 #include <__undef_macros> 26 27 _LIBCPP_BEGIN_NAMESPACE_STD 28 29 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __libcpp_ctz(unsigned __x) _NOEXCEPT { 30 return __builtin_ctz(__x); 31 } 32 33 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __libcpp_ctz(unsigned long __x) _NOEXCEPT { 34 return __builtin_ctzl(__x); 35 } 36 37 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { 38 return __builtin_ctzll(__x); 39 } 40 41 template <class _Tp> 42 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int __countr_zero(_Tp __t) _NOEXCEPT { 43 #if __has_builtin(__builtin_ctzg) 44 return __builtin_ctzg(__t, numeric_limits<_Tp>::digits); 45 #else // __has_builtin(__builtin_ctzg) 46 if (__t == 0) 47 return numeric_limits<_Tp>::digits; 48 if (sizeof(_Tp) <= sizeof(unsigned int)) 49 return std::__libcpp_ctz(static_cast<unsigned int>(__t)); 50 else if (sizeof(_Tp) <= sizeof(unsigned long)) 51 return std::__libcpp_ctz(static_cast<unsigned long>(__t)); 52 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 53 return std::__libcpp_ctz(static_cast<unsigned long long>(__t)); 54 else { 55 int __ret = 0; 56 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 57 while (static_cast<unsigned long long>(__t) == 0uLL) { 58 __ret += __ulldigits; 59 __t >>= __ulldigits; 60 } 61 return __ret + std::__libcpp_ctz(static_cast<unsigned long long>(__t)); 62 } 63 #endif // __has_builtin(__builtin_ctzg) 64 } 65 66 #if _LIBCPP_STD_VER >= 20 67 68 template <__libcpp_unsigned_integer _Tp> 69 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept { 70 return std::__countr_zero(__t); 71 } 72 73 template <__libcpp_unsigned_integer _Tp> 74 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept { 75 return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; 76 } 77 78 #endif // _LIBCPP_STD_VER >= 20 79 80 _LIBCPP_END_NAMESPACE_STD 81 82 _LIBCPP_POP_MACROS 83 84 #endif // _LIBCPP___BIT_COUNTR_H 85