【算法与数据结构专场】BitMap算法基本操作代码实现

上篇我们讲了BitMap是如何对数据进行存储的，没看过的可以看一下【算法与数据结构专场】BitMap算法介绍

这篇我们来讲一下BitMap这个数据结构的代码实现。

回顾下数据的存储原理

一个二进制位对应一个非负数n，如果n存在，则对应的二进制位的值为1，否则为0。
这个时候，我们的第一个问题：
我们在使用byte,int,short,long等这些数据类型在存储数据的时候，他们最小的都要占用一个字节的内存，也就是8个bit，也就是说，最小的操作单位是8个bit。根本就没有可以一个一个bit位操作的数据类型啊。

在Java的bitMaP实现中，它采用的是用一个long数据来进行存储的。一个long占用8个字节，即64bit，所以一个long可以存储64个数。例如 arr 是一个long 类型的数组，则 arr[0]可以存 0 ~ 63，arr[1]可以存64 ~127，以此类推。
不过，我们就采用byte数组的来存吧。一个byte占用一个字节，即8bit，可以存8个数字。
当然，你要采用long数组来存也可以。在实现上可以说是一样的。
例如我们要存储(1,3,5,7,8,10)时，他们的内存如下所示。

下面我们就来讲讲如何对一个一个位进行操作的。

如何向bitmap中添加一个数值

我们先来说说如何在bitmap中如何添加一个数值的问题，例如我们我们要添加n=14。
这个其实很简单，我们先找到n在arr数组中的下标index，显然index = 1。然后再找到n在arr[index]中的位置position，显然这里position = 6。
这里还是可以很容易找出index和position的公式的。即
index = n / 8 = n >> 3。
position = n % 8 = n & 0x07。

接下来我们把1向右移动position个二进制位，然后把所得的结果和arr[index]做“或(or)”操作就可以了。如下图

这里有个需要注意的地方，在画图的时候，为了方便，我们是把左边的位当作低位，右边的位当作高位来算了。不过在实际的存储中，左边的才是存高位，而右边的存的是低位。所以在我们的代码实现中，我们所说的右移对应代码的左移。
代码实现

//添加数据的操作 public void add(int n){ //用>>的操作是，运算会比较快 int index = n >> 3; int position = n & 0x07; //把1右移和做or操作两步一起 //即 << 对应上图的右移，实际上<<是左移符。 arr[index] |= 1 << position; }

知道了add操作，其他的操作差不多类似。
当然，我们实现的add操作只是简单的实现一下，假如你要严谨地实现的话，还是需要很多异常的判断的。例如判断这个数是否是非负数，判断arr数组是否下标越界，进行容量的扩充等等。有兴趣的可以严谨去实现一下。

删除操作。

我们只需要把对应的二进制的1变成0就可以了。
我们可以把1右移(代码中对应左移)后的结果取反，然后与arr[index]做“与”操作就可以了。代码如下：

public void delete(int n){ int index = n >> 3; int position = n & 0x07; arr[index] &= ~(1 << position); } 判断是否存在操作

我们把1右移之后，把结果和arr[index]做“与”操作，如何结果不为0，则证明存在，否则就不存在。

public boolean contain(int n){ int index = n >> 3; int position = n & 0x07; return (arr[index] & (1 << position)) != 0; }

三个最基本的操作代码基本实现了。
希望大家能够去实践一下。
全部代码：

public class BitMap { private byte[] arr; //容量，即最多能够存多少个数据 private int capacity; public BitMap(int capacity) { this.capacity = capacity; //一个byte可以存8个数据，capacity实际上指的是多少个bit arr = new byte[(capacity / 8 + 1)]; } //添加数据的操作 public void add(int n){ //用>>的操作是，运算会比较快 int index = n >> 3; int position = n & 0x07; //把1右移和做or操作两步一起 //即 << 对应上图的右移，实际上<<是左移符。 arr[index] |= 1 << position; } public void delete(int n){ int index = n >> 3; int position = n & 0x07; arr[index] &= ~(1 << position); } public boolean contain(int n){ int index = n >> 3; int position = n & 0x07; return (arr[index] & (1 << position)) != 0; } } 问题

大家看了以上的代码，有没发现一些问题呢？