位图原理、代码实现及应用实例

位图的原理：

• 在位图中采用比特位表示对应的元素存在或者不存在
  0：不存在
  1：存在
• 例如一个int整数有32个比特位可以表示0-31个整数。

• 再举一个例子
  存入的数字为8988
  首先： 8988/32 = 280
  其次： 8988%32 = 28

• 再来一个例子
  存入的数字16
  首先： 16/32 = 0
  其次： 16%32=16

位图的应用

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集。

• 将第一个文件的数据分成1000份存储到位图里，再判断第二份文件中的数据是否在位图中。

源码

• 测试代码

#include <stdio.h>
#include "BitMap.h"

int main()
{
    BitMap bm;
    BMInit(&bm,100000);
    int i, j;    
    // 插入数据
    for (i = 0; i < 100000; i++) {
        BMSetOne(&bm, i);
    }
	// 判断数字是否在位图里面
    for (j = 990; j < 100010; j++) {
        if (BMTestOne(&bm, j) != 0) {
            printf("数字 %d存在于位图, 返回值： %d\n", j, BMTestOne(&bm, j));
        } else {
            printf("数字 %d不存在于位图, 返回值： %d\n", j, BMTestOne(&bm, j));
        }
    }
    return 0;
}

• 运行结果

数字 99993存在于位图, 返回值： 33554432
数字 99994存在于位图, 返回值： 67108864
数字 99995存在于位图, 返回值： 134217728
数字 99996存在于位图, 返回值： 268435456
数字 99997存在于位图, 返回值： 536870912
数字 99998存在于位图, 返回值： 1073741824
数字 99999存在于位图, 返回值： -2147483648
数字 100000不存在于位图, 返回值： 0
数字 100001不存在于位图, 返回值： 0
数字 100002不存在于位图, 返回值： 0
数字 100003不存在于位图, 返回值： 0
数字 100004不存在于位图, 返回值： 0
数字 100005不存在于位图, 返回值： 0
数字 100006不存在于位图, 返回值： 0
数字 100007不存在于位图, 返回值： 0
数字 100008不存在于位图, 返回值： 0
数字 100009不存在于位图, 返回值： 0

位图占用的空间大小
unsignedint 的取值范围是0到2^32-1=4 294 967 296-1（大约40亿）
申请了约2^32/8=512M的内存
源码

• 优质参考：
  https://blog.csdn.net/tonglin12138/article/details/93382025