位运算/BitMap位图表示某事物是否存在的集合

题目1

一个整数表示 0-31是否存在的集合。   一个整数4字节，32位， 0-31只要出现在相应位置上标记为1.  节省空间， 如果用hashset来存储，需要 （ 4字节*32 ） 个字节空间

题目2

表示 0-1023 的集合， 使用一个int[]数组 ， 1024/32 = 32， 所以准备一个int[32]的数据即可。

位图的功能和好处以及Java代码实现

1. 位图的功能： 做成一个集合， 数字范围确定，可以告诉你存在还是不存在
2. 位图的好处：极大的压缩空间

public class BitMap {

    private long[] bits;

    // 右移6位，= 除以64  -> (max + 64 ) / 64
    public BitMap(int max) {
        bits = new long[(max + 64) >> 6];
    }

    // 添加
    // num >> 6 ->  num / 64 决定是第几个整数
    // num & 63 ->  num % 64 num模64 等价于 num 与 63（只选7位数01111111） ， num在Long中在第几位。
    // |=  -> x = x1 | x2  把相应位置标为1 ， 1L 也有64位
    // bits[2] = bits[2] | (1L << 42) -> 第二个数字， 第42位，标记成1 ， 主意必须是1L，长整型数
    public void add(int num) {
        bits[num >> 6] |= (1L << (num & 63));
    }

    // 删除
    // 把相应位置标为0
    public void delete(int num) {
        bits[num >> 6] &= ~(1L << (num & 63));
    }

    //是否包含
    public boolean contains(int num) {
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }

    public static void main(String[] args) {
        System.out.println("测试开始！");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTime = 10000000;
        for (int i = 0; i < testTime; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            // 1/3概率加一个数
            if (decide < 0.333) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {
                // 1/3概率删除一个数
                bitMap.delete(num);
                set.remove(num);
            } else {
                // 1/3概率查一个数
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("Oops!");
                    break;
                }
            }
        }
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }
}