编程中通过二进制状态位存储信息

原文发表于2009年3月7日

今天解皞同学询问了一道编程题，要求是用表驱动法也就是查表的办法解决，题目（部分）如下：

映射关系如下：
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9
Q和Z没有映射到任何数字。

可能最近一个链表的项目做晕头了，我的第一反应竟然是链表，后来想了下，这个应该使用普通数组的表结构会比较合理，我给出的建表方案如下：

映射关系是连续的，假设没有映射是1，那么映射关系应该是1-9这九个数字，化为数组下标应该是0-8。然后知道这是个一对多的关系，首先0对Q和Z、1对A、B和C……假设数组就是0~8的。

如何才能将一个数组下标对应的空间包含相应的多个联系呢？

我们可以通过状态位来判断，这里需要用到点位运算的知识。

设二元序列如下：
<0000 0001, A>
<0000 0010, B>
<0000 0100, C>
<0000 1000, D>
<0001 0000, E>
<0010 0000, F>
<0100 0000, G>
（省略若干）

大家应该能看出什么规律了，二进制的一位代表一个状态位，那么我们可以通过这些状态位索引字母A-Z。

那么一个无符号长整型（unsigned long）即可包含全部大写字母表的信息，比如包含A、B和C的信息，只要将A、B和C的二进制状态位按位或即可。

因此可以得到一张编码表：
<0x2010000> <Q, Z>
<0x0000007> <A, B, C>
<0x0000038> <D, E, F>
<0x00001c0> <G, H, I>
<0x0000e00> <J, K, L>
<0x0007000> <M, N, O>
<0x0068000> <P, R, S>
<0x0380000> <T, U, V>
<0x1c00000> <W, X, Y>

然后可以通过查这张表，然后用检测某位的方式判断映射关系，检测某位只需要按位与判断结果是否为0即可。

下面给出源代码：

#include <stdio.h> 
 
int main(void) {
 
  unsigned long letter_table[9] = 
    {0x2010000, 0x0000007, 0x0000038, 0x00001c0,
     0x0000e00, 0x0007000, 0x0068000, 0x0380000,  0x1c00000};
 
  int get_letter, i;
 
  puts("Enter letter [A-Z] ?");
  get_letter = getchar();
 
  if(get_letter < 0x41 || get_letter > 0x5a) {
    fprintf(stderr, "Error letter must A-Z");
    return 1;              
  }
 
  for(i = 0; i < 9; i++) {
    if((((unsigned long)(0x1 << (get_letter - 0x41))) &
      letter_table[i]) != 0) {
      if(i != 0)
        printf("found it!  @ %c = %d\n", get_letter, i + 1);
      else 
        printf("letter %c without number.\n", get_letter);
      break;              
    }      
  }
 
  return 0;    
}

以上源代码在Dev-CPP GCC下编译通过。

当然不见得这个就是效率很高的，我只是想通过这篇文章给大家编程时拓宽思路，比如位状态变化就是一个比较好的存储信息的方式。

如果想要查表效率很高，我觉得可以根据用户的具体输入，经过简单数学运算可以得到离结果最近的查表起始点，然后查找。

如果对于位操作比较感兴趣的可以参考我的前面的《简单介绍编程中位运算的使用》。