位图：

位图概念：

例如：

        之前腾讯的一道面试题：

        给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】

这道题如果用排序的思想去做会非常麻烦，

如果用最快的排序+遍历：时间复杂度O(log n)+O(n)。

用排序+二分查找时间复杂度：O(log n) + O(log n)。

此时如果一个无符号整数占4个字节，那么40亿个整数是：

需要用14.9011GB的内存，占用的空间是非常大的。

那么如果用位图去解决，每一位代表一个数字，一个整型32位，就可以代表32个数字

那么40亿个数字，就只需要用40亿+1个位。

也就是约等于：0.46566GB的内存就可以解bingqie！

 自己实现简易位图：

如图：

        

每位都表示一个数字！！

class类定义为：

public class bitMap {
    private byte[] arr;
    private int usedsize;
    public bitMap() {
        arr = new byte[1];
    }
    //n个比特位
    public void myBitMap(int n) {
        arr = new byte[n/8+1];
    }
}

每一位的插入push：

        如果此时每一位代表一个数字，那么如何找到对应的位？

只需要/8和%8操作。

如果此时有一个byte[]类型的数组，此时每一个下标表示的的是一个byte，一个byte表示的是8个bit。

此时先将我们呢要存放的数据/8找到数组的下标，之后再%8找到对应的位，那么要想操作位，就需要用到位操作运算符：&  |  ^   ~ 等等的操作符！

所以此时就需要讲val%8对应的位改为1，只需要将byte[val/8] |= 1<<val%8（按位或等）！

代码如下：

 public void push(int val) {
        if(val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arryIndex =  val/8;
        int bitIndex = val%8;
        arr[arryIndex] |= (1<<bitIndex);
        usedsize++;
    }

判断val值是否存在：

        如何判断val值是否存在于位图里面，如果存在那么对应位置上面应该是1.

此时话是需要找到对你应为图的位置，也就是/8和%8的操作！

找到对应位置之后，就需要判断该位置是否为1，就需要用到&运算符！

代码如下：

    public boolean get(int val) {
        if(val <0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex =  val/8;
        int bitIndex = val%8;
        if(arr[arrayIndex] % (1<<bitIndex) != 0) {
            return true;
        }
        return false;
    }

删除数据：

        如何在位图中删除数据，首先要判断val值是否符合条件，如果符合，还是重复相同的步骤找到要删除位的位置，将对应的位置0！

        需要用到~和&运算符！

代码如下：
 

    public void reSet(int val) {
        if(val<0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8;
        int bitIndex = val % 8;
        arr[arrayIndex] &= ~(1<<bitIndex);
        usedsize--;
    }