本文共 1229 字，大约阅读时间需要 4 分钟。

位图的原理：

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

• 再举一个例子

  存入的数字为8988
  首先： 8988/32 = 280
  其次： 8988%32 = 28

• 再来一个例子

  存入的数字16
  首先： 16/32 = 0
  其次： 16%32=16

位图的应用

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

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

源码

• 测试代码

#include 
   
    #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

位图占用的空间大小

• 优质参考：

转载地址：http://coorb.baihongyu.com/