关于bitmap:BitMap

根本思维 ：
不同于应用 int（long 或 double 或 …）类型来存储某个元素，BitMap 采纳一个 bit 位来标记某个元素（bit 位的 value 为 1 示意该元素存在，此时该 bit 位的 index 即为该元素的值。）

一个字节 byte 占用 8 个 bit 位，每个 bit 位的值为 0 或 1，0 代表该 bit 位没有元素存储，1 代表该 bit 位的元素存在（元素的值为该 bit 位的 index）。

问题：

问题：给 40 亿个不反复的 unsigned int 的整数，没排序。再给一个数，疾速判断这个数是否存在 40 亿个整数中？内存限度 2G。

剖析过程 ：
40 亿个无符号整数须要占用的内存空间 = 40 * 10^8 * 4 / 2^30 ≈ 14.9G，无奈全副加载到内存中应用传统的内存排序。
如果应用 BitMap，须要占用的内存空间 = 40 * 10^8 / 8 / 2^30 ≈ 477M，大大节俭了存储空间。

byte[]
index = n >> 3;
position = n & 7;

// add(n)
byte[index] |= 1 << position;

// clear(n)
byte[index] &= ~(1 << position);

// contain(n)
byte[index] & (1 << position) != 0

算法