相關數據結構

typedef uint64_t BitmapType;#define BITMAPMAXSIZE 1000 //位圖所能容納的位數typedef struct Bitmap
{uint64_t* data;uint64_t capacity;
}Bitmap;

初始化

void BitmapInit(Bitmap* bm, uint64_t capacity)
{if(bm == NULL){return;}//當capacity = 100, 2個元素//當capacity = 200, 4個元素//當capacity = 300, 5個元素//當capacity = N, capacity / 64 + 1   => capacity / (sizeof(uint64_t) * 8) + 1bm -> capacity = capacity;  uint64_t size = capacity / (sizeof(uint64_t) * 8) + 1;//位圖對應的數組有幾個元素bm -> data = (BitmapType*)malloc(sizeof(BitmapType) * size);
}

銷毀

void BitmapDestroy(Bitmap* bm)
{if(bm == NULL){return;}bm -> capacity = 0;free(bm -> data);bm -> data = NULL;
}

將某一位設置為1

void GetOffset(uint64_t index, uint64_t* offset, uint64_t* n)
{if(offset == NULL || n == NULL){return ;}*n = index / (sizeof(BitmapType) * 8);*offset = index % (sizeof(BitmapType) * 8) ;
}void BitmapSet(Bitmap* bm, uint64_t index)
{if(bm == NULL || index >= bm -> capacity){return;}uint64_t n, offset;GetOffset(index, &n, &offset);bm -> data[n] |= (0x1lu << offset);
}

將某一位設置為0

void BitmapUnSet(Bitmap* bm, uint64_t index)
{if(bm == NULL || index >= bm -> capacity){return;}uint64_t offset, n;GetOffset(index, &n, &offset);bm -> data[n] &= ~(0x1lu << offset);
}

檢測某一位是0還是1

int BitmapTest(Bitmap* bm, uint64_t index)
{if(bm == NULL){return 0;}uint64_t n, offset;GetOffset(index, &n, &offset);uint64_t ret = bm -> data[n] & (0x1lu << offset);if(ret == 0){return 0;}return 1;
}

將位圖每一位都設置為1

void BitmapFill(Bitmap* bm)
{if(bm == NULL){return;}uint64_t size = bm -> capacity / (sizeof(BitmapType) * 8) + 1;memset(bm -> data, 0xff, sizeof(uint64_t) * size);
}

將位圖清零

void BitmapClean(Bitmap* bm)
{if(bm == NULL){return;}uint64_t size = bm -> capacity / (sizeof(BitmapType) * 8) + 1;memset(bm -> data, 0x00, sizeof(uint64_t) * size);
}