9

This is what I'm currently doing:

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;

Really nasty, I know, and it's killing performance.

What's the fastest way to find the bit offset of the first set of x consecutive 0 bits in a char array, where 0 < x < 7? I'm on GCC with SSE 4.2 so builtins like __builtin_ctz, __builtin_popcountl are an option, I just can't figure out the best way to use them.

4

9 回答 9

5

有多少个数字有 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...

};
于 2012-10-29T06:22:06.287 回答
3

这是一个与问题中提供的输出相匹配的函数（至少在有限的测试下）。它使用表格查找，表格是由一次性脚本生成的。老实说，我不确定它的性能是否与使用 bit testing hackery 或 GCC builtins 的建议相比具有竞争力，但我敢打赌它不会太远。

struct zeros {
    unsigned char leading;
    unsigned char internal;
    unsigned char trailing;
};

// forward declaration so the long, non-interesting table is at the 
//  end of this 
static struct zeros const zero_table[256];

int find_zero_bits_offset( char const* data, int datalen, int desired)
{
    int offset = -1;
    int found = 0;
    char const* dataptr = &data[0];
    char const* endptr  = &data[datalen];


    // first, find which byte the sequence of zeros begins

    while (!found && (dataptr != endptr)) {
        unsigned char ch1 = *dataptr++;
        unsigned char ch2 = (dataptr != endptr) ? *dataptr : 0xff;

        int internal = zero_table[ch1].internal;
        int trailing = zero_table[ch1].trailing;
        int leading =  zero_table[ch2].leading;

        found = (desired <= internal) || 
                (trailing && (desired <= (trailing + leading)));
    }


    // now zero in on where the sequence starts within the byte

    if (found) {
        char ch = 0;
        unsigned int mask = 0;

        --dataptr;

        // dataptr points to the byte where the sequence of zeros starts.
        //  figure out exactly where the sequence is...

        // there's possibly some opportunity for optimization, if neccesary,
        //  by testing if the sequence was found in the "leading", "internal", or
        //  "trailing" cases. But the explicit loop will only iterate at most
        //  8 times (and will early-out on the first iteration if the match is 
        //  for the "leading" case) that it didn't seem too important

        ch = *dataptr;
        offset = (dataptr - data) * 8;

        // figure out where the appropriate internal run starts
        // note that the offset we need to return isn't necessarily the
        //  offset for the run of zeros counted by zero_table[tmp].internal_offset
        //  since a sufficient shorter run might come first

        // there may be a more efficient bithack for this, but the
        //  loop will iterate at most 8 times...
        mask = ((1 << desired) - 1);
        mask <<= (8 - desired);

        while ((ch & mask) != 0) {
            ++offset;
            mask >>= 1;
        }
    }
    else {
        // however you want to handle the "not found" situation. 
        //  This is equivalent to what was in the question:
        offset = (endptr - data) * 8;
    }

    return offset;
}



