代码之家 › 专栏 › 技术社区 › PeterK

计算字节数组中的零b位子序列

bit-manipulation c++

PeterK · 技术社区 · 9 年前

我正在寻找计算 b -位子序列(非重叠) 在中 uint8_t 任意大小的数组 S ( S 但通常很小)。

限制条件:

b 始终是2的幂,有效值实际上只有:1、2、4、8、16和32
假设 单位8_t S*8系列 可除以 b

示例:

b=4,阵列= 0xA0 0x39 0x04 0x30 -正确答案是3
b=1,阵列= 0xFF 0x1F 0xF8 -正确答案是6
b=16,阵列= 0x05 0x16 0x32 0x00 -正确答案是0

我目前正在做的是将位“解压缩”成字节,然后用零缓冲区memcmp子序列,但在我看来,应该有一种更快的方法来实现这一点。

2 回复 | 直到 9 年前

Falk Hüffner 9 年前

您可以使用位循环,类似于检测字符串中的空字节的著名方法。例如,对于b=4,可以读取32位字 x 并且这样做

__builtin_popcount((x - 0x11111111) & (~x & 0x88888888))

x - 0x11111111 如果4位组为零或已设置,则生成每个4位组的高位为1的值;第二部分丢弃已经设置好的部分,然后只计算剩余的位数。

BeyelerStudios 9 年前

对于仅考虑从以下位置开始的序列的附加约束 b 位偏移有一个非常简单的解决方案(这里也不存在结束性问题,因为您只考虑整块零):

size_t countZeroChunks(const uint8_t* bytes, size_t nbytes, uint8_t b) {
    assert(b == 2 || b == 4 || b == 8 || b == 16 || b == 32);
    size_t count = 0;
    if(b <= 8) {
        // chunks fit inside a byte
        for(size_t i = 0; i < nbytes; ++i) {
            uint8_t byte = *bytes++;
            for(uint8_t offset = 0; offset < 8; offset += b) {
                // collect bits in chunk
                // e.g. for b=2 at offset=2
                // yyyyxxyy >> 2 -> 00yyyyxx
                // 00yyyyxx << 6 -> xx000000
                uint8_t chunk = (byte >> offset) << ((8 - offset) % 8);
                if(chunk == 0)
                    ++count;
            }
        }
    } else {
        // chunks span multiple bytes
        size_t nchunks = nbytes * 8 / b;
        for(size_t i = 0; i < nchunks; ++i) {
            // collect chunk from bytes
            uint32_t chunk = 0;
            for(size_t k = 0, bytesPerChunk = b / 8; k < bytesPerChunk; ++k)
                chunk |= (uint32_t)(*bytes++) << (k * 8);
            if(chunk == 0)
                ++count;
        }
    }
    return count;
}