Boost population count on multiprecision ints

boost_popcnt.hpp

/*
Credits to the original author in the post from StackOverflow: https://stackoverflow.com/questions/24824681/how-do-i-get-the-population-count-of-an-unsigned-unchecked-number-with-boostmu
*/

#include <bitset>
#include <limits>
#include <type_traits>

#include <boost/multiprecision/cpp_int.hpp>

// N.B.: Prior to Boost 1.79 MinBits and MaxBits were unsigned,
//       not size_t - using auto to paper over this difference.
template <
    auto MinBits,
    auto MaxBits,
    boost::multiprecision::cpp_integer_type SignType,
    boost::multiprecision::cpp_int_check_type Checked,
    class Allocator>
size_t popcount(
        const boost::multiprecision::number<
            boost::multiprecision::cpp_int_backend<
                MinBits,
                MaxBits,
                SignType,
                Checked,
                Allocator>>& bits) {
    const auto& backend = bits.backend();

    // Using std::bitset::count to access a native popcnt.
    // In principle the limb type could be larger than what a
    // bitset can natively handle, in practice it likely isn't.
    using BitsetNativeType = unsigned long long;
    constexpr size_t kNativeBits = std::numeric_limits<BitsetNativeType>::digits;
    using LimbType = std::decay_t<decltype(*backend.limbs())>;
    constexpr size_t kLimbBits = std::numeric_limits<LimbType>::digits;

    constexpr size_t kNativesToCount = (kLimbBits + kNativeBits - 1) / kNativeBits;
    constexpr size_t kShiftPerNative = kNativesToCount > 1 ? kNativeBits : 0;
    static_assert(kNativesToCount > 0, "bad bit counts");

    size_t result = 0;
    for (size_t i = 0; i != backend.size(); ++i) {
        auto limb_value = backend.limbs()[i];
        for (size_t j = 0; j != kNativesToCount; ++j) {
            const std::bitset<kNativeBits> limb_bitset{BitsetNativeType(limb_value)};
            result += limb_bitset.count();
            limb_value >>= kShiftPerNative;            
        }
    }
    return result;
}

// Demo:

template <size_t Bits>
using uint_fixed = boost::multiprecision::number<
    boost::multiprecision::cpp_int_backend<
        Bits, Bits,
        boost::multiprecision::unsigned_magnitude,
        boost::multiprecision::unchecked,
        void
    >
>;

#define SHOW_POPCOUNT(n) \
        size_t popcount_ ## n(const uint_fixed<n>& bits) { \
            return popcount(bits); \
        }

SHOW_POPCOUNT(4)
SHOW_POPCOUNT(8)
SHOW_POPCOUNT(16)
SHOW_POPCOUNT(32)
SHOW_POPCOUNT(64)
SHOW_POPCOUNT(65)
SHOW_POPCOUNT(128)
SHOW_POPCOUNT(129)
SHOW_POPCOUNT(512)
SHOW_POPCOUNT(2048)