位图

模型

位图是“位”的数组。

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

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

基本操作

• 增 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. 释放arrayfree(bm->array);// 2. 释放BitMapfree(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->bitsif (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->bitsif (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亿 ($10^9\approx 2^{30}$) 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)