static struct zeros const zero_table[256] = {
    { 8, 8, 8 },  // 0000 0000
    { 7, 7, 0 },  // 0000 0001
    { 6, 6, 1 },  // 0000 0010
    { 6, 6, 0 },  // 0000 0011
    { 5, 5, 2 },  // 0000 0100
    { 5, 5, 0 },  // 0000 0101
    { 5, 5, 1 },  // 0000 0110
    { 5, 5, 0 },  // 0000 0111
    { 4, 4, 3 },  // 0000 1000
    { 4, 4, 0 },  // 0000 1001
    { 4, 4, 1 },  // 0000 1010
    { 4, 4, 0 },  // 0000 1011
    { 4, 4, 2 },  // 0000 1100
    { 4, 4, 0 },  // 0000 1101
    { 4, 4, 1 },  // 0000 1110
    { 4, 4, 0 },  // 0000 1111
    { 3, 4, 4 },  // 0001 0000
    { 3, 3, 0 },  // 0001 0001
    { 3, 3, 1 },  // 0001 0010
    { 3, 3, 0 },  // 0001 0011
    { 3, 3, 2 },  // 0001 0100
    { 3, 3, 0 },  // 0001 0101
    { 3, 3, 1 },  // 0001 0110
    { 3, 3, 0 },  // 0001 0111
    { 3, 3, 3 },  // 0001 1000
    { 3, 3, 0 },  // 0001 1001
    { 3, 3, 1 },  // 0001 1010
    { 3, 3, 0 },  // 0001 1011
    { 3, 3, 2 },  // 0001 1100
    { 3, 3, 0 },  // 0001 1101
    { 3, 3, 1 },  // 0001 1110
    { 3, 3, 0 },  // 0001 1111
    { 2, 5, 5 },  // 0010 0000
    { 2, 4, 0 },  // 0010 0001
    { 2, 3, 1 },  // 0010 0010
    { 2, 3, 0 },  // 0010 0011
    { 2, 2, 2 },  // 0010 0100
    { 2, 2, 0 },  // 0010 0101
    { 2, 2, 1 },  // 0010 0110
    { 2, 2, 0 },  // 0010 0111
    { 2, 3, 3 },  // 0010 1000
    { 2, 2, 0 },  // 0010 1001
    { 2, 2, 1 },  // 0010 1010
    { 2, 2, 0 },  // 0010 1011
    { 2, 2, 2 },  // 0010 1100
    { 2, 2, 0 },  // 0010 1101
    { 2, 2, 1 },  // 0010 1110
    { 2, 2, 0 },  // 0010 1111
    { 2, 4, 4 },  // 0011 0000
    { 2, 3, 0 },  // 0011 0001
    { 2, 2, 1 },  // 0011 0010
    { 2, 2, 0 },  // 0011 0011
    { 2, 2, 2 },  // 0011 0100
    { 2, 2, 0 },  // 0011 0101
    { 2, 2, 1 },  // 0011 0110
    { 2, 2, 0 },  // 0011 0111
    { 2, 3, 3 },  // 0011 1000
    { 2, 2, 0 },  // 0011 1001
    { 2, 2, 1 },  // 0011 1010
    { 2, 2, 0 },  // 0011 1011
    { 2, 2, 2 },  // 0011 1100
    { 2, 2, 0 },  // 0011 1101
    { 2, 2, 1 },  // 0011 1110
    { 2, 2, 0 },  // 0011 1111
    { 1, 6, 6 },  // 0100 0000
    { 1, 5, 0 },  // 0100 0001
    { 1, 4, 1 },  // 0100 0010
    { 1, 4, 0 },  // 0100 0011
    { 1, 3, 2 },  // 0100 0100
    { 1, 3, 0 },  // 0100 0101
    { 1, 3, 1 },  // 0100 0110
    { 1, 3, 0 },  // 0100 0111
    { 1, 3, 3 },  // 0100 1000
    { 1, 2, 0 },  // 0100 1001
    { 1, 2, 1 },  // 0100 1010
    { 1, 2, 0 },  // 0100 1011
    { 1, 2, 2 },  // 0100 1100
    { 1, 2, 0 },  // 0100 1101
    { 1, 2, 1 },  // 0100 1110
    { 1, 2, 0 },  // 0100 1111
    { 1, 4, 4 },  // 0101 0000
    { 1, 3, 0 },  // 0101 0001
    { 1, 2, 1 },  // 0101 0010
    { 1, 2, 0 },  // 0101 0011
    { 1, 2, 2 },  // 0101 0100
    { 1, 1, 0 },  // 0101 0101
    { 1, 1, 1 },  // 0101 0110
    { 1, 1, 0 },  // 0101 0111
    { 1, 3, 3 },  // 0101 1000
    { 1, 2, 0 },  // 0101 1001
    { 1, 1, 1 },  // 0101 1010
    { 1, 1, 0 },  // 0101 1011
    { 1, 2, 2 },  // 0101 1100
    { 1, 1, 0 },  // 0101 1101
    { 1, 1, 1 },  // 0101 1110
    { 1, 1, 0 },  // 0101 1111
    { 1, 5, 5 },  // 0110 0000
    { 1, 4, 0 },  // 0110 0001
    { 1, 3, 1 },  // 0110 0010
    { 1, 3, 0 },  // 0110 0011
    { 1, 2, 2 },  // 0110 0100
    { 1, 2, 0 },  // 0110 0101
    { 1, 2, 1 },  // 0110 0110
    { 1, 2, 0 },  // 0110 0111
    { 1, 3, 3 },  // 0110 1000
    { 1, 2, 0 },  // 0110 1001
    { 1, 1, 1 },  // 0110 1010
    { 1, 1, 0 },  // 0110 1011
    { 1, 2, 2 },  // 0110 1100
    { 1, 1, 0 },  // 0110 1101
    { 1, 1, 1 },  // 0110 1110
    { 1, 1, 0 },  // 0110 1111
    { 1, 4, 4 },  // 0111 0000
    { 1, 3, 0 },  // 0111 0001
    { 1, 2, 1 },  // 0111 0010
    { 1, 2, 0 },  // 0111 0011
    { 1, 2, 2 },  // 0111 0100
    { 1, 1, 0 },  // 0111 0101
    { 1, 1, 1 },  // 0111 0110
    { 1, 1, 0 },  // 0111 0111
    { 1, 3, 3 },  // 0111 1000
    { 1, 2, 0 },  // 0111 1001
    { 1, 1, 1 },  // 0111 1010
    { 1, 1, 0 },  // 0111 1011
    { 1, 2, 2 },  // 0111 1100
    { 1, 1, 0 },  // 0111 1101
    { 1, 1, 1 },  // 0111 1110
    { 1, 1, 0 },  // 0111 1111
    { 0, 7, 7 },  // 1000 0000
    { 0, 6, 0 },  // 1000 0001
    { 0, 5, 1 },  // 1000 0010
    { 0, 5, 0 },  // 1000 0011
    { 0, 4, 2 },  // 1000 0100
    { 0, 4, 0 },  // 1000 0101
    { 0, 4, 1 },  // 1000 0110
    { 0, 4, 0 },  // 1000 0111
    { 0, 3, 3 },  // 1000 1000
    { 0, 3, 0 },  // 1000 1001
    { 0, 3, 1 },  // 1000 1010
    { 0, 3, 0 },  // 1000 1011
    { 0, 3, 2 },  // 1000 1100
    { 0, 3, 0 },  // 1000 1101
    { 0, 3, 1 },  // 1000 1110
    { 0, 3, 0 },  // 1000 1111
    { 0, 4, 4 },  // 1001 0000
    { 0, 3, 0 },  // 1001 0001
    { 0, 2, 1 },  // 1001 0010
    { 0, 2, 0 },  // 1001 0011
    { 0, 2, 2 },  // 1001 0100
    { 0, 2, 0 },  // 1001 0101
    { 0, 2, 1 },  // 1001 0110
    { 0, 2, 0 },  // 1001 0111
    { 0, 3, 3 },  // 1001 1000
    { 0, 2, 0 },  // 1001 1001
    { 0, 2, 1 },  // 1001 1010
    { 0, 2, 0 },  // 1001 1011
    { 0, 2, 2 },  // 1001 1100
    { 0, 2, 0 },  // 1001 1101
    { 0, 2, 1 },  // 1001 1110
    { 0, 2, 0 },  // 1001 1111
    { 0, 5, 5 },  // 1010 0000
    { 0, 4, 0 },  // 1010 0001
    { 0, 3, 1 },  // 1010 0010
    { 0, 3, 0 },  // 1010 0011
    { 0, 2, 2 },  // 1010 0100
    { 0, 2, 0 },  // 1010 0101
    { 0, 2, 1 },  // 1010 0110
    { 0, 2, 0 },  // 1010 0111
    { 0, 3, 3 },  // 1010 1000
    { 0, 2, 0 },  // 1010 1001
    { 0, 1, 1 },  // 1010 1010
    { 0, 1, 0 },  // 1010 1011
    { 0, 2, 2 },  // 1010 1100
    { 0, 1, 0 },  // 1010 1101
    { 0, 1, 1 },  // 1010 1110
    { 0, 1, 0 },  // 1010 1111
    { 0, 4, 4 },  // 1011 0000
    { 0, 3, 0 },  // 1011 0001
    { 0, 2, 1 },  // 1011 0010
    { 0, 2, 0 },  // 1011 0011
    { 0, 2, 2 },  // 1011 0100
    { 0, 1, 0 },  // 1011 0101
    { 0, 1, 1 },  // 1011 0110
    { 0, 1, 0 },  // 1011 0111
    { 0, 3, 3 },  // 1011 1000
    { 0, 2, 0 },  // 1011 1001
    { 0, 1, 1 },  // 1011 1010
    { 0, 1, 0 },  // 1011 1011
    { 0, 2, 2 },  // 1011 1100
    { 0, 1, 0 },  // 1011 1101
    { 0, 1, 1 },  // 1011 1110
    { 0, 1, 0 },  // 1011 1111
    { 0, 6, 6 },  // 1100 0000
    { 0, 5, 0 },  // 1100 0001
    { 0, 4, 1 },  // 1100 0010
    { 0, 4, 0 },  // 1100 0011
    { 0, 3, 2 },  // 1100 0100
    { 0, 3, 0 },  // 1100 0101
    { 0, 3, 1 },  // 1100 0110
    { 0, 3, 0 },  // 1100 0111
    { 0, 3, 3 },  // 1100 1000
    { 0, 2, 0 },  // 1100 1001
    { 0, 2, 1 },  // 1100 1010
    { 0, 2, 0 },  // 1100 1011
    { 0, 2, 2 },  // 1100 1100
    { 0, 2, 0 },  // 1100 1101
    { 0, 2, 1 },  // 1100 1110
    { 0, 2, 0 },  // 1100 1111
    { 0, 4, 4 },  // 1101 0000
    { 0, 3, 0 },  // 1101 0001
    { 0, 2, 1 },  // 1101 0010
    { 0, 2, 0 },  // 1101 0011
    { 0, 2, 2 },  // 1101 0100
    { 0, 1, 0 },  // 1101 0101
    { 0, 1, 1 },  // 1101 0110
    { 0, 1, 0 },  // 1101 0111
    { 0, 3, 3 },  // 1101 1000
    { 0, 2, 0 },  // 1101 1001
    { 0, 1, 1 },  // 1101 1010
    { 0, 1, 0 },  // 1101 1011
    { 0, 2, 2 },  // 1101 1100
    { 0, 1, 0 },  // 1101 1101
    { 0, 1, 1 },  // 1101 1110
    { 0, 1, 0 },  // 1101 1111
    { 0, 5, 5 },  // 1110 0000
    { 0, 4, 0 },  // 1110 0001
    { 0, 3, 1 },  // 1110 0010
    { 0, 3, 0 },  // 1110 0011
    { 0, 2, 2 },  // 1110 0100
    { 0, 2, 0 },  // 1110 0101
    { 0, 2, 1 },  // 1110 0110
    { 0, 2, 0 },  // 1110 0111
    { 0, 3, 3 },  // 1110 1000
    { 0, 2, 0 },  // 1110 1001
    { 0, 1, 1 },  // 1110 1010
    { 0, 1, 0 },  // 1110 1011
    { 0, 2, 2 },  // 1110 1100
    { 0, 1, 0 },  // 1110 1101
    { 0, 1, 1 },  // 1110 1110
    { 0, 1, 0 },  // 1110 1111
    { 0, 4, 4 },  // 1111 0000
    { 0, 3, 0 },  // 1111 0001
    { 0, 2, 1 },  // 1111 0010
    { 0, 2, 0 },  // 1111 0011
    { 0, 2, 2 },  // 1111 0100
    { 0, 1, 0 },  // 1111 0101
    { 0, 1, 1 },  // 1111 0110
    { 0, 1, 0 },  // 1111 0111
    { 0, 3, 3 },  // 1111 1000
    { 0, 2, 0 },  // 1111 1001
    { 0, 1, 1 },  // 1111 1010
    { 0, 1, 0 },  // 1111 1011
    { 0, 2, 2 },  // 1111 1100
    { 0, 1, 0 },  // 1111 1101
    { 0, 1, 1 },  // 1111 1110
    { 0, 0, 0 },  // 1111 1111
};
于 2012-10-30T05:27:16.373 回答
2

