快速的4个字符的字符串比较

偶然看到的一个非常巧妙的算法:

#define COMPARE_4CHAR(p,a,b,c,d) \
( ( (*(int*)p) | 0x20202020) == (a | (b<<8) | (c<<16) | (d<<24))

很简短的一行宏定义代码,你能看出它的功能吗?
从宏的名称能看出来,是比较字符串的。p是一个字符串指针,a、b、c、d是四个字符。等号的右边,将4个字符(也就是四个字节)按先后顺序的倒序排列成一个4字节串,等号的右边是将字符串指针p指向的内存的前4个字节转换为一个int型整数,再与0×20202020做“或操作”。这个宏的值,就取决于等号左右两端是否相等,相等,则为TRUE,不相等,则为FALSE。
右边好理解,在小头序(little endian)的CPU上,字节序是与阅读序相反的,也就是说内存中从低到高的0xaa,0xbb,0xcc,0xdd四个字节表示的数值是0xddccbbaa。所以,内存中连续存储的a、b、c、d4个字节转换成一个4字节的int型整数的值就是(a | (b<<8) | (c<<16) | (d<<24))。
再看左边,(*(int*)p)也不难理解,就是将指针指向的内存前4个字节转换成int型整数,这样,跟等号右边的数值相比较,如果相同,就是说明p指向的字符串和abcd这4个字节组成的字符串相同的字符串。
但是,那个古怪的0×20202020又是什么用意呢?相当于每个字节要或上一个二进制的00100000,这样,无论每个字符的第6个比特是0还是1,不应影响该宏的比较结果…
真是着实耗费我若干脑细胞才琢磨出来。
从A到Z这26个大写英文字符的ascii码是64到90,小写英文字符a到z的ascii码是97到122,二进制的00100000实际就是32,实际就是小写字符和对应的大写字符的差。原来如此,无论p指示的字符串中的字符时小写还是大写,或上一个二进制的00100000,就都变成小写的了,然后再与abcd比较,这样,就可以忽略p字符串的大小写了。
所以,这个宏的功能是判断一个四字符的字符串是否为指定的字符串,字符串必须是英文字母,大小写无关。
用法是:p为4字节字符串指针,abcd分别为小写英文字符。
使用举例:
if (COMPARE_4CHAR(“AdrM”,’a',’d',’r',’m'))
printf(“yes! it is adrm”);

这真是一个很巧妙的英文字符比较方法,不知道人家是怎么琢磨出来这么牛的想法的。要是一般人来写,肯定是循环读字符串的每个字节,逐字节判断是否小写,不是就转化成小写,再逐字比较是否相等。两相比较,真是一个人间,一个天上。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>