likes
comments
collection
share

如何用一个整数表示一个集合？Bitmap！

作者站长头像
站长
· 阅读数 14

前言

本文主要介绍如何用一个整数来实现集合的功能，包括添加、删除、是否包含，实现这个功能就用到了位图——bitmap。

正文

我们知道集合能添加元素、判断元素是否存在、删除元素等等，在空间占用方面，每往集合中添加一个int型元素，至少要占用4个字节。

一个int型的整数有32位，所以一个int型整数可以表示0 ~ 31范围上的数字，如果换成long类型的话，表示数字的范围就会更加广泛。

那么，我们就可以根据这种特性，来不使用集合就能实现几个简单的集合功能。

思路分析

一个int型的整数占4字节，一共有32位，那么从二进制的角度来考虑，这一个整数就可以表示一个0 ~ 31数字范围的集合，也就是一个int型整数的二进制有32位，可以用这32位来表示32个数。

看到这里，我们可以发现一个int型整数只能表示32个数，使用范围有限，只能表示0 ~ 31范围上的数，其实表示更多的数也是可以的，就算换成long的话，一个long类型的整数也只能表示0 ~ 63范围上的数是否存在，那么怎么才能表示更多的数字呢？

其实也是可以的，比如，如果使用int型，要表示0 ~ 1024上的数，让这个范围的最大值除去32，1024 / 32 = 32，也就是说，我准备一个32长度的数组即可，让数据分段展示：0 ~ 31，32 ~ 63，... ，993 ~ 1024，一共分了32段。

刚才我们使用的是int的数组，我们还可以使用long类型的数组，这样就可以表示更大范围的数。

下面，我们使用long类型的数组来看一下功能的实现：

  1. 判断需要多少长度的数组

    • long是64位的，所以用最大值除去64再加上1即可，高级一点的写法就是(x + 64)>>6。

  2. 添加元素

    • 在添加元素时，需要判断要添加的元素属于这个数组中的哪一个，用这个元素除去64，得到的结果就是数组中的数组下标。
    • 找到下标后，那么这个元素在这个下标对应的数组中二进制位的第几位呢？可以用这个元素与64取模运算，得到的结果就是第几位。
    • 找到第几位后，如何把这个数字给放进去呢？可以直接采用|(或运算)，将1左移对应的位数(b步骤得到的)，与数据进行或运算即可。

  3. 删除元素

    • 删除元素与添加元素基本一致，寻找数组下标和二进制的第几位与添加元素一样。
    • 找到位数后，把1进行左移，然后取反，再进行&（与运算）即可。

  4. 查找元素

    • 查找元素与添加元素和删除元素也是类似的，寻找数组下标和二进制的第几位与添加元素一样。
    • 找到位数后，把1进行左移，再进行&（与运算）即可，如果得到的数为0说明不存在，如果不为0说明存在。

代码实现

根据上面的思路分析，来看一下代码吧，代码如下：

public class BitMap {
   private long[] bits;
   // 初始化，计算数组长度
   public BitMap(int max) {
      bits = new long[(max + 64) >> 6];
   }
   // 添加元素
   public void add(int num) {
      bits[num >> 6] |= (1L << (num & 63));
   }
   // 删除元素
   public void delete(int num) {
      bits[num >> 6] &= ~(1L << (num & 63));
   }
   // 判断是否包含
   public boolean contains(int num) {
      return (bits[num >> 6] & (1L << (num & 63))) != 0;
   }
}

需要注意的是，左移时需要用1L，因为这里使用的是long类型，所以要加上L。

总结

本文主要介绍如何使用bitmap来实现集合的功能，包括添加元素、删除元素、是否包含元素，这个实现是巧妙的运用了二进制的特性以及位运算，虽然看起来很复杂，但是短短几行代码就能实现这个功能。

另外，这里实现的时候，只适用于大于0的整数，不能为负数，如果包含负数的话，可以做一些特殊处理，比如把原整体加上某个数，使其都变成整数再来判断。