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程序最大的缺点吧。
责任编辑：小草
您现在的位置： 