最近在看 《C 标准库》这本书啊,看到第二章如何实现 ctype.h 里的那些函数,本来我的直觉是这样实现(比如 isdigit
这个函数):
#include <stdbool.h>
bool isdigit(char c) {
if ('0' <= c && c <= '9') {
return true;
} else {
return false;
}
}
但是书上说呢,这种函数调用非常影响性能,于是要用查表法来实现,就是 维基百科 上说的这种方法。
书上用了十六进制数,按位与等等,搞得非常复杂的样子,大概跟这个链接里的实现一样: http://www.cnblogs.com/archimedes/p/c-library-ctype.html
但是这种方法我看了很久还是没有理解,有没有通俗易懂的解释呢?直觉上来说,这个东西的实现本来应该非常简单的啊
补充一下,我就是那个查表法是怎么查的没有理解,比如为什么要用 16 进制,为什么要用 &
运算等等,总之就是不知道它是怎么查出来的。
一个函数的调用开销抵得上上千个CPU指令周期
!!
我们写普通应用时应该以可读性为主,仅在必要的时候才进行性能优化。但这种非常low-level
的代码必须严格对待效率问题。所以这个问题用宏来实现是最好的方式。
相比if语句,用宏+查表法实现可能第一次执行会比if语句慢,因为要把整张表加载到高速缓存,但之后的每一次调用都将比if语句快,更比函数方式快N倍。
补充回答
首先,“查表查表”,指的是什么样的一张表呢?是这么一张表:
static const short ctype_tab[257] = { 0, /* EOF */
_BB, _BB, _BB, _BB, _BB, _BB, _BB, _BB,
_BB, _CN, _CN, _CN, _CN, _CN, _BB, _BB,
_BB, _BB, _BB, _BB, _BB, _BB, _BB, _BB,
_BB, _BB, _BB, _BB, _BB, _BB, _BB, _BB,
_SP, _PU, _PU, _PU, _PU, _PU, _PU, _PU,
_PU, _PU, _PU, _PU, _PU, _PU, _PU, _PU,
XDI, XDI, XDI, XDI, XDI, XDI, XDI, XDI,
XDI, XDI, _PU, _PU, _PU, _PU, _PU, _PU,
_PU, XUP, XUP, XUP, XUP, XUP, XUP, _UP,
_UP, _UP, _UP, _UP, _UP, _UP, _UP, _UP,
_UP, _UP, _UP, _UP, _UP, _UP, _UP, _UP,
_UP, _UP, _UP, _PU, _PU, _PU, _PU, _PU,
_PU, XLO, XLO, XLO, XLO, XLO, XLO, _LO,
_LO, _LO, _LO, _LO, _LO, _LO, _LO, _LO,
_LO, _LO, _LO, _LO, _LO, _LO, _LO, _LO,
_LO, _LO, _LO, _PU, _PU, _PU, _PU, _BB,
};
此数组长度257
,实际只初始化了前面129
个元素。但是实际用来判断的_Ctype
是截取了该数组的后面256
个元素:
const short *_Ctype = &ctype_tab[1];
忽略掉那个EOF
的0
,注意看上面的128
个元素。这实际上是对整个ASCII
表进行了归类。比如_LO
表示小写字母,_UP
表示大写字母,_DI
表示数字,这些宏常量都已经在前面定义了的。注意对于数字,他并不是用的_DI
,而是XDI
,这代表这些数字同时代表十进制数字+十六进制数字
,同理,字母中的A-F
和a-f
也不是_UP或_LO
而是XUP和XLO
,表示它们即是字母又是十六进制数字。
这样分类之后,它又是怎么判断一个字符的属性的呢?主要的技巧是每个类别的常量之间是互斥的
,把它们的值转成二进制以后,每个常量的1
的位置是不同的。例如_LO
的值是0x10
,二进制是1 0000
,1
在右数第五位,而其他的几个常量中的1
全部与它不同,不信你可以自己验证一下(几个组合常量除外)。
实际上,它是从_XD
(代表十六进制数字的常量)到_XA
(代表编码超过128的那些ASCII超集字符
),每个常量都是前一个的2
倍。2
倍在二进制中相当于把1
向左挪动了一位,这样每一个常量中的1
就错开了。
这种技巧在编程中有一个专门的名字:掩码
,英文名字是Mask
,它除了可以判断一个值是不是某个我期望的值之外,还能很容易地进行组合判断。比如g
是小写字母,而a
不仅是小写字母,还是一个十六进制数字。
判断的时候,只要把实际值与预先定义的掩码
进行与操作
,然后判断结果是否不为0
即可。
例如,你拿到一个小写字母g
,它在该表中对应的值是_LO
即0x10
,二进制为1 0000
,(请自行对照着ASCII码表
来看),此时把它与_LO
相与,即10000 & 10000
,由于第五位都是1
,所以结果不为0
,表示它是一个小写字母。
如果你拿到的不是一个小写字母,例如是大写字母G
,它在该表中对应的值是_UP
即0x02
(二进制10
),此时把它与_LO
相与,即10 & 10000
,结果为0
,表示它不是一个小写字母。其他同理。
如果你拿到一个具有组合属性
的字符,例如a
,它在表中对应的值是XLO
,这是一个由_XD
和_LO
进行或操作
得到的组合值,即10 | 10000
,得到的结果为10010
,也就是十六进制的0x12
。多个掩码之间进行或操作
就相当于为它们赋予了多重属性,因为它们的二进制上有多个位置同时为1
,这样它们就可以在多种判断中返回不为0
的结果。以a
为例,它与_LO
进行与操作
时结果不为0
,表示它是一个小写字母,同时它与_XD
进行与操作
时结果也不为0
,因此它也是一个十六进制数字。
基本原理就是这样。掩码其实很常见,比如对IP地址的网段的判断(子网掩码)、Windows的GDI编程中为画刷设置属性、某些系统中对角色权限的判断,等等。
最后,对于你的为什么要使用十六进制来定义
的疑惑,实际上是为了清晰,一看就知道这些定义的是掩码。如果用二进制则太长,用十进制则不够直观(别忘了我们是程序员,天生对十六进制更加敏感)。