如何确定一个字节中的一个字节是否为空

Question

我正在从 glibc 读取“strlen”源代码，开发人员发现加快它的技巧是读取 n 个字节，其中 n 是一个长字的大小，而不是在每次迭代时读取 1 个字节。

我假设一个长字有 4 个字节。

棘手的部分是函数读取的每个 4 字节的“块”都可以包含一个空字节，因此在每次迭代时，函数必须检查块中是否有空字节。他们这样做

if (((longword - lomagic) & ~longword & himagic) != 0) { /* null byte found */ }

哪里longword是数据块，himagic和lowmagic是神奇的值，定义为：

himagic = 0x80808080L;
lomagic = 0x01010101L;

这是对这些值的评论

/* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
 the "holes."  Note that there is a hole just to the left of
 each byte, with an extra at the end:

 bits:  01111110 11111110 11111110 11111111
 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

 The 1-bits make sure that carries propagate to the next 0-bit.
 The 0-bits provide holes for carries to fall into.  */

这个寻找空字节的技巧是如何工作的？

Answer 1

来自Sean Eron Anderson著名的“Bit Twiddling Hacks”页面，描述了glibc您所指的实现中当前使用的内容（Anderson 称其为算法hasless(v, 1)）：

(v - 0x01010101UL)只要 v 中的相应字节为零或大于，子表达式, 就会计算为任何字节中设置的高位 0x80。子表达式~v & 0x80808080UL计算为以字节为单位设置的高位，其中 v 的字节没有设置高位（因此字节小于0x80）。最后，通过对这两个子表达式进行 AND 运算，结果是高位设置，其中 v 中的字节为零，因为由于大于0x80第一个子表达式中的值而设置的高位被第二个子表达式屏蔽掉。

glibc源代码中的注释似乎令人困惑，因为它不再适用于代码实际执行的操作——它描述的是安德森在描述hasless(v, 1)算法之前描述的算法的实现。