位圖的原理：

• 在位圖中采用比特位表示對應的元素存在或者不存在
  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