#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define MAX_NUM 16777216//最大的數,也就是需要的位
#define BYTE_NUM (1+MAX_NUM/8)//字節數
#define MASK 0x07

void setAllZero(unsigned char *p,long size);
void setOne(unsigned char *p,long loc);
int find(unsigned char *p,long loc);
bool getSorted(unsigned char *bitmap,char *fileName);
bool setBitmap(unsigned char *bitmap,char *fileName);
int bitmapSort();
int main(){
    return bitmapSort();
}
int bitmapSort(){
    unsigned char *bitmap;    //位圖指針
    bitmap = (unsigned char *)malloc(BYTE_NUM*sizeof(unsigned char));
    if(bitmap == NULL){
        printf("Malloc failed/n");
        return -1;
    }   
    setAllZero(bitmap,BYTE_NUM);//將位圖所有位設置為0
    setBitmap(bitmap,"phoneNumber.txt");//掃描待排文件，將位圖對應位設置為1
    getSorted(bitmap,"bitmapSort.txt");    //掃描位圖，將位圖為1的位號輸出到文件
    free(bitmap);//釋放位圖
    return 0;
}
/***********設置待排序數據的位圖**************/
bool setBitmap(unsigned char *bitmap,char *fileName){
    FILE *readFp;
    printf("Setting bitmap.../n");
    readFp = fopen(fileName,"r");
    if(readFp == NULL)
        return false;   
    long phoneNum=0;
    while(fscanf(readFp,"%ld/n",&phoneNum) != EOF){
        setOne(bitmap,phoneNum);//將    phoneNum位設置為1   
    }
    fclose(readFp);
    return true;
}
/*****順序遍歷位圖輸出記錄，從而實現排序****************/
bool getSorted(unsigned char *bitmap,char *fileName){
    printf("Search bitmap.../n");
    FILE *writeFp;
    writeFp = fopen(fileName,"w");
    if(writeFp == NULL)
        return false;
    long phoneNum=0;
    for(phoneNum = 0; phoneNum < MAX_NUM; phoneNum += 1){
        if(find(bitmap,phoneNum)){
            fprintf(writeFp,"%ld/n",phoneNum);
        }
    }
    fclose(writeFp);
    return true;
}
/******先將位圖清零********/
void setAllZero(unsigned char *bitmap,long size){
    for(long i=0;i<size;i++)
        *(bitmap+i) &= 0;
}
/*************************************************
將指定的位置為1
(loc>>3)相當于整除2^3=8，即定位到字節數，MASK=0x07,loc&MASK相當于loc%8
***************************************************/
void setOne(unsigned char *bitmap,long loc){
    *(bitmap+(loc>>3)) |= (1<<(loc&MASK));//
}

/******查找指定的位是否為1********/
int find(unsigned char *bitmap,long loc){
    return ((*(bitmap+(loc>>3))) & (1<<(loc&MASK))) == (1<<(loc&MASK));   
}
 

 #include <bitset>
#define MAX_NUM 4000000//最多的數，即需要的位數
using namespace std;

int main(){
    FILE *readFp,*writeFp;
    readFp = fopen("phoneNumber1.txt","r");       
    writeFp = fopen("bitsetSorted.txt","w");   
    bitset<MAX_NUM> bitmap;
    for(long i=0;i<MAX_NUM;i++){//先將位圖初試化為0
        bitmap.set(i,0);
    }
    printf("Begin set bitmap.../n");
    long number = 0;
    while(fscanf(readFp,"%ld/n",&number) != EOF){
        bitmap.set(number,1);//將number所在位設置為1       
    }
    printf("Begin search bitmap.../n");
    for(long i=0;i<MAX_NUM;i++){
        if(bitmap[i] == 1)//將位1的位輸出到已排序文件
            fprintf(writeFp,"%ld/n",number);
    }
    fclose(writeFp);
    fclose(readFp);
}