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_popcountg 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_popcountg. 11 12 #ifndef _LIBCPP___BIT_POPCOUNT_H 13 #define _LIBCPP___BIT_POPCOUNT_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 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __libcpp_popcount(unsigned __x) _NOEXCEPT { 30 return __builtin_popcount(__x); 31 } 32 33 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __libcpp_popcount(unsigned long __x) _NOEXCEPT { 34 return __builtin_popcountl(__x); 35 } 36 37 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { 38 return __builtin_popcountll(__x); 39 } 40 41 #if _LIBCPP_STD_VER >= 20 42 43 template <__libcpp_unsigned_integer _Tp> 44 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept { 45 # if __has_builtin(__builtin_popcountg) 46 return __builtin_popcountg(__t); 47 # else // __has_builtin(__builtin_popcountg) 48 if (sizeof(_Tp) <= sizeof(unsigned int)) 49 return std::__libcpp_popcount(static_cast<unsigned int>(__t)); 50 else if (sizeof(_Tp) <= sizeof(unsigned long)) 51 return std::__libcpp_popcount(static_cast<unsigned long>(__t)); 52 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 53 return std::__libcpp_popcount(static_cast<unsigned long long>(__t)); 54 else { 55 int __ret = 0; 56 while (__t != 0) { 57 __ret += std::__libcpp_popcount(static_cast<unsigned long long>(__t)); 58 __t >>= numeric_limits<unsigned long long>::digits; 59 } 60 return __ret; 61 } 62 # endif // __has_builtin(__builtin_popcountg) 63 } 64 65 #endif // _LIBCPP_STD_VER >= 20 66 67 _LIBCPP_END_NAMESPACE_STD 68 69 _LIBCPP_POP_MACROS 70 71 #endif // _LIBCPP___BIT_POPCOUNT_H 72