快速搜索位数组中连续设置/清除位的代码？

Question

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

通过“相当快速”，我的意思是指能够利用机器字长并同时比较整个字，而不是进行可怕缓慢的逐位分析（例如使用vector<bool>进行的分析）。

这对于例如搜索卷的位图以查找空闲空间（用于碎片整理等）非常有用。

- user541686

---

你不能把数组当作整数数组处理，然后将整数与零进行比较吗？ - Andrew

@Andrew：这有点取决于你想要实现什么... 每次8位可能不会对齐。 - user541686

你可以将6个字节（如果BMP是彩色图像文件：6个字节是两个相邻的像素）与一个由6个零组成的数组进行比较。 - Hicham

@eharvest：我不是在谈论图片！这与光栅图像完全无关。我说的是位数组，即一组位。 - user541686

抱歉，我读你的问题太快了... - Hicham

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++，那么我包含了一个可以为您完成此操作的函数。如果您发现错误，请随时让我知道。

- user541686

Answer 2

听起来这可能会有用：

http://www.aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29 and 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.

- xryl669

Answer 3

我无法直接在内存单词上做出良好的解决方案，因此我想出了一个快速解决方案，它可以在字节上运行；为了方便起见，让我们勾画一下计算连续1的算法：

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

一个缺陷是它不能计算一个字节内的（小）连续1集合...

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

- Bentoy13