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

是否有一些合理的快速代码可以帮助我快速搜索一个大的位图（几兆字节）用于连续零位或一位的运行？ “合理快速”我的意思是可以利用机器字的大小并一次比较整个单词，而不是进行可怕的慢速比特分析（如vector<bool>）。用于搜索连续置位/清除位的位数组的快速代码？

它对于例如搜索卷的位图以获得可用空间（用于碎片整理等）。

来源

2012-07-30 Mehrdad

你不能把你的数组当作一个整数数组并将整数比较为零吗？ – Andrew 2012-07-30 11:06:36

@Andrew：这种类型取决于你想要达到的效果......这些比特可能不会一次对齐8比特。 – Mehrdad 2012-07-30 11:42:54

您可以比较6个字节（如果bmp是彩色图像文件：6个字节是两个连续像素），并且有6个零的数组。 – 2012-07-30 11:48:35

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代码，但没有明显改善性能。但是，一般来说，代码比逐位分析快很多倍，所以我认为它可能有用。

它应该很容易测试，如果你可以以某种方式获得缓冲区的缓冲区，并且如果你使用Visual C++，那么我有一个函数可以帮助你。如果您发现错误，请随时通知我。

来源

2012-07-30 11:01:32 Mehrdad

我不知道如何直接在记忆词上做得很好，所以我编写了一个快速的解决方案，它处理字节;为了方便起见，我们来简单介绍一下连续计数的算法：

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

中的一个缺陷是，它不计数（小）组连续的一个字节内的人的...

除了这个算法，一个朋友告诉我，如果它是磁盘压缩，只是看不同的字节从0（空盘区）和255（全盘区）。建立你必须压缩的块的映射是一种快速启发式方法。也许它超出了这个话题的范围......

来源

2012-07-30 13:46:42 Bentoy13

听起来，这可能是有用的：

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.

来源

2012-08-01 10:27:33 xryl669

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

回答

相关问题