1

kth清除 a 中每一位的最快方法是什么boost::dynamic_bitset，可选择从 offset中清除j？

目前我正在这样做，这非常慢（伪代码）：

for (i = j; i < bitset.size(); i += k) {
    bitset[i] = 0;
}

数以百万计的位清除必须完成，所以这就是为什么我正在寻找一种快速的方法来做到这一点。

4

2 回答 2

1

好的，不确定这是否更快，但我认为您可以测试：

关键操作是掩码位集的构建，您应该有一个预先构建的掩码表（这将允许您将每个k位重置到每个第 32 位 [在我的平台上unsigned long是 32 位]）。然后昂贵的操作是构造一个与输入相同大小的完整掩码——如果它总是相同的大小，并且内存不是一个约束，你也可以简单地为此构造一个查找表，然后它只是简单地&将两者位集。

#include <iostream>
#include <limits>
#include <boost/dynamic_bitset.hpp>

using namespace std;

int main(void)
{
  boost::dynamic_bitset<> orig(64);
  for (int i = 0; i < orig.size(); ++i) {
    orig[i] = rand() % 2;
  }

  std::cout << orig << std::endl;

  unsigned long mask = 0x88888888; // reset every 4th bit
  boost::dynamic_bitset<> mbits(numeric_limits<unsigned long>::digits, mask);

  while(mbits.size() < orig.size())
    mbits.append(mask);
  mbits.resize(orig.size()); // incase not aligned
  mbits <<= 5; // arbitary starting point (i.e. j)
  std::cout << mbits << std::endl;

  mbits.flip();

  std::cout << mbits << std::endl;

  orig &= mbits;

  std::cout << orig << std::endl;

  return 0;
}

更新：好的，只是非常粗略地测试了它，你可以在这里看到结果：http ://www.ideone.com/ez3Oc ，使用预先构建的掩码，它可以快 +40%...

于 2011-04-13T14:40:23.523 回答
0

对于非常大的位集，按照 Nim 的建议计算一个 n 位长的掩码（其中 n 是您的本机大小，例如 x86_64 为 64），然后应用它。
如果您的原始长度不是 k 的倍数，请相应地移动它。
因此，如果您的本机长度为 10，并且只想设置 30 位长的位集的每个第 3 位，则需要 3 次这样的传递：
前 10 位：0010010010
第二个
10 位：0100100100 最后 10 位：1001001001
所以，在应用每个掩码后，您需要将其 (n%k) 位向左移动。

重复直到完成。

于 2011-04-13T15:36:40.403 回答