c++ - 如何使用 boost::multiprecision 获取无符号未检查数的人口数？

Question

我正在使用 boost::multiprecision 来获得固定但任意精度的整数。 我打算使用 number<cpp_int<W, W, unsigned_magnitude, unchecked, void>> .第一个明显的问题是:

此数据类型是否具有给定精度的任何无符号整数的标准位模式？我听说有符号的扩展精度数不使用 2 的补码，但我认为无符号的应该使用标准表示，还是我遗漏了什么？

如果是这种情况，那么我可以得到整数的人口数吗？我似乎没有任何公共(public)界面可以做到这一点。我也很高兴有办法获得内部 内存，这样我就可以计算用作存储的单个单词的数量。

谢谢

Answer 1

在寻找同样的东西时偶然发现了这个。我最终写了以下内容:

#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;
}

对于原生字大小(即 <= 64 位)，这将编译为单个 popcnt。上面它编译为两个 popcnt 最多 128 位。除此之外，它会在 clang 中自动矢量化 - 大概是受 Faster Population Counts Using AVX2 Instructions 启发的东西但坦率地说，我没有进一步调查。在 gcc 中，它只是不展开循环，仍然使用 popcnt。

---

clang 演示:https://godbolt.org/z/fve195TeM
gcc 演示:https://godbolt.org/z/P4ndY8ccq