在char数组中找到最多6个连续0位的最快方法

Question

这就是我目前正在做的事情:

int dataLen = 500;
char data[dataLen];
int desired = 1; // between 1 and 6, inclusive
...
char bits[dataLen * 8];
for (int32 j = 0; j < dataLen; j++) {
    for (int i = 0; i < 8; i++) {
        bits[j*8+i] = ( (data[j] & (1 << (7-i))) ? '1' : '0' );
    }
}
int offset = std::search_n(bits, bits + dataLen*8, desired, '0') - bits;

我知道真的很讨厌,而且它的性能很差.

查找xchar数组中第一组连续0位的位偏移的最快方法是什么0 < x < 7？我在GCC上使用SSE 4.2,所以内置像__builtin_ctz,__ builtin_popcountl是一个选项,我只是无法弄清楚使用它们的最佳方式.

Answer 1

有多少个数字有6个连续的0位(即使考虑2个连续的字节)？

Byte 1
XXXXXXXX
000000??             0/1/2/3
?000000?             0/1/128/129
??000000             0/64/128/192

因此,如果我们一次考虑1个字节,那么0/1/2/3/64/128/192

Byte a   Byte b
XXXXXXXX XXXXXXXX
??100000 0???????    (a & 31 == 0) && (b & 128 == 0)
???10000 00??????    (a & 15 == 0) && (b & 192 == 0)
????1000 000?????    (a & 7  == 0) && (b & 224 == 0)
?????100 0000????    (a & 3  == 0) && (b & 240 == 0)
??????10 00000???    (a & 1  == 0) && (b & 248 == 0)

因此绝对最多12次测试可以为您提供所有组合.
我相信如果你巧妙地进行比较,你可以减少它.

如果我们在下面使用@Michael Burr解决方案来使用表驱动方法.然后我们可以组织它,以便您可以每个字节进行一次或两次比较.

struct TestStruct
{
    bool    is6Consecutive;
    bool    hasTrailing;
    int     maskNextByte;
    int     offset;
};
TestStruct   testData[256];

std::size_t findOffsetOf_6ConsecutiveZero(char const* data, size_t size)
{
    for(int loop = 0;loop < (size-1); ++loop)
    {
        char const&           val  = data[loop];
        TestStructure const&  test = testData[val];

        if (test.is6Consecutive)
        {   return loop*8 + test.offset;
        }

        if (test.hasTrailing)
        {
            if ((data[loop + 1] & test.maskNextByte) == 0)
            {   return loop*8 + test.offset;
            }
        }
    }
    // Test last byte
    TestStructure const&  test = testData[data[size-1]];
    if (test.is6Consecutive)
    {   return (size-1)*8 + test.offset;
    }

    return -1;
}

前几个表条目:

TestStruct   testData[256] =
{
    {true,  false, 0x00, 0},
    {true,  false, 0x00, 0},
    {true,  false, 0x00, 0},
    {true,  false, 0x00, 0},
    {false, true,  0xf0, 6},  // 4 => 00000100 <Next 4 bytes are zero we hit>
    {false, false, 0x00, 0},  // 5 => 00000101 <Ignore and move on>
    {false, true,  0xf8, 7},  // 6 => 00000110 <Next 5 bytes are zero we hit>
    etc...

};

Answer 2

逐字迭代数组（32 位或 64 位取决于您的架构）。使用__builtin_clz和__builtin_ctz计算每个单词的前导零和尾随零。

连续零有两种情况：

• 一言以蔽之
• 跨越形容词。

第一种情况很容易检查。第二种情况需要检查此项的前导零 + 前一项的尾随零是否 >= 6。