逐字遍历数组（32 位或 64 位取决于您的拱门）。使用__builtin_clzand__builtin_ctz计算每个单词的前导零和尾随零。

连续零有两种情况：

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

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

于 2012-10-29T05:44:50.000 回答
1

请注意这些算术技巧：

// remove the trailing one bits
y = x & (x + 1);

x       11100011
        +      1
        --------
x+1     11100100
x&(x+1) 11100000

// remove the trailing zero bits
z = y | (y - 1);

y       11100000
        -      1
        --------
y-1     11011111
y|(y-1) 11111111

// isolate the hole
hole = z - x;
hole = z ^ x;

z       11111111
x       11100011
        --------
z^x     00011100

// Now you can count the set bits of the hole.
length = bitcount(hole);

// Or you can make it by computing highbit only (log2).
length = highbit(z^y) - highbit(x^y);

因此，一种可能的算法是使用这些技巧与大整数算术和循环直到长度==0（没有更多的洞）或长度>=n（你开始下一个循环 x=z;）。

您可以自己模拟大整数，逐字节作用于收集，并在没有进位时停止。

  • 仅当 byte==0xFF 时 x+1 才有进位
  • y-1 只有在 byte==0x00 时才有进位
  • highbit 易于在单个字节上编程

这会给出这样的结果：

