
public class MyBitSet {
    public byte[] elem;
    //记录当前位图中，存放了多少个有效数据
    public int usedSize;

    /**
     * 默认初始化位为一个字节
     */
    public MyBitSet() {
        this.elem = new byte[1];
    }

    /**
     * 指定构造方法中的初始化位数
     * 一般会多给一个字节，因为如果是12，那么12%8=4，不能整除，还多出来4个bit位
     * 所以多给一个也无所谓(不要那么抠)
     */
    public MyBitSet(int n) {
        this.elem = new byte[n / 8 + 1];
    }
}

3.2、存放数据

创建一个set方法用来存放数据，首先要先判断数据是否小于0，若小于0就是不符合要求的，直接抛出异常；

怎么存放数据呢？如下图：

最后还要注意，若数据过大，需要考虑扩容（否则会越界访问）；

代码如下：

    /**
     * 设置某一位为1(1为有效)
     * @param val
     */
    public void set(int val) {
        if(val < 0) {//必须是大于等于零的整数
            throw new IndexOutOfBoundsException();
        }
        //先确定val在elem的哪一个下标的哪一个bit位
        int arrayIndex = val / 8;
        //扩容
        if(arrayIndex > elem.length - 1) {
            elem = Arrays.copyOf(elem, arrayIndex + 1);
        }
        int bitIndex = val % 8;
        elem[arrayIndex] |= (1 << bitIndex);//不能是异或，会修改原来的值
        usedSize++;
    }

3.3、检测数据是否存在

创建一个get方法，先检验val值是否小于零，小于直接抛异常，然后还是通过除8模8，左移1的方式确定位置，与存放数据不同， 这回使用按位与，若按位与得到的数字为0，则说明原来这一位就是0，数字不存在，返回false，反之则存在，返回true;

如下代码：


    /**
     * 判断当前位是不是1
     * @param val
     * @return
     */
    public boolean get(int val) {
        if(val < 0) {//必须是大于等于零的整数
            throw new IndexOutOfBoundsException();
        }
        //先确定val在elem的哪一个下标的哪一个bit位
        int arrayIndex = val / 8;
        int bitIndex = val % 8;

        if((elem[arrayIndex] & (1 << bitIndex)) != 0) {
            return true;
        }
        return false;
    }

3.4、设置某个数据的对应位为0

创建一个reSet方法，先检验val值是否小于零，小于直接抛异常；怎么设置为某一位为0呢，好像直接按位与、或、异或都不行，实际上我们可以这样做，按原来的方法，除8模8，左移1的方式确定位置，然后给这个数据取反，再按位与等这一字节，就可以了，如下图：

代码如下：

    /**
     * 将对应位置 设置为0
     * @param val
     */
    public void reSet(int val) {
        if(val < 0) {//必须是大于等于零的整数
            throw new IndexOutOfBoundsException();
        }
        //先确定val在elem的哪一个下标的哪一个bit位
        int arrayIndex = val / 8;
        int bitIndex = val % 8;

        elem[arrayIndex] &= ~(1 << bitIndex);
        usedSize--;
    }

四、位图模拟代码（完整）

public class MyBitSet {
    public byte[] elem;
    //记录当前位图中，存放了多少个有效数据
    public int usedSize;

    /**
     * 默认初始化位为一个字节
     */
    public MyBitSet() {
        this.elem = new byte[1];
    }

    /**
     * 指定构造方法中的初始化位数
     * 一般会多给一个字节，因为如果是12，那么12%8=4，不能整除，还多出来4个bit位
     * 所以多给一个也无所谓(不要那么抠)
     */
    public MyBitSet(int n) {
        this.elem = new byte[n / 8 + 1];
    }

    /**
     * 获取当前位图存储的数据量
     */
    public int getUsedSize() {
        return this.usedSize;
    }


    /**
     * 设置某一位为1(1为有效)
     * @param val
     */
    public void set(int val) {
        if(val < 0) {//必须是大于等于零的整数
            throw new IndexOutOfBoundsException();
        }
        //先确定val在elem的哪一个下标的哪一个bit位
        int arrayIndex = val / 8;
        //扩容
        if(arrayIndex > elem.length - 1) {
            elem = Arrays.copyOf(elem, arrayIndex + 1);
        }
        int bitIndex = val % 8;
        elem[arrayIndex] |= (1 << bitIndex);//不能是异或，会修改原来的值
        usedSize++;
    }

    /**
     * 判断当前位是不是1
     * @param val
     * @return
     */
    public boolean get(int val) {
        if(val < 0) {//必须是大于等于零的整数
            throw new IndexOutOfBoundsException();
        }
        //先确定val在elem的哪一个下标的哪一个bit位
        int arrayIndex = val / 8;
        int bitIndex = val % 8;

        if((elem[arrayIndex] & (1 << bitIndex)) != 0) {
            return true;
        }
        return false;
    }

    /**
     * 将对应位置 设置为0
     * @param val
     */
    public void reSet(int val) {
        if(val < 0) {//必须是大于等于零的整数
            throw new IndexOutOfBoundsException();
        }
        //先确定val在elem的哪一个下标的哪一个bit位
        int arrayIndex = val / 8;
        int bitIndex = val % 8;

        elem[arrayIndex] &= ~(1 << bitIndex);
        usedSize--;
    }

}