用于搜索连续置位/清零位的位数组的快速代码？

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>'s 缓冲区应该很容易 - 如果您使用的是 Visual C++，那么我包含的一个函数可以为您完成此操作。如果您发现错误，请随时告诉我。