在 int 中测试 4 个字节的零

Question

我是来求技巧的。我有一个 32 位整数（即 4 个字节）。我想为每个字节测试零，如果其中一个为真，则 return 为真。

例如

int c1 = 0x01020304
cout<<test(c1)<<endl; // output false
int c2 = 0x00010203
cout<<test(c2)<<endl; // output true
int c3 = 0xfffefc00
cout<<test(c3)<<endl; // output true

有没有什么技巧可以在最少的 CPU 周期内做到这一点？

Answer 1

您可以通过屏蔽 & 操作中的每个字节并将结果与零进行比较来测试它：

bool hasZeroByte(int32_t n) {
    return !(n & 0x000000FF)
        || !(n & 0x0000FF00)
        || !(n & 0x00FF0000)
        || !(n & 0xFF000000);
}

Answer 2

执行此操作的最快方法可能是使用 strnlen，因为大多数编译器都会对此进行优化，以使用低级指令在字符串中查找零字节。

bool hasZeroByte(int32_t n) {
    return strnlen(reinterpret_cast<char *>(&n), 4) < 4;
}

如果你想更明确一点，你可以使用 memchr 函数，它被记录下来完全按照你的要求做：

bool hasZeroByte(int32_t n) {
    return memchr(reinterpret_cast<void *>(&n), 0, 4) != nullptr;
}

对于那些不相信这个答案的人，请随意看一下 glibc implementation of strlen，看看它已经在做其他答案中提到的所有位技巧。

另请参阅：

Answer 3

著名的bithacks页面中有几种方法

bool hasZeroByte(unsigned int v)
{
    return ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
}

或

bool hasZeroByte = ((v + 0x7efefeff) ^ ~v) & 0x81010100;
if (hasZeroByte) // or may just have 0x80 in the high byte
{
  hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
}

以及编译为汇编时可能最紧凑的方式

#define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)

因为它们是技巧，所以它们很难理解，所以如果你想要清楚，屏蔽掉每个字节并像 dasblinkenlight 的回答中那样检查

Example assembly output on Compiler Explorer

在 int 中测试 4 个字节的零

Test zero for 4 bytes in an int

c++

algorithm

bit