用于搜索连续置位/清除位的位数组的快速代码？
有没有一些相当快的代码可以帮助我快速搜索大的位图（几兆字节）运行连续的零或一位？
通过“合理快速”，我的意思是可以利用机器字大小并一次比较整个单词，而不是进行逐点分析，这种分析非常慢（例如使用vector ）。
它对于例如在卷的位图中搜索可用空间（用于碎片整理等）非常有用。
Windows具有可与其API一起使用的RTL_BITMAP数据结构。
但是我之前需要这个代码，所以我在这里写了它（警告，它有点难看）：
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);
鉴于其多function性，其他所有内容都应该易于构建。
我试图包含一些SSE代码，但它没有显着提高性能。 但是，一般来说，代码比逐位分析快很多倍，所以我认为它可能很有用。
如果你能以某种方式获得vector的缓冲区应该很容易测试 – 如果你使用的是Visual C ++，那么我所包含的函数就是为你做的。 如果您发现错误，请随时告诉我。
我无法想象如何直接在记忆单词上做得好，所以我已经编写了一个快速解决方案，它正在处理字节; 为方便起见，让我们勾勒计算连续计算的算法：
构造两个256大小的表，您将为0到255之间的每个数字写入，在开头和结尾处的尾随1的数字。 例如，对于数字167（二进制的10100111），在第一个表中放置1，在第二个表中放置3。 让我们调用第一个表BBeg和第二个表BEnd。 然后，对于每个字节b，有两种情况：如果它是255，则将8添加到当前连续的1的当前总和，并且您处于1的区域中。 否则，你用BBeg [b]位结束一个区域，并用BEnd [b]位开始一个新区域。 根据你想要的信息，你可以调整这个算法（这就是为什么我不在这里放任何代码，我不知道你想要什么输出的原因）。
一个缺陷是它不计算一个字节内的（小）连续的一组…
除了这个算法，朋友告诉我，如果它是用于磁盘压缩，只需查找不同于0（空磁盘区域）和255（完整磁盘区域）的字节。 这是一个快速的启发式方法，可以构建一个您必须压缩的块的映射。 也许这超出了本主题的范围……
这听起来可能有用：
你没有说你是想做某种RLE还是简单地计算字节内的零和一位（比如0b1001应该返回1×1 2×0 1×1）。
查找表以及用于快速检查的SWAR算法可以轻松地为您提供该信息。 有点像这样：
byte lut[0x10000] = { /* see below */ }; for (uint * word = words; word < words + bitmapSize; word++) { if (word == 0 || word == (uint)-1) // Fast bailout { // Do what you want if all 0 or all 1 } byte hiVal = lut[*word >> 16], loVal = lut[*word & 0xFFFF]; // Do what you want with hiVal and loVal
必须根据您的预期算法构建LUT。 如果你想计算单词中连续0和1的数量，你就会像这样构建它：
for (int i = 0; i < sizeof(lut); i++) lut[i] = countContiguousZero(i); // Or countContiguousOne(i) // The implementation of countContiguousZero can be slow, you don't care // The result of the function should return the largest number of contiguous zero (0 to 15, using the 4 low bits of the byte, and might return the position of the run in the 4 high bits of the byte // Since you've already dismissed word = 0, you don't need the 16 contiguous zero case.