// return 1-based position of highest bit set in a byte
int highbit(unsigned char c)
{
    unsigned char n;
    int position = 0;
    n = c >> 4;
    if( n > 0 ) { c=n; position+=4; };
    n = c >> 2;
    if( n > 0 ) { c=n; position+=2; };
    n = c >> 1;
    if( n > 0 ) { c=n; position+=1; };
    position += c;
    return position;
}

int find_consecutive_zeros( unsigned char *bits , int nbytes , int nzero )
{
    int i,nTrailingOnes,nTrailingZero,sizeOfNextHole;
    unsigned char x,y;
    for(i=0 , x=bits[0]; 1; )
    {
        // perform y=x&(x+1) to count and remove trailing ones
        for(;x==0xFF && i<nbytes-1;x=bits[++i]);
        y = x&(x+1);
        nTrailingOnes = 8*i + highbit( x^y );
        // perform x=y|(y-1); to count and remove trailing zeros
        for(;y==0 && i<nbytes-1;y=bits[++i]);
        x = y|(y-1);
        nTrailingZero = 8*i + highbit( x^y );
        sizeOfNextHole = nTrailingZero - nTrailingOnes;
        // if size of hole is long enough, return it's low bit rank (0-based)
        if( sizeOfNextHole >= nzero ) return nTrailingOnes;
        // or return -1 if no more hole
        if( sizeOfNextHole == 0 ) return -1;
    }
}

