位数组

如何判断一个数字是否在海量的数字中出现？

常规做法是把海量数字存放到HashMap中，但这会造成内存溢出。
位数组就是用更少的内存来构建这个 "HashMap"。

位数组的核心思想是用一个char来表示8个整数，char转换成2进制后，正好是8位长，每一位表示一个整数，例如：10011010，分别对应0,1,2,3,4,5,6,7，其中0存在，3存在，4存在，6存在，其他不存在。 因为每一个数字都可以用n * 8 + x //x为0~7来表示，所以n用数组的下标表示，0~7用当前下标的值表示。

简要代码为：

public class Test {

    char[] c = new char[64];

    public static void main(String[] args) {
        Test test = new Test();
        System.out.println(test.check(2));
        test.add(2);
        System.out.println(test.check(2));
        
    }

    public void add(int num) {
        c[num >> 3] |= (1 << (num & 0x07));
    }

    public boolean check(int num) {
        return (c[num >> 3] & (1 << (num & 0x07))) != 0x00;
    }
}

num >> 3的意思数字除以8，找到数字在数组中的位置。
num & 0x07的意思是数字和二进制的0111做与运算，得到0~7的一个值，并且正好是8个不同数字对应8个不同的结果，这样就能用一个char来表示8个数字了，一个char数组表示8*lenth个数字了，内存大大减少。