C-查找第一个不在指定字符串中出现的字符 strspn实现

Question

 ;***
 ;int strspn(string, control) - find init substring of control chars
 ;
 ;Purpose:
 ;       Finds the index of the first character in string that does belong
 ;       to the set of characters specified by control.  This is
 ;       equivalent to the length of the initial substring of string that
 ;       consists entirely of characters from control.  The '' character
 ;       that terminates control is not considered in the matching process.
 ;
 ;       Algorithm:
 ;       int
 ;       strspn (string, control)
 ;               unsigned char *string, *control;
 ;       {
 ;               unsigned char map[32];
 ;               int count;
 ;
 ;               for (count = 0; count < 32; count++)
 ;                       map[count] = 0;
 ;               while (*control)
 ;               {
 ;                       map[*control >> 3] |= (1 << (*control & 7));
 ;                       control++;
 ;               }
 ;               if (*string)
 ;               {
 ;                       while (map[*string >> 3] & (1 << (*string & 7)))
 ;                       {
 ;                               count++;
 ;                               string++;
 ;                       }
 ;                       return(count);
 ;               }
 ;               return(0);
 ;       }
 ;
 ;Entry:
 ;       char *string - string to search
 ;       char *control - string containing characters not to search for
 ;
 ;Exit:
 ;       returns index of first char in string not in control
 ;
 ;Uses:
 ;
 ;Exceptions:
 ;
 ;*******************************************************************************

Answer 1

该算法的巧妙之处是位图map的设计和使用。
字符的类型是char，而char需要用一个字节即8位来表示。char能表示的不同字符总数目为256个。
要查找出s1中第一个不在s2中的字符，采取如下方法比较快速而且节省空间：
建立一个位图，记录字符串s2中出现了哪些字符，出现的标记1，否则标记0。这样每一个标记位只需一个bite空间。这样总共需要空间256bites。然后搜索字符串s1，对比位图，搜索到第一个在位图中标记位是0的即为所需要的字符。因此定义位图如下：

unsigned char map[32];

一个char提供8个标记位，32个元素的char型数组提供256个标记位。每位映射到一个ASCII码。每个ASCII码（设为c）有8位，把它分为2部分，低3位构成下标j（通过c & 7得到），用来搜寻其标记为在数组位图中一个元素中的索引，下标j就是在map[i]中的第j位。而高5位构成下标i（通过c>>3得到），用来搜寻其标记位在位图数组的哪个元素中。

例如，对于字符‘1’，其ASCII码是0x31，>>3得6，&7得1，也就是它在map[6]的第1位，通过1 <<1得1，然后与map[6]相与。