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

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

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

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

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

简单介绍编程中位运算的使用

原文发表于2008年11月22日

在我刚刚接触C语言时,对于10进制转2进制这种数学运算很是反感,记得某次实验课上老师要求写一段10进制转换为2进制的C语言程序,我竟然忙活了半天没有搞定,本来以为很简单的,不就是除以二判断余数吗?但偏偏弄不好,后来接触到数据结构课知道每次余数判断需要将结果进栈,然后输出结果时出栈即可,代码后来自己搞定了。后来上过汇编课后了解了位运算。于是我写了如下代码,对,这就是进制转换,很简单。当然,如果你有更好的欢迎共同交流。

#include <stdio.h>   
int main(void)   
{ 
    int usr_input;   
    short i;   
    puts("Enter a number:");   
    scanf("%d", &usr_input);   
    for(i = ((sizeof(usr_input) << 3) - 1);
	i > -1; i--)   
    {   
        printf("%d", ((usr_input &
		     (0x1 << i)) == 0 ?
				0 : 1));   
        if((i & 3) == 0)   
            putchar(' ');    /* 这个if也可以省掉 */  
    }   
    putchar('\n');   
    return 0;   
}

位操作的魅力就在这里,代码简洁,当然最重要的一点还是位操作的效率比较高。缺点就是代码不易理解,不过我认为你对二进制位有深刻了解并且经常写一些位操作的代码的话这些代码你也会很容易理解的。

下面解释下这段进制转换的代码。

((sizeof(usr_input) << 3) – 1) 获取数据的位数,这里是int型,sizeof后为4,左移3位,左移1位即乘以2,这里即乘以8,结果是32,也就是说int型为32位(注:不同的机器可能sizeof的值是不同的,这里仅仅以Intel x86机型为例)。一般情况下二进制我们从右向左读,第1位也就是我们这里说的第0位,那么输出这个二进制,需要先输出最高的一位,也就是输出第31位。怎么判断这一位呢?这是我们下面要做的工作,学过汇编的知道,使用TEST指令即可判断位,而TEST指令做的是不写原值的按位与操作,所以要判断哪一位我们需要将那一位与1与,其余位与0与即可,比如这里的判断需要与的是1000 0000 0000 0000 0000 0000 0000 0000,如果结果是0,说明这一位是0,反之若不为0则这一位为1。但如何实现判断下一位和下下位的循环判断呢?其实我们可以设定一个初始值0000 0000 0000 0000 0000 0000 0000 0001即0x1,让其随循环次数进行左移即可。i & 3 其实这句是 i % 4,主要是为了美观,每四位输出空格。求余(模)一般对于求的是2的倍数的余数都可以用类似的按位与实现。

这段代码理解后可以看看下面的代码:

/* 转化为大写 */  
char *UCase(char *Source)   
{   
 long i=0;   
 do  
  if(*(Source+i) <= 'z' &&
	*(Source+i) >= 'a')   
   *(Source+i) &= 223; /* 将二进制第六位置为0 */  
 while(*(Source+i++));   
  return Source;   
}   
 
/* 转化为小写 */  
char *LCase(char *Source)   
{   
 long i=0;   
 do  
  if(*(Source+i) <= 'Z' &&
	*(Source+i) >= 'A')   
   *(Source+i) |= 32; /* 将二进制第六位置为1 */  
 while(*(Source+i++));   
  return Source;   
}

这段代码应该是比较好理解的,其实你只要用心观察过ASCII码表,分析其二进制后你就会发现一定的规律,然后也可以像上面的代码一样轻松的用位操作实现常用的功能。

如果我要让你写一段判断奇偶数的代码呢?很多人肯定认为,这还不简单,直接与2求余即可,学过汇编后,我才知道有比这个还方便的位操作方法,即直接判断最后一位是否为1,为1即为奇数,反之为偶数。怎么判断呢,上面说过了,用按位与即可,对0x1按位与。你会发现和刚才提到的求余的位操作简化有着相同之处,即模2。

再介绍个我较早接触的位操作,即交换两个整形变量。老师在授课时绝大多会和你讲,交换两个数需要临时变量什么的,然后要你写一个swap函数,其实在书上位操作那章介绍了一个不需要临时变量的整形交换方法。即异或。下次老师再要求你写交换两个整形的函数你就可以这样去写:

void swap(int *a, int *b)   
{   
    *a ^= *b;   
    *b ^= *a;   
    *a ^= *b;   
}

不相信吗?自己调试看看。这段代码类似与使用位运算的简单应用实现的密钥加密解密的功能。

下面提供一些,我写的用来操作位的宏:

#define BIT_TEST(src, pos) \
	((((src) & (0x1 << (pos))) == 0) ? 0 : 1)   
#define BIT_SET(src, pos) \
	((src) | (0x1 << (pos)))   
#define BIT_CLEAR(src, pos) \
	((src) & (~(0x1 << (pos))))   
#define BIT_TURN(src, pos) \
	((src) ^ (0x1 << (pos)))   
#define BIT_SIZE(type)     \
	(sizeof((type)) << 3)   
#define BIT_MOD(src0, src1) \
	((src0) & ((src1) - 1)) /* src1 must be 2*n */

解释:

BIT_TEST 输出src的pos位是0还是1。
BIT_SET 设置src的pos位为1。
BIT_CLEAR 设置src的pos位为0。
BIT_TURN 翻转src的pos位,即0变成1,1变成0。
BIT_SIZE 输出type型的位数。
BIT_MOD 求余(模),即将src0 % src1,特别提醒的是src1必须是2的倍数。

最后,我想说的是,这里提到的位操作均适用于整形数,最好不要尝试在浮点型上应用,以避免意想不到的后果。