计算机最小单位

在计算机中最小的数据单位是bit（比特），bit是二进制数的一位，包含的信息只有两种状态：0和1

常见数据类型长度转换

1 byte = 8 bit
1 char = 2 byte = 16 bit
1 short = 2 byte = 16 bit
1 int = 4 byte = 32 bit
1 long = 8 byte = 64 bit
1 float = 4 byte = 32 bit
1 double = 8 byte = 64 bit

问题思考

思考一个问题，如何在4亿个整数（整数值范围在0~3亿之间）中判断某个整数是否存在？而目前只有一台计算机，内存大小为500M。

最简单的方案就是开一个大小为3亿的数组（int[] data = new int[300000000]），如果100存在，则data[100] = 1，判断某个数是否存在只需要判断该数组中该下标位置上的值是否为1，该数组占用的大小为：

300000000*4 /1024 / 1024 = 1144.4 MB

这显然超出了机器的内存，而且该方案中，int占32bit，而我们记录只需要1个bit，白白浪费了31bit空间，那么能不能只用bit的类型来存储呢？当然是可以

什么是BitMap

BitMap一种数据结构，代表了有限域中的稠集，每一个元素至少出现一次……学术上的定义个人也很难理解，其实Bitmap的基本思想就是用一个bit位来标记某个元素对应的信息（其信息量大小为1bit）由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省空间。

/*
* @Author 松岛安
* */
public class BitMap {
    byte[] bits;
    int max;
    public BitMap(int max){
        this.bits = new byte[(max >> 3)+1];
        this.max = max;
    }
    public void add(int n){
        //落在哪个数组上
        int index = n >> 3;
        //落在byte的哪一位上
        int loc = n & 7;
        //在loc位上置1,做或运算,有1则为1
        bits[index] |= (1<<loc);
    }
    public void delect(int n){
        int index = n>>3;
        int loc = n & 7;
        if(isExit(n)){
            int delete = (1<<loc);
            //做异或运算,相同则为0,不同则为1
            bits[index] ^= delete;
        }
    }
    //查询某个数是否存在
    public boolean isExit(int n){
        int index = n >> 3;
        int loc = n & 7;
        int exit = 1 << loc;
        int flag = bits[index] & exit;
        return !(flag == 0);
    }
}

上面代码中，我们用一个byte[]数组实现BitMap，数组的长度取决于所有要查找整数中最大值max，1 byte = 8 bit，数组的长度 length = max/8 + 1，整数落在byte中的哪一个bit上，可以通过取余（%）运算获得，由于byte = 8 bit（2的整数倍），可以通过与通过与运算计算

插入

当插入整数12时，首先需要计算12落在数组下标为多少的位置，通过位运算计算（1100 >> 3 = 1）落在byte[1] 的位置，在计算落在byte中哪一个bit上（1100 & 111 = 100 = 4），计算得到落在向左偏移量为4的bit上

最后只需或运算即可插入

00000000 | (1<<4) =00000000 | 00010000 = 00010000

查找

查找12是否存在，同样找到12落在哪个bit上，接着进行与运算

00010000 & (1 << 4) = 00010000 & 00010000 = 00010000

若结果为0则不存在，结果不为0则存在

删除

删除12，同样找到12对应落在哪个bit上，接着进行异或运算（相同为0，不同为1）

00010000 ^ (1<<4) = 00010000 ^ 00010000 = 00000000

此时回到一开始的问题，在4亿个整数（整数值范围在0~3亿之间）中判断某个整数是否存在，我们只需要创建长度为 300000000>>3 的byte[ ]数组，即可覆盖0~3亿范围的整数范围，判断其是否存在只需要检查其对应的bit上是否为1即可，空间开销为：

300000000 / 8 /1024 /1024 = 35.8 MB

我们只需要35.8MB的空间就可以表示3亿的数据量，是不是很妙！

如何判断某个数是否重复？

BitMap通过一个bit来判断元素是否存在，如果要判断某个元素是否重复，则需要在此基础上做一点变化。我们用 2个bit 的大小来表示某个元素的三种状态
00：元素不存在
01：元素置存在一个
11：元素重复出现

我们还是以 byte[] 数组作为存储，由于每个元素的状态需要2bit表示，所以空间消耗为原来BitMap的两倍，原来一个byte能表示8个元素，现在只能表示4个

/*
* @Author 松岛安
* */
public class BitMapRepeat {
    byte[] bits;
    int max;
    public BitMapRepeat(int max){
        this.bits = new byte[(max >> 2)+1];
        this.max = max;
    }
    /*
    * 检查元素是否重复
    * */
    public boolean isRepeat(int n){
        int index = n >> 2;
        //在原来基础上左移原来的长度
        int loc = (n & 3) << (n & 3);
        int repeat = 1 << (loc+1);
        int flag = bits[index] & repeat;
        return !(flag == 0);
    }
    /*
    * 检查元素是否存在
    * */
    public boolean isExit(int n){
        int index = n >> 2;
        int loc = (n & 3) << (n & 3);
        int exit = 1 << loc;
        int flag = bits[index] & exit;
        return !(flag == 0);
    }
    /*
    * 添加某个元素
    * */
    public void add(int n){
        int index = n >> 2;
        int loc = (n & 3) << (n & 3);
        //如果元素存在
        if(isExit(n)){
            //将元素所在的bit位置上左移1位的bit置为1
            int repeat = 1 << (loc+1);
            bits[index] |= repeat;
        }else {
            int add = 1 << loc;
            bits[index] |= add;
        }
    }
    /*
    * 删除某个元素
    * */
    public void delete(int n){
        int index = n >> 2;
        int loc = (n & 3) << (n & 3);
        //如果元素存在
        if(isExit(n)){
            //如果元素有重复,将11置为00,即全部都删除
            if(isRepeat(n)){
                int delete = (1 << loc) | (1 << (loc + 1));
                bits[index] ^= delete;
            }else {
                int delete = 1 << loc;
                bits[index] ^= delete;
            }
        }
    }
}