用于搜索位阵列以查找连续设置/清除位的快速代码

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++，那么我提供了一个函数可以帮你做到这一点。如果你发现虫子，请随时告诉我。

Answer 2

我不知道如何直接处理内存字，所以我想出了一个处理字节的快速解决方案；为了方便起见，让我们画出一个计算连续数的算法：

构造两个大小为256的表，在其中为0和255之间的每个数字写入，即字节开头和结尾的尾随1的数量。例如，对于数字167（二进制为10100111），将1放在第一个表中，将3放在第二个表中。让我们称第一张表为BBeg，第二张表为BEnd。然后，对于每个字节b，有两种情况：如果它是255，那么在当前连续的一组一的当前和上加8，就处于一个一的区域中。否则，您将用BBeg[b]位结束一个区域，并用BEnd[b]位开始一个新区域。根据你想要的信息，你可以调整这个算法（这就是为什么我不在这里放任何代码的原因，我不知道你想要什么输出）。

一个缺陷是它不计算一个字节内的（小的）连续一组1。。。

除了这个算法，一个朋友告诉我，如果是磁盘压缩，只需查找0（空磁盘区域）和255（满磁盘区域）之间的字节。这是一种快速的启发式方法，可以构建一个需要压缩哪些块的映射。也许这超出了这个话题的范围。。。

Answer 3

听起来这可能很有用：

http://www.aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29和http://www.aggregate.org/MAGIC/#Leading%20Zero%20Count

你没有说你是否想做某种RLE，或者只是在字节中计数零和一位（比如0b1001应该返回1x1 2x0 1x1）。

查找表加上快速检查的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.