c++ - 如何快速识别巨大的二进制数据中1(索引)的连续范围？

有人可以建议使用更快的算法来识别大型二进制数据中1的连续范围吗？

遍历数据是唯一的解决方案吗？在最不希望的情况下，遍历会给出O(n)，我真的不想要。

有谁可以建议更快的算法？

如下图所示。我需要找到索引4000，它是1的连续范围的起始位置

index 0
|
00000000000000000000000000000000000000000011111100000

最佳答案

我想不出什么都不是O(n)，因为数据始终是未排序的。

但是，我可以想到快捷方式，因为您需要至少3个一组，并且是二进制数据。

#include <iostream>

using namespace std;

int main()
{
    unsigned int seed = 3758096384; //11100000000000000000000000000000
    unsigned int testvar = 419307644; //00011000111111100010000001111100
    int result = 0;
    int continuous = 0;

    while (seed != 7 && (continuous == 1 || result == 0)) {
        if (seed == (testvar & seed)) {
            result |= seed;
            continuous = 1;
        } else
            continuous = 0;
        seed >>= 1;
    }
    // result = 16646144 or 00000000111111100000000000000000
    cout << result << endl;
    //the index, 8388608 or 00000000100000000000000000000000
    cout << (int)((result ^ (result >> 1)) & ~(result >> 1)) << endl;
    return 0;
}

怎么运行的:
它是一个二进制滤波器，它创建3位掩码，并在循环的每一步中向左连续移1。

因此，您将这些数字用作过滤器:

3758096384 - 11100000000000000000000000000000
1879048192 - 01110000000000000000000000000000
939524096  - 00111000000000000000000000000000
...
14         - 00000000000000000000000000001110
7          - 00000000000000000000000000000111

然后，它检查种子是否与测试的数字和种子本身之间的逻辑与结果相符(这将过滤所有与过滤器不匹配的数字)。

如果种子和AND匹配，它将使用逻辑“或”将种子移到结果，并设置一个continuous以控制序列的连续性。第一次结果不连续时，它将中断循环。

最后，您将得到结果并可以通过以下方式计算索引:

1110
0111 SHIFT TO LEFT by 1 and XOR
1001
0111 NOT (SHIFT TO LEFT by 1) and AND
------------
1000

您将需要按32位块扫描50gb数据(很容易适应64位，甚至对其进行 vector 化处理)。