正文

编程珠矶学习笔记(1)--位排序2009-10-12 22:55:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ljqy/49181.html

分享到:

个人原创,转载请注明出处,谢谢!

一、代码
#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

 

阅读(3283) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册