您可以通过使用比基本集合更长的字节来提高效率......

编辑：当你有一个固定大小的 nzero 像 6 时加速
上面的算法迭代所有的孔，并且可能会在小孔上浪费时间。
您可以使用填充了小孔的预计算表来避免这种情况。

例如 10010101 有 3 个孔太短，因此您可以将其替换为 11111111。
但您必须保持前导零和尾随零不变。

要初始化这样的表，您只需使用 0xFF 和 xor 与包含 1 位代替尾随零(x|(x-1))^x的掩码和包含 1 位代替前导零的掩码((1<<highbit(x))-1)^0xFF。
为 10000001 添加一个例外，唯一的字节在 1 之间包含 6 个零。

EDIT2：我首先处理了第一个字节的最低有效位的位序列，这很适合算术方法。该问题首先明确使用第一个字节的最高有效位。所以我必须反转位以适应问题，这是在初始化表时完成的......

int reversebits(unsigned char c)
{
    c = ((c & 0x0F) << 4) | ((c & 0xF0) >> 4);
    c = ((c & 0x33) << 2) | ((c & 0xCC) >> 2);
    c = ((c & 0x55) << 1) | ((c & 0xAA) >> 1);
    return c;
}
void initializeFillShortHoles(unsigned char fillShortHoles[256])
    for(unsigned int x=0;x<256;x++) {
        fillShortHoles[reversebits(x)] = ((1<<highbit(x))-1) ^ (x|(x-1)) ^ x;
    }
    fillShortHoles[0]=0;     // no use to reverse bits for those two
    fillShortHoles[129]=129;
}

然后你只需替换出现的x=bits[ i ]with x=fillShortHoles[ bits[ i ] ]，你就完成了：

