代码之家 › 专栏 › 技术社区 › Daniel Langr

如何高效地从比特集中提取单词?

bitset c++

4

Daniel Langr · 技术社区 · 6 月前

在两者中 libstdc++ 和 libc++ , std::bitset 内部基于(机器)单词数组。我想有效地将这些单词提取为整数。理想情况下,这种提取应该只从底层数组中读取所需的单词。我试图为这个提取编写一些代码,如下所示(它假设一个64位的单词 N

template <std::size_t IW, std::size_t N>
unsigned long extract_word(const std::bitset<N>& bs)
{
  static constexpr std::bitset<N> mask
    = std::numeric_limits<unsigned long>::max();

  auto res = bs >> IW * 64;
  res &= mask;

  return res.to_ulong();
}

问题是,在我的测试用例中,与读取单个数组元素相比,这会导致极其漫长和复杂的机器代码。现场演示: https://godbolt.org/z/rqhhcqKd9 .

我的问题是,是否有办法从中提取单词直接从底层数组中提取。

我想使用位集作为哈希表的键。虽然有一个专业 std::hash std::bitset ,它似乎没有得到很好的实施。在 libc++ libstdc++ ,该方法更复杂,但它对单个字节而不是单词进行操作。我更喜欢使用 boost::hash 例如,首先将单词提取到数组中。(例如, boost::dynamic_bitset 提供了一个名为 to_block_range

1 回复 | 直到 6 月前

1

3

abcdefg 6 月前

如果你想遵守 std::bitset operator[]

改进我自己的评论,MarekR建议定义 extract_word

template <std::size_t IW, std::size_t N>
constexpr unsigned long extract_word (std::bitset<N> const& bs)
{
  using limits = std::numeric_limits<unsigned long>;

  static_assert(N % limits::digits == 0);
  static_assert(IW < N / limits::digits);

  return [&bs] <std::size_t...Is> (std::index_sequence<Is...>) {
        return ( (std::size_t{bs[Is + IW * limits::digits]}<<Is) | ...);
    } (std::make_index_sequence<limits::digits>());
}

在这里,我们扩展了一个 std::index_sequence 然后使用折叠表达式来计算给定索引处的单词。以下 demo 似乎导致了一个相当简洁的汇编代码。