void setVal(int val)
{
    bmap[val/32] |= (1<<(val%32));
    //bmap[val>>5] != (val&0x1F);//这个更快？
}

怎样检测整数是否存在？

比如我们检测33，同样我们需要计算index，以及在index元素中的位置

33: index = 1, 在bmap[1]中的位置为 1，只需要检测这个位置是否为1

bmp[1] &(1<<1),这样是1返回true，否侧返回false

67:bmp[2]&(1<<3)

127:bmp[3]&(1<<31)

bool testVal(int val)
{
    return bmap[val/32] & (1<<(val%32));
    //return bmap[val>>5] & (val&0x1F);
}

现在我们来看如果内存要求是10MB呢？

这当然不能用bitmap来直接计算。因为从40亿数据找出一个不存在的数据，我们可以将这么多的数据分成许

多块， 比如每一个块的大小是1000，那么第一块保存的就是0到999的数，第2块保存的就是1000 到1999的数……

实际上我们并不保存这些数，而是给每一个块设置一个计数器。 这样每读入一个数，我们就在它所在的块对应的计数器加1。

处理结束之后， 我们找到一个块，它的计数器值小于块大小(1000)， 说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理
这个块即可。接下来我们就可以用Bit Map算法了。我们再遍历一遍数据， 把落在这个块的数对应的位置1(我们要先把这个数
归约到0到blocksize之间)。 最后我们找到这个块中第一个为0的位，其对应的数就是一个没有出现在该文件中的数。)

 1 //去除重复并排序
 2 import java.util.Arrays;
 3 import java.util.BitSet;
 4 import java.util.Random;
 5 
 6 /**
 7  * @author 8  * @date Time: 
 9  * @des:
10  */
11 public class BitMap {
12     int ARRNUM = 800;
13     int LEN_INT = 32;
14     int mmax = 9999;
15     int mmin = 1000;
16     int N = mmax - mmin + 1;
17 
18     public static void main(String args[]) {
19          new BitMap().findDuplicate();
20          new BitMap().findDup_jdk();
21     }
22 
23     public void findDup_jdk() {
24         System.out.println("*******调用JDK中的库方法--开始********");
25         BitSet bitArray = new BitSet(N);
26         int[] array = getArray(ARRNUM);
27         for (int i = 0; i < ARRNUM; i++) {
28             bitArray.set(array[i] - mmin);
29         }
30         int count = 0;
31         for (int j = 0; j < bitArray.length(); j++) {
32             if (bitArray.get(j)) {
33                 System.out.print(j + mmin + " ");
34                 count++;
35             }
36         }
37         System.out.println();
38         System.out.println("排序后的数组大小为：" + count );
39         System.out.println("*******调用JDK中的库方法--结束********");
40     }
41     //下面是自己实现的方法：
42     public void findDuplicate() {
43         int[] array = getArray(ARRNUM);
44         int[] bitArray = setBit(array);
45         printBitArray(bitArray);
46     }
47 
48     public void printBitArray(int[] bitArray) {
49         int count = 0;
50         for (int i = 0; i < N; i++) {
51             if (getBit(bitArray, i) != 0) {
52                 count++;
53                 System.out.print(i + mmin + "\t");
54             }
55         }
56         System.out.println();
57         System.out.println("去重排序后的数组大小为：" + count);
58     }
59 
60     public int getBit(int[] bitArray, int k) {// 1右移 k % 32位 与上 数组下标为 k/32 位置的值
61         return bitArray[k / LEN_INT] & (1 << (k % LEN_INT));
62     }
63 
64     public int[] setBit(int[] array) {// 首先取得数组位置下标 i/32, 然后 或上
65                                         // 在该位置int类型数值的bit位：i % 32
66         int m = array.length;
67         int bit_arr_len = N / LEN_INT + 1;
68         int[] bitArray = new int[bit_arr_len];
69         for (int i = 0; i < m; i++) {
70             int num = array[i] - mmin;
71             bitArray[num / LEN_INT] |= (1 << (num % LEN_INT));
72         }
73         return bitArray;
74     }
75 
76     public int[] getArray(int ARRNUM) {
77 
78         @SuppressWarnings("unused")
79         int array1[] = { 1000, 1002, 1032, 1033, 6543, 9999, 1033, 1000 };
80 
81         int array[] = new int[ARRNUM];
82         System.out.println("数组大小：" + ARRNUM);
83         Random r = new Random();
84         for (int i = 0; i < ARRNUM; i++) {
85             array[i] = r.nextInt(N) + mmin;
86         }
87 
88         System.out.println(Arrays.toString(array));
89         return array;
90     }
91 }