开发者社区> 问答> 正文

c 语言里 ctype.h 实现的问题

a123456678 2016-06-08 21:15:58 1057

最近在看 《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 进制,为什么要用 & 运算等等,总之就是不知道它是怎么查出来的。

分享到
取消 提交回答
全部回答(1)
  • a123456678
    2019-07-17 19:32:46

    一个函数的调用开销抵得上上千个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编程中为画刷设置属性、某些系统中对角色权限的判断,等等。

    最后,对于你的为什么要使用十六进制来定义的疑惑,实际上是为了清晰,一看就知道这些定义的是掩码。如果用二进制则太长,用十进制则不够直观(别忘了我们是程序员,天生对十六进制更加敏感)。

    0 0

集结各类场景实战经验,助你开发运维畅行无忧

推荐文章
相似问题