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