c++ - 用于搜索连续设置/清除位的位数组的快速代码？

Question

是否有一些速度相当快的代码可以帮助我快速搜索大位图(几兆字节)以查找连续的零位或一位？

我所说的“相当快”是指可以利用机器字大小并一次比较整个单词的东西，而不是进行非常慢的逐位分析(例如使用 vector<bool> ) .

这对于例如在卷的位图中搜索可用空间(用于碎片整理等)。

Answer 1

Windows 有一个 RTL_BITMAP 可以与其 API 一起使用的数据结构。

但我前段时间需要这个代码，所以我把它写在这里(警告，它有点难看):
https://gist.github.com/3206128

我只是部分测试了它，所以它可能仍然有错误(尤其是在 reverse 上)。但是最近的一个版本(与这个版本略有不同)似乎对我有用，所以值得一试。

整个事情的基本操作是能够——快速——找到一段位的长度:

long long GetRunLength(
    const void *const pBitmap, unsigned long long nBitmapBits,
    long long startInclusive, long long endExclusive,
    const bool reverse, /*out*/ bool *pBit);

考虑到它的多功能性，其他一切都应该很容易在此基础上构建。

我尝试包含一些 SSE 代码，但它并没有显着提高性能。但是，一般来说，代码比逐位分析快很多倍，所以我认为它可能有用。

如果你能拿到vector<bool>应该很容易测试的缓冲区以某种方式——如果您使用的是 Visual C++，那么我包含的一个函数可以为您执行此操作。如果您发现错误，请随时告诉我。