个人原创，转载请注明出处，谢谢！
一、代码
#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
评论