当前位置：首页 > article >正文

Bit-map按位存储--轻松应对面试被问到从10亿个数字中查找指定数是否存在

article 2024/10/11 17:44:32

首先：1G=1024M，1M=1024KB，1KB=1024B（字节） 1G = 102410241024 =1073741824 字节（约等于10亿个字节。）所以10亿个数字，如果是int32位（4个Byte）的话，大概就是4G的内存。

1000000000*4/1024/1024/1024≈3.725 G

显然消耗的内存空间太多了。如果按位存储就不一样了，10亿个数就是10亿位，占用空间约为：

1000000000/8/1024/1024/1024≈0.116 G

只有原来的 $\frac{1}{32}$

什么是按位存储(Bit-map)

Bit-map的基本思想就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

Bit-map每一位表示一个数，0表示不存在，1表示存在。例如我们要存储数字{1,2,3,6}，则可以使用Bit-map存储结构如下：

计算机内存分配的最小单位是字节，也就是8位，那如果要表示{12,13,15}怎么办呢？当然是在另一个8位上表示了，如下图所示：

有没有感觉这样得结构有点眼熟？不错，好像变成一个二维数组。我们知道1个int占32位，如果我们要存储得数字得最大数字是N，则我们只需要申请一个int数组长度为 int b[1+N/32] 即可存储，其中:

b[0]：可以表示0~31;
b[1]：可以表示32~63;
b[2]：可以表示64~95;
...

这样，给定任意整数N，那么N/32就得到下标，N%32就知道它在此下标的哪个位置。

Bit-map 添加数据

如果现在我们想把5这个数字放进去，怎么做呢？上面提到了，给定任意整数N，那么N/32就得到下标，N%32就知道它在此下标b的哪个位置。首先，5/32=0，也是说它应该在b[0]，5%32=5，说明它应该在b[0]的第5个位置，那我们把1向左移动5位，然后与原数据按位或：

代码如下

b[0] = b[0] | (1<<5)

因此，公式可以概括为：p + (i/8)|(1<<(i%8)) 其中，p表示现在的值，i表示待插入的数。

Bit-map 清除数据

假设我们要移除某个数字N，该怎么做呢？只需将该数所在的位置为0即可，那么怎么可以做到呢？为了便于理解，我们还是将结构看成是一个二位数组。则步骤可以归纳如下： N/32得到下标i，N%32得到此下标的位置index；将1左移index位，就到达index这个数字所代表的位；按位取反，最后与原数按位与，将改位置置0。假设我们要6移除，我们用图示来表示以一下执行过程：

Bit-map 快速查找数据

前面我们也说了，每一位代表一个数字，1表示有（或者说存在），0表示无（或者说不存在）。通过把该为置为1或者0来达到添加和清除的效果，那么判断一个数存不存在就是判断该数所在的位是0还是1。所以查找相对来说比较简单。假设，我们想知道6在不在，那么只需判断 b[0] & (1<<6) 如果这个值是0，则不存在，如果是1，就表示存在。