位图（C语言版）

文章目录 位图模型基本操作实现代码运行结果 应用存储只有两种状态的数据排序并去重

位图 模型

位图是“位”的数组。

为什么需要构建一个专门的数据结构来表示位的数组？：因为计算机最小的寻址单位是字节，而不是位。

位图是一种内存紧凑的数据结构，即位图在内存资源紧张的设备中更多使用，如嵌入式设备等。

基本操作 增 set：将某一位设置为1删 unset：将某一位设置为0查 isset：判断某一位是不是1遍历 实现 代码 // 位运算技巧 n * 32 等价于 n << 5 /* 2^5 = 32 */ n / 32 等价于 n >> 5 n % 32 等价于 n & 0x1F /* 与31(MASK)相与 */ n |= 0x1 << offset /* 将n的第offset位设置为1 */ n &= ~(0x1 << offset) /* 将n的第offset位设置为0 */

位图要求尽可能少地使用内存空间，所以实际使用多少内存，就申请多少内存。

// BitMap.h #include <stdbool.h> #include <stdint.h> typedef uint32_t Word; // uint32_t: 1.大小确定 (32bits); 2.无符号整数 typedef struct { Word* array; size_t bits; // 位数组的长度 } BitMap; BitMap* bitmap_create(size_t bits); void bitmap_destroy(BitMap* bm); void bitmap_set(BitMap* bm, size_t n); // n is a bit index void bitmap_unset(BitMap* bm, size_t n); bool bitmap_isset(BitMap* bm, size_t n); void bitmap_clear(BitMap* bm); // BitMap.c #include "BitMap.h" #include <stdlib.h> #include <string.h> #include <stdio.h> #define BITS_PER_WORD 32 #define BITMAP_SHIFT 5 #define BITMAP_MASK 0x1F // 存储bits位，需要多少个word #define BITMAP_SIZE(bits) ((bits + BITS_PER_WORD - 1) >> BITMAP_SHIFT) // 位图的长度 BitMap* bitmap_create(size_t bits) { BitMap* bm = (BitMap*)malloc(sizeof(BitMap)); bm->array = (Word*)calloc(BITMAP_SIZE(bits), BITS_PER_WORD); bm->bits = bits; return bm; } void bitmap_destroy(BitMap* bm) { // 1. 释放array free(bm->array); // 2. 释放BitMap free(bm); } void grow_capacity(BitMap* bm, size_t bits) { Word* newArray = (Word*)realloc(bm->array, BITMAP_SIZE(bits) * sizeof(Word)); bm->array = newArray; // realloc 并不会自动将扩容的空间清零，需要手动清零 int bytes = (BITMAP_SIZE(bits) - BITMAP_SIZE(bm->bits)) * sizeof(Word); memset(bm->array + BITMAP_SIZE(bm->bits), 0, bytes); } void bitmap_set(BitMap* bm, size_t n) { // n is a bit index // 需判断索引n是否在位图范围内 if (n + 1 > bm->bits) { // 这里不一定要扩容，但要改变bm->bits if (BITMAP_SIZE(n + 1) > BITMAP_SIZE(bm->bits)) { // 不在BitMap范围内，需扩容 // 扩容 grow_capacity(bm, n + 1); } bm->bits = n + 1; } // 如何表示第n位(word, offset) size_t word = n >> BITMAP_SHIFT; // 该索引在哪个word块中 size_t offset = n & BITMAP_MASK; // 等价于 n % BITS_PER_WORD (取余操作)，表示该索引在该word块的offset位 bm->array[word] |= (0x01 << offset); } void bitmap_unset(BitMap* bm, size_t n) { // 需判断索引n是否在位图范围内 if (n + 1 > bm->bits) { // 这里不一定要扩容，但要改变bm->bits if (BITMAP_SIZE(n + 1) > BITMAP_SIZE(bm->bits)) { // 不在BitMap范围内，需扩容 // 扩容 grow_capacity(bm, n + 1); } bm->bits = n + 1; } // 如何表示第n位(word, offset) size_t word = n >> BITMAP_SHIFT; // 该索引在哪个word块中 size_t offset = n & BITMAP_MASK; // 等价于 n % BITS_PER_WORD (取余操作)，表示该索引在该word块的offset位 bm->array[word] &= ~(0x01 << offset); } bool bitmap_isset(BitMap* bm, size_t n) { // 需判断索引n是否在位图范围内 if (n + 1 > bm->bits) { printf("索引n不在位图范围内\n"); return false; } // 如何表示第n位(word, offset) size_t word = n >> BITMAP_SHIFT; // 该索引在哪个word块中 size_t offset = n & BITMAP_MASK; // 等价于 n % BITS_PER_WORD (取余操作)，表示该索引在该word块的offset位 return bm->array[word] & (0x1 << offset); } void bitmap_clear(BitMap* bm) { // 全部置零 int bytes = BITMAP_SIZE(bm->bits) * sizeof(Word); memset(bm->array, 0, bytes); } // main.c #include <stdio.h> #include "BitMap.h" int main() { BitMap* bm = bitmap_create(100); int bits_per_word = 8 * sizeof(bm->array[0]); printf("位图使用了%d 位的空间，实际开辟的内存空间%d\n", bm->bits, bits_per_word * (1 + bm->bits / bits_per_word)); bitmap_set(bm, 80); printf("第80位的值为：%d\n", bitmap_isset(bm, 80)); bitmap_unset(bm, 80); printf("第80位的值为：%d\n", bitmap_isset(bm, 80)); bitmap_set(bm, 130); // 扩容 printf("位图使用了%d 位空间，实际开辟的内存空间%d\n", bm->bits, bits_per_word * (1 + bm->bits / bits_per_word)); bitmap_clear(bm); printf("第0~50位的值为："); for (int i = 0; i < 50; i++) { printf(" %d", bitmap_isset(bm, i)); } bitmap_destroy(bm); return 0; } 运行结果

应用 存储只有两种状态的数据

比如，存储10亿 ( 1 0 9 ≈ 2 30 10^{9} \approx 2^{30} 109≈230) QQ用户的在线状态：

如果用int数组存储，那么需要的存储空间为：4B * 2^30 = 4GB如果用位图存储，所需空间位：1/8B * 2^30 = 0.125GB 排序并去重

比如排序数组int array[] = {123, 456, 3, 7, 8, 9, 34, 3, 7, 3};并去重

如果用平常方法：需要先对数组进行排序（快速排序O(nlog(n)），然后对排序后的数组去重 (O(n))使用位图，可以将数组array的值对应为位图的位索引， 比如数组第一个值为123， 那么就将位图索引为128的位设置为1，对其他数组值也进行相同处理。最后输出位图中值为1的位对应索引即可。时间复杂度为O(n)