位图法排序(编程珠玑)

问题
- 输入
- 输出
- 约束
解决思路
程序代码

问题

输入

一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出

按升序排列的输入正数的列表。

约束

最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

解决思路

应用位图或位向量表示集合。可用一个32位长的字符串来表示一个简单的非负整数，例如，可以用如下字符串表示集合{1,2,4,5,8}。

1	01101100100

32位字符串位表示：0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32位字符串位下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
数值的位都置为1，其他所有的位置为0。编程珠玑当中建议一个具有1000万个位的字符串来表示这个文件，那么这个文件的所占容量为10000000 bit= $10^7$bit，不到1MB的大小。
分三个阶段来编写程序。

第一阶段：将所有的位都置为0，从而将集合初始化为空。
第二阶段：将每个对应的位置都置为1。
第三阶段：检验每一位，如果该为为1，就输出对应的整数，有此产生有序的输出文件。（通过&运算来比较是否为1）

int数组的存储位置：位置=数据/32(采用位运算即右移5位)
int数组元素的位位置：位位置=数据%32(采用位运算即跟0X1F进行与操作)
int数组如下所示，int大小：32位，从0开始。数组中每一个元素就是一个int，所以有长度是32位。

程序代码

#include <stdio.h>

//1000w位
#define MAX 10000000   
#define SHIFT 5
//0x1F = 31
//下标从0开始，所以是31
#define MASK 0x1F 
#define DIGITS 32

//初始化数组大小
int a[1+MAX/DIGITS];

//假设n=10
//0000000000 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
//0123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

void set(int n)                                //将逻辑位置为n的二进制位置为1 
{
	//n>>SHIFT:在数组中的位置
	//n&MASK = n在字节{0，1}中的位置
	a[n>>SHIFT] |=(1<<(n&MASK));               //n>>SHIFT右移5位相当于除以32求算字节位置，n&MASK相当于对32取余即求位位置，
}                                                

//设置0，就是按位取反
void clear(int n)
{
	a[n>>SHIFT] &=(~(1<<(n&MASK)));           //将逻辑位置为n的二进制位置为0
}

//对比
int test(int n)
{
	//&，2个数字为1，则都为1
	return a[n>>SHIFT] & (1<<(n&MASK));        //测试逻辑位置为n的二进制位是否为1 
}

int main(int argc, char *argv[])
{
	int i,n;
	//清空设置为0
	for(i=1;i<=MAX;i++)
	{
		clear(i);
	}    
	 
	set(10);
	
	for(i=1;i<=MAX;i++)
	{
		if(test(i)){
			printf("%d ",i);
		}
	}
	return 0;
}