int find_6_consecutive_zeros( unsigned char *bits , int nbytes )
{
    static unsigned char fillShortHoles[256];
    static unsigned char highbitTable[256];
    static first=1;
    int i,nTrailingOnes,nTrailingZero,sizeOfNextHole;
    unsigned char x,y;

    if (first)
    {
        first = 0;
        initializeFillShortHoles( fillShortHoles );
        for(i=0;i<256;i++) highbitTable[i]=highbit(i);
    }
    for(x=fillShortHoles[bits[i=0]]; 1; )
    {
        // perform y=x&(x+1) to count trailing ones
        for(;x==0xFF && i<nbytes-1;x=fillShortHoles[bits[++i]]);
        y = x&(x+1);
        nTrailingOnes = 8*i + highbitTable[ x^y ];
        // perform z=y|(y-1); to count trailing zeros
        for(;y==0 && i<nbytes-1;y=fillShortHoles[bits[++i]]);
        x = y|(y-1);
        nTrailingZero = 8*i + highbitTable[ x^y ];
        sizeOfNextHole = nTrailingZero - nTrailingOnes;
        // if size of hole is long enough, return it's low bit rank (0-based)
        if( sizeOfNextHole >= 6 ) return nTrailingOnes;
        // or return -1 if no more hole
        if( sizeOfNextHole == 0 ) return -1;
    }
}

EDIT3：最后，对于 nzero<=9，更快的方法是缓存每对字节的位置。

int find_n_consecutive_zeros_bypair( unsigned char *bits , int nbytes , int nzero)
{
    static int first=1;
    static signed char holepositionbypair[8][65536];
    signed char position;
    int i;
    unsigned short x;
    if (first)
    {
        first = 0;
        for(i=0;i<8;i++) {
            initializeHolePositionByPair( holepositionbypair[i] , i+1 );
        }
    }
    for (i=0 , x=0xFF; i<nbytes; i++) {
        x = (x << 8) + bits[i];
        if( (position = holepositionbypair[nzero-1][x]) >= 0) return (i-1)*8 + position;
    }
    return -1;
}

注意初始化 x=0xFF 将处理 nbytes<2 的情况。

无论您如何逐对填充缓存孔位置，它都只会在初始化时调用。我当然提出算术方法：

int highbit16(unsigned short c)
{
    unsigned short n;
    int position = 0;
    n = c >> 8;
    if( n ) { c=n; position+=8; };
    n = c >> 4;
    if( n ) { c=n; position+=4; };
    n = c >> 2;
    if( n ) { c=n; position+=2; };
    n = c >> 1;
    if( n ) { c=n; position+=1; };
    position += c;
    return position;
}
unsigned short reversebits16(unsigned short c)
{
    c = ((c & 0x00FF) << 8) | ((c & 0xFF00) >> 8);
    c = ((c & 0x0F0F) << 4) | ((c & 0xF0F0) >> 4);
    c = ((c & 0x3333) << 2) | ((c & 0xCCCC) >> 2);
    c = ((c & 0x5555) << 1) | ((c & 0xAAAA) >> 1);
    return c;
}
initializeHolePositionByPair(signed char holepositionbypair[65536],int n)
{
    int i,n1,n0;
    unsigned short x,y;
    signed char position;
    for(i=0;i<65536;i++) {
        position = -1;
        x = i;
        while(x != 0xFFFF) {
            /* remove trailing ones */
            y = x&(x+1);
            n1 = highbit16(x^y);
            /* remove trailing zeros */
            x = y|(y-1);
            n0 = highbit16(x^y);
            if(n0-n1>=n) {
                position = n1; break;
            }
        }
        holepositionbypair[reversebits16(i)] = position;
    }
}
于 2012-10-31T23:53:55.103 回答
0

让我试试 - 怎么样：

class bitIterator{
    unsigned char* farray;
    int foffset;
public:
    bitIterator(unsigned char* array, int offset)
        :farray(array), foffset(offset)
    {}

    bool operator*() const {
        return (farray[foffset/8] >> (7 - foffset%8)) & 1;
    }

    bitIterator& operator++(){
        foffset++;
        return *this;
    }

    int offset() const {
        return foffset; 
    }

};

// Just to demonstrate how to call it
int find_first_n(unsigned char* buffer, int length, int n){
    return std::search_n(bitIterator(buffer, 0), bitIterator(buffer, length*8), n, 0).offset();
}

