参考答案

具体方案：那么接下来我们只需要申请一个int数组长度为int tmp[N/32+1]即可存储完这些数据，其中N代表要进行查找的总数（这里也就是2^32），tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:tmp[0]:可表示0~31，tmp[1]:可表示32~63，tmp[2]可表示64~95，~~

假设这10亿int数据为：6,3,8,32,36,……，那么具体的BitMap表示为：

(1).如何判断int数字放在哪一个tmp数组中：将数字直接除以32取整数部分(x/32)，例如：整数8除以32取整等于0，那么8就在tmp[0]上；

(2).如何确定数字放在32个位中的哪个位：将数字mod32取模(x%32)。上例中我们如何确定8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。

然后我们怎么统计只出现一次的数呢？每一个数出现的情况我们可以分为三种：0次、1次、大于1次。也就是说我们需要用2个bit位才能表示每个数的出现情况。此时则三种情况分别对应的bit位表示是：00、01、11

我们顺序扫描这10亿的数，在对应的双bit位上标记该数出现的次数。最后取出所有双bit位为01的int型数就可以了。

class BitmapTest {

private static final int CAPACITY = 1000000000;//数据容量

//定义一个byte数组缓存所有的数据

private byte[] dataBytes = new byte[1 << 29];

public static void main(String[] args) {

BitmapTest ms = new BitmapTest();

byte[] bytes = null;

Random random = new Random();

for (int i = 0; i < CAPACITY; i++) {

int num = random.nextInt();

System.out.println("读取了第" + (i + 1) + "\t个数: " + num);

bytes = ms.splitBigData(num);

}

System.out.println("");

ms.output(bytes);

}

/**

*读取数据，并将对应数数据的 到对应的bit中，并返回byte数组

* @param num读取的数据

* @return byte数组  dataBytes

*/

private byte[] splitBigData(int num) {

//获取num数据对应bit数组（虚拟）的索引

long bitIndex = num + (1l << 31);

int index = (int) (bitIndex / 8); //bit数组（虚拟）在byte数组中的索引

//bitIndex在byte[]数组索引index中的具体位置

int innerIndex = (int) (bitIndex % 8);

System.out.println("byte[" + index + "]中的索引：" + innerIndex);

dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));

return dataBytes;

}

/**

*输出数组中的数据

* @param bytes byte数组

*/

private void output(byte[] bytes) {

int count = 0;

for (int i = 0; i < bytes.length; i++) {

for (int j = 0; j < 8; j++) {

if (!(((bytes[i]) & (1 << j)) == 0)) {

count++;

int number = (int) ((((long) i * 8 + j) - (1l << 31)));

System.out.println("取出的第"+ count+"\t个数: "+ number);

}

}

}

}