c++ - 快速位集追加？

Question

我正在寻找具有快速位追加的位集实现，其中可以一次性高效地追加多个位。

例如

char value = 31;
char n_bits = 5;
fast_bitset bits;
bits.append(value, n_bits);

到目前为止，我已经尝试过 boost::dynamic_bitset 和 std::vector。两者都很慢。

---

旧帖

我正在使用 boost::dynamic_bitset 来打包一些数据。

通常我想一次打包 ~5 位，这会导致这样的调用:

char value = 31;
char n_bits = 5;
boost::dynamic_bitset<> bits;
for(char n = n_bits-1; n >= 0; --n)
    bits.push_back((value >> n) & 1);

然而，这在我看来效率很低，不能一次性添加所有位吗？

例如

char value = 31;
char n_bits = 5;
boost::dynamic_bitset<> bits;
bits.append(value, n_bits);

我希望它能做类似的事情:

template<typename T>
void append(T value, size_t n_bits)
{
     value <<= sizeof(T) - n_bits; // Make target bits most significant, remove all non-target bits.

     // TODO: Shift bits into proper place and use OR to add all target bits to bitset in one go
}

为什么dynamic_bitset没有这样的功能呢？能否高效实现？

Answer 1

使用 resize成员函数。

/* Append the lower-order nbits bits from value to set. */
template <typename T>
void append(boost::dynamic_bitset<> &set, T value, size_t nbits)
{
    set.resize(set.size() + nbits);
    for (size_t i=1; i<=nbits; i++) {
        set[set.size() - i] = value & 1;
        value >>= 1;
    }
}