用于搜索位阵列用于连续置位/清零位的快速代码？ [英] Fast code for searching bit-array for contiguous set/clear bits?

问题描述

有没有一些相当快的代码，可以帮助我快速搜索一个大的位图（几兆字节）连续零或一个位的运行？

Is there some reasonably fast code out there which can help me quickly search a large bitmap (a few megabytes) for runs of contiguous zero or one bits?

相当快我的意思是可以利用机器字大小并且一次比较整个字，而不是逐个比特分析，这是可怕的慢（例如一个用 vector < bool> ）。

By "reasonably fast" I mean something that can take advantage of the machine word size and compare entire words at once, instead of doing bit-by-bit analysis which is horrifically slow (such as one does with vector<bool>).

推荐答案

Windows具有 RTL_BITMAP 数据结构可以使用它的API。

Windows has an RTL_BITMAP data structure one can use along with its APIs.

但是我需要这个代码，因此我在这里写了（警告，这有点丑）：

https://gist.github.com/3206128

But I needed the code for this sometime ago, and so I wrote it here (warning, it's a little ugly):
https://gist.github.com/3206128

我已只部分测试它，因此它可能仍然有错误（特别是在 reverse ）。但是最近的一个版本（与这个版本略有不同）似乎对我有用，所以值得一试。

I have only partially tested it, so it might still have bugs (especially on reverse). But a recent version (only slightly different from this one) seemed to be usable for me, so it's worth a try.

整个事情的基本操作是到 - 快速 - 查找位运行的长度：

The fundamental operation for the entire thing is being able to -- quickly -- find the length of a run of bits:

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

鉴于其多功能性，一切都应该很容易构建。

Everything else should be easy to build upon this, given its versatility.

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

I tried to include some SSE code, but it didn't noticeably improve the performance. However, in general, the code is many times faster than doing bit-by-bit analysis, so I think it might be useful.

应该很容易测试if你可以得到一个向量< bool> 的缓冲区某种程度 - 如果你是Visual C ++，那么有一个函数，我包括它为你。如果你发现错误，请随时让我知道。

It should be easy to test if you can get a hold of vector<bool>'s buffer somehow -- and if you're on Visual C++, then there's a function I included which does that for you. If you find bugs, feel free to let me know.

这篇关于用于搜索位阵列用于连续置位/清零位的快速代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！