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

!本文可能 超过1年没有更新,今后内容也许不会被维护或者支持,部分内容可能具有时效性,涉及技术细节或者软件使用方面,本人不保证相应的兼容和可操作性。

原文发表于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下编译通过。

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

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

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

若无特别说明,本网站文章均为原创,原则上这些文章不允许转载,但是如果阁下是出于研究学习目的可以转载到阁下的个人博客或者主页,转载遵循创作共同性“署名-非商业性使用-相同方式共享”原则,请转载时注明作者出处谢绝商业性、非署名、采集站、垃圾站或者纯粹为了流量的转载。谢谢合作!
请稍后...

发表评论

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

*