快速的strlen我发现这个代码有位操作
int strlen_my(const char *s)
{
int len = 0;
for(;;)
{
unsigned x = *(unsigned*)s;
if((x & 0xFF) == 0) return len;
if((x & 0xFF00) == 0) return len + 1;
if((x & 0xFF0000) == 0) return len + 2;
if((x & 0xFF000000) == 0) return len + 3;
s += 4, len += 4;
}
}
我在知道它是如何工作非常感兴趣。 ¿任何人都可以解释它是如何工作的？
与1进行按位AND将从其他操作数检索位模式。意思是，10101 & 11111 = 10101。如果按位AND的结果为0，那么我们知道我们知道另一个操作数是0.当将单个字节与0xFF（ones）进行与时，结果为0将指示NULL字节。
代码本身检查字节数组的四个字节分区中的每个字节。 注意：此代码不可移植;在另一台机器或编译器上，unsigned int可能超过4个字节。使用uint32_t数据类型可能会更好，以确保32位无符号整数。
首先要注意的是，在小端机上，组成字符数组的字节将按相反的顺序读入无符号数据类型;也就是说，如果当前地址的四个字节是与abcd对应的位模式，那么无符号变量将包含对应于dcba的位模式。
第二个是C中的一个十六进制数字常量会产生一个int大小的数字，并在位模式的小端指定字节。意思是，当用4字节整数编译时，0xFF实际上是0x000000FF。 0xFF00是0x0000FF00。等等。
所以程序基本上是在四个可能的位置寻找NULL字符。如果当前分区中没有NULL字符，则前进到下一个四字节插槽。
以char数组abcdef为例。在C中，字符串常量的末尾总是有空终止符，所以在该字符串的末尾有一个字节0x00。
它会工作如下：
读 “ABCD” 为unsigned int类型X：
x: 0x64636261 [ASCII representations for "dcba"]
检查每个字节的空终止：
0x64636261
& 0x000000FF
0x00000061 != 0,
0x64636261
& 0x0000FF00
0x00006200 != 0,
并检查其他两个职位;在这个4字节分区中没有空终止符，所以前进到下一个分区。
读 “EF” 到unsigned int的X：
x: 0xBF006665 [ASCII representations for "fe"]
注为0xBF字节;这已经超过了字符串的长度，所以我们从运行时堆栈读取垃圾。它可能是任何东西。在不允许未对齐访问的机器上，如果字符串之后的内存不是1字节对齐，则会崩溃。如果字符串中只剩下一个字符，我们将读取两个额外的字节，因此与char数组相邻的内存对齐必须为2字节对齐。
检查每个字节的空终止：
0xBF006665
& 0x000000FF
0x00000065 != 0,
0xBF006665
& 0x0000FF00
0x00006600 != 0,
0xBF006665
& 0x00FF0000
0x00000000 == 0 !!!
所以我们返回len + 2; len是4，因为我们增加了4次，所以我们返回6，这实际上是字符串的长度。
我接受这个答案，因为它帮助我理解代码是如何工作 – Kevin
它检测是否有任何位设置在小端机上的特定字节上。由于我们只检查单个字节（因为所有半字节0或0xF都翻倍），并且它恰好是最后一个字节位置（因为机器是小端的，因此数字的字节模式是颠倒的）我们可以立即知道哪个字节包含NUL。
循环为每个迭代取4个字节的char数组。这四个if语句用于确定字符串是否结束，使用带AND运算符的位掩码读取所选子字符串的第i个元素的状态。
对于非常可疑的加速（它甚至可能更慢），它会交易未定义的行为（未对齐的访问，超过数组末尾的访问概率为75％）。并且不符合标准，因为它返回int而不是size_t。即使在平台上允许未对齐访问，它们也可能比对齐访问慢得多。
它也不适用于big-endian系统，或者如果unsigned不是32位。更不用说多重掩码和条件操作了。
这就是说：
它由加载试验在时间4的8位字节的unsigned（其甚至不保证有多于16位）。一旦任何字节包含'\0'-terminminator，它将返回当前长度加上该字节位置的总和。否则它将当前长度增加并行测试的字节数（4），并获得下一个unsigned。
我的建议：优化的坏榜样加上太多的不确定性/陷阱。很可能没能更快 - 只是轮廓它与标准版：
size_t strlen(restrict const char *s)
{
size_t l = 0;
while (*s++)
l++;
return l;
}
有可能是使用特殊的矢量指令的方式，但除非你能证明这是一个重要的功能，你应该离开这个给编译器 - 有些人可能更好地展开/加速这样的循环。
通过假设字符串被布置并且像int的数组那样尝试一次读取4个字节来代码“工作”。代码首先读取第一个int，然后依次读取每个字节，测试它是否为空字符。理论上，使用int的代码将运行得更快，然后运行4个人。
但也有问题：
对齐是一个问题：例如， *(unsigned*)s可能seg-fault。
尾数是if((x & 0xFF) == 0)的问题可能不会在地址s
s += 4得到字节是sizeof(int)有问题，可能从4
数组类型不同可能会超过int范围，更好地使用size_t。
试图解决这些困难。
#include <stddef.h>
#include <stdio.h>
static inline aligned_as_int(const char *s) {
max_align_t mat; // C11
uintptr_t i = (uintptr_t) s;
return i % sizeof mat == 0;
}
size_t strlen_my(const char *s) {
size_t len = 0;
// align
while (!aligned_as_int(s)) {
if (*s == 0) return len;
s++;
len++;
}
for (;;) {
unsigned x = *(unsigned*) s;
#if UINT_MAX >> CHAR_BIT == UCHAR_MAX
if(!(x & 0xFF) || !(x & 0xFF00)) break;
s += 2, len += 2;
#elif UINT_MAX >> CHAR_BIT*3 == UCHAR_MAX
if (!(x & 0xFF) || !(x & 0xFF00) || !(x & 0xFF0000) || !(x & 0xFF000000)) break;
s += 4, len += 4;
#elif UINT_MAX >> CHAR_BIT*7 == UCHAR_MAX
if ( !(x & 0xFF) || !(x & 0xFF00)
|| !(x & 0xFF0000) || !(x & 0xFF000000)
|| !(x & 0xFF00000000) || !(x & 0xFF0000000000)
|| !(x & 0xFF000000000000) || !(x & 0xFF00000000000000)) break;
s += 8, len += 8;
#else
#error TBD code
#endif
}
while (*s++) {
len++;
}
return len;
}
它是利用* max_align_t垫;在* aligned_as_int *的，也是我想知道，不正是* aligned_as_int * – Kevin
@Kevin不同的平台有对齐要求，例如，一些要求所有的'int'变量地址是4的倍数。在C11之前，确定这一要求并不是可能的。对于C11，'max_align_t'是一种对较大类型有要求的类型。所以代码应该逐字节地进行，直到's'处于'int'对齐地址。然后可以开始更高速度的“int”。如果所有这些努力都值得，那还是一个悬而未决的问题分析这个解决方案与'strlen（）'会回答 - 仍然依赖于平台/编译器。 – chux
即从一个不是4的倍数的地址移动四字节会导致对齐错误，但这取决于机器，是真的吗？ – Kevin
所有提案都比简单的strlen（）慢。
原因是它们不会减少比较次数，只有一次会处理对齐。
检查网络中Torbjorn Granlund（[email protected]）和Dan Sahlin（[email protected]）的strlen（）提案。如果你在64位平台上，这真的有助于加快速度。
它交易一个非常有问题的加速未定义的行为（它甚至可能更慢）。并且不符合标准，因为它返回'int'而不是'size_t' – Olaf
是的，如果int类型变得大于4字节或者机器不是little-endian，这不会引起问题吗？ –
@MillieSmith：这是最少的问题，因为大多数64位系统是I32LP64（POSIX）。问题是未对齐的访问，endianess（如你所述）。即使在平台上允许未对齐访问，它们也可能比对齐访问慢得多。更不用说多重掩码和条件操作了。 – Olaf