那只是为了好玩...

现在，如果您真的想从中挤出一些性能，我会建议

int find_first_n(unsigned char* buffer, int length, int n){
    int prev_trail = 0;
    unsigned int* buf = reinterpret_cast<unsigned int*>(buffer);
    int len = length/sizeof(int); 
    // Last few bytes will need special treatment if your array is not multple of int-size length.
    // However last bytes should not influence overall performance of code - assuming it is used on rather long arrays.
    // If you plan using rather short arrays (20-50 bytes?) you will probably be better off just using plain char.
    for (int i=0; i<len; i++){
        if (!buf[i]) return i*sizeof(int)*8-prev_trail; // __builtin_clz and __builtin_ctz are undefined on zero ;
        // EDIT:
        if (!~buf[i]){
            prev_trail = 0;
            continue;
        }
        // END EDIT!


        int shft = __builtin_clz(buf[i]);
        if (shft + prev_trail >= n) return i*sizeof(int)*8-prev_trail; // Leading + previous trailing <= n
                                                           // Not enough leading zeros, continue search.
        prev_trail = __builtin_ctz(buf[i]); // Store it to use for next int in array
        unsigned int tmp =0;               
        while(shft < sizeof(int)*8-prev_trail){   // While we haven't got to trailing zeros in this uint
            tmp = buf[i] << shft;               // Shift-out leading zeros;
            shft += (__builtin_clz(~tmp));
            tmp = buf[i] << shft;               // Shift-out leading ones;

            lead_zeros = __builtin_clz(tmp);
            if (lead_zeros >= n)                // and see if have enough leading zeros.
                return i*sizeof(int)*8+shft;

            shft += lead_zeros;
        }
        return length*8; // Not found :(
    }

这很难阅读，但概念很简单 - 只需遍历每个 int 大小的块，并查看每个块的前导零 + 前一个的尾随零是否 >= n。如果不只是反复移出前导零和后面的零（设置位），并再次检查尾随零> = n，只要我们没有得到尾随字节。

还有一个想法：

int find_first_n(unsigned char* buffer, int length, int n){
    union {
        unsigned char chr[2];
        unsigned int uit;
    };

    unsigned int onemask = 0x8000;
    for (int i = 1 ; i<n; i++) onemask = onemask | (onemask >> 1);

    int* masks = new int[8];
    for (int i = 0; i<8; i++){
        masks[i]=onemask >> i;
    }

    // generating masks - eg. for n == 3 would be:
    // [ 1110 0000 0000 0000 ]
    // [ 0111 0000 0000 0000 ]
    // [ 0011 1000 0000 0000 ]
    // [ 0001 1100 0000 0000 ]
    // [ ... ]
    // [ 0000 0001 1100 0000 ]


    uit = 0;
    for (int i=0; i<length-1; i++){
        chr[0] = buffer[i];
        chr[1] = buffer[i+1];
        for (int j=0; j<8; j++){
            if (!(uit & masks[j])) return i*8+j;
        }
    }
    chr[0] = buffer[length-1];
    chr[1] = 0xff; // Fill with ones at the end.
    for (int j=0; j<8; j++){
        if (!(uit & masks[j])) return (length-1)*8+j;
    }
    return length*8; // Not found :(
}

您可能很想将指向仍在缓冲区中的变量的指针直接转换为 word ( reinterpret_cast<unsigned short int*>(buffer[i])) 并在不使用联合的情况下应用掩码。但是请注意，此类操作中有一半会使用未对齐的变量，这会降低性能，并且在某些平台上甚至会产生异常。

于 2012-10-29T08:36:12.377 回答
0

在这里，试试这个代码。

int dataLen = 500;
char data[dataLen];
//Get the data in place with whatever is your algorithm.
int i,j;
unsigned int dataSample;
unsigned int mask;
for(i=0;i<dataLen-1;i++){
    dataSample=((unsigned int)(data[i+1]) << 8) | (unsigned int) (data[i]);
    mask=(1<<6) - 1 ; //6 consecutive 1's
    for(j=0;j<8;j++){
        if((dataSample & (mask << j)) == 0){
            printf("Found consecutive 6 zeros at byte %d offset %d\n",i,j);
            j+=5; // Followed by j++ makes it j+=6.
        }
    }
}
于 2012-10-29T06:16:46.353 回答
0

假设您正在寻找正好6 个连续的零。您可以使用这样的代码片段：

unsigned d1 = 0xff;
for (int i = 0; i < dataLen; i += 3) {
  unsigned d1 = (d1 << 24) | (data[i] << 16) | (data [i+1] << 8) | (data[i+2]);
  unsigned d2 = ~d1; // ones
  unsigned d3 = d2 & (d2 << 2) & (d2 << 4);
  unsigned d4 = d3 & (d3 << 1);
  if (!d4) continue;
  doSomethingWithTheSequence(i, d4);
}

d1将前一次运行的最后一个字节与三个新字节结合起来。因此，您可以以 3 的倍数迭代数据。您可以尝试 2 的倍数，这可能更有效，因为您可以将数据视为 16 位原子量。您还可以尝试 4 的倍数，然后对 64 位数字进行后续计算，尤其是在 64 位平台上时。或者您为跨越字节的零序列引入了一种特殊情况。

d2反转位模式，这很有用，因为移位会引入人为的零，但不会引入人为的零。d3在偏移量 0、2 和 4 处查找三个匹配的偏移量。d4然后添加另一位偏移量，从而组合从 0 到 5 的所有偏移量。所以d4当且仅当d1. 然后您可以使用__builtin_clz来识别 in 中最高d4位的位置，这也是这 6 位中的第一个的位置d1。从中你可以得到职位data。

您可以通过添加一个循环并希望编译器将其优化掉，或者通过提供一个内联模板函数来调整代码以适应其他运行长度，该函数以适合所需运行长度的方式进行d4计算。d2

于 2012-10-29T10:24:18.310 回答
0

对于一个字节，你只需要做 3 次测试：

if( (byte & 0x3F) == 0) { /* Found */ }
if( (byte & 0x7E) == 0) { /* Found */ }
if( (byte & 0xFC) == 0) { /* Found */ }

将其扩展到更广泛的值应该相对容易。例如，对于uint32_t：

tempValue1 = value & 0x3F3F3F3F;
tempValue2 = value & 0x7E7E7E7E;
tempValue3 = value & 0xFCFCFCFC;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }
tempValue1 >>= 8;
tempValue2 >>= 8;
tempValue3 >>= 8;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }
tempValue1 >>= 8;
tempValue2 >>= 8;
tempValue3 >>= 8;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }
tempValue1 >>= 8;
tempValue2 >>= 8;
tempValue3 >>= 8;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }

