问题： 给10^7 个 不重复的整数， 排序

位图实现：

基本思路： 使用一位来表示一个数 例如集合 {1， 3， 5， 8}， 可以用 位图 {10101001} 来表示。即对应位置为1 如下图所示.

关键操作有： 1） 找到数据所对应的字节位置 2）找到数据对应的字节中位位置 3） 判断某位为1， 置某位为1 etc

方法：

1） 找到 对应字节位置: 如果系统是32 位的话 相当于将 数据/32, 使用位操作 数据 >> 5

2) 找到对应字节的位位置: 如果系统是32位的话 相当于将 数据%32, 使用位操作 数据 &0x1F

3）数字 a 的 第i位 是1： 方法 a & (1 << i) ，将数据a的第 i位 置1 a | (1 << i)

具体步骤：

#define MAX 5000000
#define SHIFT 5
#define MASK 0x1F
#define DIGITS 32

int bitmap[1 + MAX/DIGITS];

// 先找到数据n 所在位置bitmap[n >> SHIFT]
// 然后将这个整数的 所对应的数据n的位置 置1； (n & MASK) 是找到对应为位位置； 与运算 置1
void set(int n)
{
bitmap[n >> SHIFT] = bitmap[n >> SHIFT] | (1 << (n & MASK));
}

// 置0 采用 & 运算
void clear(int n)
{
bitmap[n >> SHIFT] = bitmap[n >> SHIFT] & (~ 1 << (n & MASK));
}

//采用 & 运算
void test(int n)
{
return bitmap[n >> SHIFT] & (1 << (n & MASK));
}

int main()

{

for(int i = 1; i <= MAX; i++)
{
clear(i);
}

// open data file with unsorted data
FILE *fp_unsort_file = fopen("data.txt", "r");
assert(fp_unsort_file);
FILE* fp_sort_file = fopen("sortByC.txt", "w");
assert(fp_sort_file);

int n;
while(fscanf(fp_unsort_file, "%d ", &n) != EOF)
{
set(n%MAX);
}

for(int i = 1; i <= MAX; i++)
{
if(test(i))
{
fprintf(fp_sort_file, "%d ", i);
}
}

if(fp_unsort_file != NULL)
{
fclose(fp_unsort_file);
}
if(fp_sort_file != NULL)
{
fclose(fp_sort_file);
}

}

另外C++ 实现了bitmap 也可以直接用

C++ 标准的STL

将C语言梳理一下，分布在以下10个章节中：