假设有一个需求是这样的：在200亿个随机整数中找出某个数是否存在其中？要求效率高，而且要节省内存。

我们知道，在Java中，int占4字节，1字节=8 byte，1 byte = 8 bit（位）

如果用int存储，那就是200亿个int，因而占用的空间约为

(20000000000*4/1024/1024/1024)≈74.5G。

内存消耗很大，一般的家用电脑是满足不了需求的，所以将数据存储在内存中存储是不合适的。

如果按位存储就不一样了，200亿个数就是200亿位，占用空间约为

(2000000000/8/1024/1024/1024)≈2.33G，节省了30倍的空间。

实际上这就是bitmap的思想。Bitmap的基本思想是用一个bit位来标记某个元素对应的Value，而Key即是该元素本身。采用bit存储数据，可以大大节省存储空间。

Bitmap是什么？如何在bitmap中表示一个数呢？

我们知道计算机底层存储的都是二进制数据，二进制数只有0和1。bitmap每一位的值也只能是0或1，0表示不存在，1表示存在。

这样我们可以很容易表示{1,2,4,6}这几个数：

计算机内存分配的最小单位是字节，也就是8位，那如果要表示{12,13,15}怎么办呢？

当然是在另一个8位上表示：

这样的话，好像变成一个二维数组了

1个int占32位，那么我们只需要申请一个int数组长度为 int tmp[1 N/32] 即可存储，其中N表示要存储的这些数中的最大值，于是：

tmp[0]：可以表示0~31

tmp[1]：可以表示32~63

tmp[2]：可以表示64~95

。。。

于是，对于任意整数M，M/32可以得到下标，M2就可以得到它在此下标的哪个位置。

那么，怎么把一个数放进Bitmap呢？比如想把5这个数字放进去

插入一个数

首先，5/32=0，52=5，也是说它应该在b[0]的第5个位置。我们可以把1向左移动5位，然后和b[0]按位或即可。

二进制就是: