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

Question

我正在寻找计算 uint8_t 中 b 位子序列(非重叠)零 数量的最快方法> 任意大小的数组 S(虽然 S 通常很小)。

约束:

• b 总是2的幂，有效值实际上只有:1、2、4、8、16和32
• 假定 uint8_t 中的位数为 8，并且 S * 8 可被 b
整除

例子:

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

我目前正在做的是将位“解压缩”为字节，然后使用零缓冲区 memcmp 子序列，但在我看来应该有一种更快的方法来执行此操作。

Answer 1

您可以使用与检测字符串中的空字节的众所周知方法类似的位旋转。例如对于 b=4，您可以读取一个 32 位字 x 并执行

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

此处，x - 0x11111111 生成一个值，其中如果 4 位组为零或已设置，则每个 4 位组的高位为 1；第二部分丢弃那些已经设置的，然后你只需要计算剩余的位。