文章仅供参考

今天单位要求计票，近100个人，几千张选票，每张选票上有1~12人不等，选票内容有两大类，一类分为同意和不同意，一类分为优秀、称职、比较称职和不称职这几个选项，要求分别算出这些人两大类的选票数。

杯具的是，原始的选票，木有计算机啊，再NB的程序也派不上用场了，只有手工计票了，和同事讨论的几种计票方法，同事给出的意见是：先选择选票上第一个人，然后分别筛出得票最多的选项，比如说，这一堆选票，每张有张三、李四和王五三个人，首先选择张三，大概看了一下，发现张三得同意和优秀的票最多，我们把这些票筛选出来，然后统计不是这两个选项的票，这里只能采用笨方法，依次遍历两大类的各选项。这样发现计票确实容易了一些，因为大多数票已经被筛出了，然后数一下筛出的票数，再合计就得出了张三的所有选项的票数。

下午，同事有事外出，我单独找了一间大的会议室，然后准备计票，突然想到计算机上典型的以空间换时间的算法，也就是说时间快效率高，多数是以牺牲空间为代价的，典型的就是缓存，我们将经常会访问的数据存放在缓存里，这样可以避免多次查询数据库所带来的性能开销，访问的速度就会变快，而这个速度是要牺牲内存或者硬盘空间的；相反，如果空间小，更多地是要消耗性能，导致速度瓶颈的。

那么我又研究了一下刚才同事提出的思路，然后实际计了一组选票，得出以下结论：

1. 全部选择同意和优秀的比较多排第一，这类人多数对投票不感兴趣、不敢得罪人或者是不认识被选举人。

2. 全部选择同意和称职的人数排第二，这类人多数具备有第一条所述的特点，同时思想略有保守，对优秀比较感冒，或者本人要求比较严格，无论看什么都是有缺点的。

3. 全部选择不同意和称职的人数居第三，这类人多数原则上不想被选举人当选，既然不想被选举人当选，那么“优秀”就无从谈起，接下来就是“称职”、“比较称职”和“不称职”三种说法，既然选择不同意，可能觉得被选举人缺乏职务升迁的某种能力，但是对于其工作还是认可的，所以选择称职。

继续阅读 →

编译原理及编译器那个栏目一直空着，网站改版前是有一些文章的，改版后觉得价值不高就没有放上来，想先完成基础数据结构的函数库，可能学艺不深，一些简单的数据结构函数总是要改上很多次，本来是想从基础数据结构构建，直到一些复杂数据结构及算法的实现。事实上，问题开始逐渐凸显出来，作为一些简单的基础的数据结构，实现起来很容易，调用起来也很方便，没有什么问题，对于构筑于这些简单的数据结构上的复杂数据结构及算法貌似也实现了设想的功能，似乎这样没有问题，直到有一天我在做WEB数据库操作时想到：复杂数据及算法操作总是分成若干个操作简单数据结构的步骤，如果说这些若干步骤中，第N步出错，错误可以是内存读写失败或者权限等问题，那么对于第N步的致命错误，一般是直接返回，那么第N+1步是不会执行了，问题就在于第N-1步，如果第N-1步对原有数据造成了破坏，那么有没有类似于关系型数据库的事物恢复机制呢？如果说没有这种机制，那么在调用这个函数导致失败是小事，破坏了原有的数据就麻烦了。

可能最简单的做法就是在操作数据前对数据做一个拷贝，一旦失败并导致原有数据被破坏，则立即利用拷贝恢复被破坏的数据。数据量小的情况下这种方法确实简单方便，但是在应用复杂，数据量大的情况下，必然会导致存储空间和性能瓶颈，准备有时间好好研究一下数据库的原子操作的实现，一个可靠的数据算法函数库必须要有灾难恢复机制，否则就违背了函数设计的初衷了，即输入数据，得出正确结果，或者执行可以失败，但不能破坏了原有的数据。

原创文章，未经允许，请勿转载！

关系型数据库一般都是以平面方式来存储我们的数据，这就造成了我们在实现一些数据结构上的麻烦，比如说如何实现高效的无限级的网站分类，这里MySQL的《Managing Hierarchical Data in MySQL》给出了一个比较好的办法，基于一种左右值的算法，这也是我目前接触到的查询比较高效的算法了，另外Gijs Van Tulder在sitepoint也写过一篇《Storing Hierarchical Data in a Database》文章专门讲解这个算法，我在这里再总结一下，首先看下面的这张图：

通过这张图大家应该能很清晰的看出对于一种简单的树形结构分类的左右值处理的方式，这是一种类似于树的深度优先的遍历，其次这些左右权值很清晰的表明了一种隶属的包含关系，比如Fruit的左右值分别为1~6，那么说，所有在这个之间的值都是其子节点(Child Node)。对于数据库的遍历，我们可以很轻松的指定一个范围，然后执行一条SELECT查询语句。

继续阅读 →

原文发表于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的倍数。

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