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