1//位图排序法，时空高效的至高境界
　　2#include <cstdio>
　　3
　　4#define BITSPERWORD 32
　　5#define SHIFT 5
　　6#define MASK 0x1F
　　7#define N 10000000
　　8int a[1 + N/BITSPERWORD];
　　9
　　10void set(int i){
　　11 a[i >> SHIFT] |= (1<<(i & MASK));
　　12}
　　13
　　14void clr(int i){
　　15 a[i >> SHIFT] &= ~(1<<(i & MASK));
　　16}
　　17
　　18int test(int i){
　　19 return a[i >> SHIFT] & (1<<(i & MASK));
　　20}
　　21
　　22int main(void) {
　　23 int i;
　　24 for (i = 0; i < N; i++) {
　　25 clr(i);
　　26 }
　　27 //while (scanf(\"%d\", &i) != EOF) {
　　28 // set(i);
　　29 //}
　　30 for (int j = 0; j < 3; j++) { //供简单的正确性测试
　　31 scanf(\"%d\", &i); //注意，输入的数不能重复
　　32 set(i); //否则当只输入一次
　　33 }
　　34 for (i = 0; i < N; i++) {
　　35 if (test(i))
　　36 printf(\"%d\\n\", i);
　　37 }
　　38 return 0;
　　39}
　　为什么说这个算法时空效率达到及致呢？我们对１００万个不重复的正整数（１００００００以内）的文件进行测试：　　

	系统排序	C++/STL.set	C/qsort	C/位图
总时间(s)	89	38	12.6	10.7
计算时间(s)	79	28	2.4	0.5
内存使用(MB)	0.8	70	4	1.25

　　（本测试数据是在较旧的电脑上测试的，但还是体现性能的差距）
　　第一行是总时间，第二行的计算时间是总时间减去数据读取耗时１０.２秒。虽然通用C++程序使用内存和ＣＰＵ时间是专用Ｃ程序（C/位图）的５０倍，但是它的使用仅需要一半的代码，并能很容易扩展到其他问题上，这也是专用C程序最大的缺点吧。

3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.net/exam/