个人原创，转载请注明出处，谢谢！ 一、代码#include <stdio.h> #define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; inline void set_bit(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } inline void clear_bit(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } inline int test_bit(int i) { return a[i>>SHIFT] & (1<<(i & MASK)); } int main() { int i; for (i = 0; i < N; i++) { clear_bit(i); } while (scanf("%d", &i) != EOF) set_bit(i); for (i = 0; i < N; i++) { if (test_bit(i)) { printf("%d\n", i); } } return 0; } 二、代码注解#include <stdio.h> /*每WORDR 的位数，这里用的是int型4字节32位*/ #define BITSPERWORD 32 /*这里是每个int型的偏移量， 2的5次方是32，即1左移5位是32*/ #define SHIFT 5 /*十六进制1F,用于作掩码来计算n在某一word中位于 第几位。如计算i & MASK 等价于i %32 ，但位操作性能会更高一些*/ #define MASK 0x1F #define N 10000000 /*N/BITSPERWORD为N位需要多少个WORD，加1是向上取整, 即宁可多几位也不能少1位*/ /*分配静态数组用于保存各数据位*/ int a[1 + N/BITSPERWORD]; /* *用于设置第i 位 */ inline void set_bit(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); /* *首先需要知道i会落在第几个word中即a[i >> SHIFT] *其次需要知道i在该word中应该在哪一位即 (1<<(i&MASK)) *最后使用|运算完成置位。 *例子：假设i=100，则i 在a[100 >> 5] = a[3], (1 << (100 & 31)) = (1<<4) * a[3] |= (1 << 4),则置上了a[3]的第四位 * 100= a[0 ] *32 + a[1] *32 + a[2] * 32 + a[3]的4位,这样当我们发现a[3]的 * 的第4位被置时，我们就可以知道100这个数存在 */ } /* *清位是置位的逆运算，与置位类似找到i所在的WORD，然后再 *找到其在该WORD中的位,与set相反的是它将该位取反为0，然后 * 进行与操作 */ inline void clear_bit(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } /* *测试i位是否被置位，即找到第i位然后看该位是否为1 *找位的过程和上面相同，然后令该位和1进行与操作 *如果为0则没有置位，如果不为0则该位被置 */ inline int test_bit(int i) { return a[i>>SHIFT] & (1<<(i & MASK)); } int main() { int i; /*初始化数组，清除所有位使用memset效率会更高一些*/ for (i = 0; i < N; i++) { clear_bit(i); } /*使用文件等输入方式，输入所有的整数*/ while (scanf("%d", &i) != EOF) set_bit(i);/*置每一个整数*/ /*打印出所有存在的整数*/ for (i = 0; i < N; i++) { if (test_bit(i)) { /*只要该位被置说明该整数存在*/ printf("%d\n", i); } } return 0; } 三、应用举个简单的例子，如果我们有一组乱序的整数存在文件 file-data.tmp中，我们希望对其进行排序： 100 4 98 34 56 234 假设上面的程序编译后的可执行文件为 bit-sort，那么在Linux操作系统中，我们可以使用如下的方式对文件内的乱序整数进行排序： % cat file-data.tmp | bit-sort 输出结果为： 4 34 56 98 100 234
评论