从boost dynamic_bitset提取子集 [英] Extract subset from boost dynamic_bitset

问题描述

我需要从给定的boost_dynamic_bitset中提取并解码位(idx，idx + 1，... idx + n_bits). 我创建了以下解决方案:

I need to extract and decode the bits (idx, idx+1, ... idx+n_bits) from a given boost dynamic_bitset. I have created the following solution:

boost::dynamic_bitset<> mybitset(...);
// build mask 2^{idx+n_bits} - 2^{idx}
const boost::dynamic_bitset<> mask(mybitset.size(), (1 << idx+n_bits) - (1 << idx));
// shift the masked result idx times and get long
unsigned long u = ((mybitset & mask) >> idx ).to_ulong();

它可以很好地工作，但是由于此代码对于我的应用程序的性能至关重要，因此我很好奇是否存在更好的方法来实现这一目标吗?

It works well, but as this code is critical for the performance of my application, I am curious if there exists a better way to achieve this?

推荐答案

解决方案很简单:

#include <tuple>
    using std::get;
    using std::tuple;
    using std::make_tuple;
#include <boost/dynamic_bitset.hpp>
    using boost::dynamic_bitset;

template <typename Block, typename Allocator>
unsigned block_index(const boost::dynamic_bitset<Block, Allocator>& b, unsigned pos)
{ return pos / b.bits_per_block; }

namespace boost {
template <>
inline void
to_block_range(const dynamic_bitset<>& b, tuple<unsigned, unsigned,  unsigned long&> param)
{

    {
        unsigned beg = get<0>(param);
        unsigned len = get<1>(param);
        unsigned block1 = block_index(b, beg);
        unsigned block2 = block_index(b, beg + len -1);
        unsigned bit_index = beg % b.bits_per_block;
        unsigned long bitmask = (1 << len) - 1;
        get<2>(param) = ((b.m_bits[block1] >> bit_index) |
                               (b.m_bits[block2] << (b.bits_per_block - bit_index)  )) &
                                bitmask;
        return;
    }
}
}


unsigned long res;
to_block_range(bits, make_tuple(pos, len, std::ref(res)));

致电:

boost::dynamic_bitset<> bits;
unsigned long result;
to_block_range(bits, t_extract_range{begin_bit, length_bits, result});

dynamic_bitset中没有直接的本机支持.

There is no direct, native support in dynamic_bitset.

要获得一定范围的位，您必须进入dynamic_bitset内部，可以访问基础存储，然后自己提取位.

To get a range of bits, you have to get inside dynamic_bitset, get access to the underlying storage, and extract the bits yourself.

执行此操作的代码很简单，但是数据(dynamic_bitset::m_bits)位于类的私有部分内.有三种方法可以破解私密墙:

The code to do this is trivial but the data (dynamic_bitset::m_bits) is inside the private part of the class. There are three ways to hack past the private wall:

1. 假装您的编译器不合格.
   #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS.通过更改BOOST_DYNAMIC_BITSET_PRIVATE，将private更改为public.
2. 使用dynamic_bitset.hpp标头公开m_bits.
3. 第三个解决方案是解决当前代码.

1. Pretend your compiler is non-conforming.
   #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. This changes private to public by changing BOOST_DYNAMIC_BITSET_PRIVATE.
2. Hacking the dynamic_bitset.hpp header to expose m_bits.
3. The third solution is to work around the current code.

(1)和(2)是易碎的正面攻击，这将是维护的噩梦.

(1) and (2) are brittle, frontal assaults which will be a maintenance nightmare.

幸运的是，对于(3)，有一些模板函数是dynamic_bitset的friend个.我们可以通过接管(专门化)此模板来替代我们自己的功能来进行自己的提取.

Luckily for (3), there are template functions which are friends of dynamic_bitset. We can substitute our own function to do our own extraction by taking over (specialising) this template.

template <typename Block, typename Allocator, typename BlockOutputIterator>
inline void
to_block_range(const dynamic_bitset<Block, Allocator>& b,
               BlockOutputIterator result)
{
    std::copy(b.m_bits.begin(), b.m_bits.end(), result);
}

规范模板功能将整个位集复制到迭代器BlockOutputIterator中，这不是我们想要的.

The canonical template function copies the entire bitset to iterator BlockOutputIterator which is not what we want.

我们将使用单个自定义类型代替BlockOutputIterator来专门化boost::to_block_range，该类型将容纳所有3个I/O参数:即

We are going to specialise boost::to_block_range using a single custom type in place of BlockOutputIterator which will hold all 3 i/o parameters: namely

• begin_bit，
• length_of_range和
• 目的地.

• begin_bit,
• length_of_range and
• destination.

假设您使用必需的类型调用to_block_range，它将调用您自己的函数而不是标准模板，但也具有对内部函数的完全访问权限.您实质上已经颠覆了c ++访问规范系统！

Providing you call to_block_range with the requisite type, it will call your own function instead of the standard template, but with full access to the internals as well. You have essentially subverted the c++ access specification system!

该示例代码不进行错误检查.没有尝试确保

N.B. The example code does no error checking. No attempt to make sure

• 该范围适合无符号长或
• 该范围不超过位集或
的范围
• 该位集在内部使用无符号长数.

这篇关于从boost dynamic_bitset提取子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！