上面的代码看起来不是最好的方法（因为它可能不是）。我故意这样写，以便更容易了解如何使用 SSE 完成。对于 SSE，它与上述类似（但范围更广）。

但是，对于 SSE，您可以并行进行所有比较并摆脱大量分支。例如，您可以对 3 个掩码中的每一个进行 AND 并使用PCMPEQB3 次，然后将这些结果组合在一起，然后执行一次PMOVMSKB；这将为您提供一个 16 位值（表示 16 个字节 - 每个源字节一位），可以使用单个 进行测试if(result_flags == 0) { /* None of the 16 bytes matched */ }，其中最终测试可能在“do/while”循环的末尾。

于 2012-10-29T07:24:07.023 回答
0

我将通过利用 x86 小端序和未对齐的内存访问能力来解决这个问题。使用 popcount 查找候选词，然后使用 __builtin_ctz 通过循环查找位置。这从您的代码中消除了一个循环，并在单词不是候选词时避免位搜索循环。在大端机器上，您需要使用 htons(*(unsigned short *)p) 来交换字节。这需要一台允许非对齐字访问的机器。您还需要在数组末尾设置额外的 0xFF 字节。

unsigned char *p;
unsigned short v;
int c;
for (p = data; p < data + sizeof(data); p++)
  if (__builtin_popcount(*(unsigned short *)p) <= 16 - desired)
  { for (v = *(unsigned short *)p, c = 0; __builtin_ctz(v) < desired; v>>=1, c++) ;
    if (c < 16) // Gotcha @ p starting at bit c
      break;
  }
if (c == 16 || p >= data + sizeof(data)) // didn't find
else // found
于 2020-11-26T03:39:58.410 回答