如何判断一个数是否在40亿个整数中
2.1《编程珠玑》给出的方案
我们把40亿个数中的每一个用32位的二进制来表示，假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类：1.最高位为0；2.最高位为1。
并将这两类分别写入到两个文件中，其中一个文件中数的个数
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类：1.次最高位为0；2.次最高位为1。
并将这两类分别写入到两个文件中，其中一个文件中数的个数
以此类推，就可以找到了,而且时间复杂度为O(logn)。
此方案不是本文要讲的重点，只是把思路放在这边供大家参考。
2.2 位图法
我们之所以无法将40亿个数字直接读取到内存去进行处理，是因为40亿个unsigned int的整数大约要占15G内存，正常情况下，没有这么大的内存，也不可能这样做。
这种情况是因为一个整数占用了4个字节（Byte），而在本题中，我们其实只关心某个数字是否存在，在这种情况下，我们可以通过位图法来解决该问题。
位图法思想：对于40亿个unsigned int的整数，每个数字用1个二进制数（一个二进制数占用1Bit，1Byte = 8Bit）来表示该数字是否存在，0为不存在，1为存在。从低位开始数：
第1个二进制数表示整数0是否存在，
第2个二进制数表示整数1是否存在，
第3个二进制数表示整数2是否存在，
依次类推… …
第4294967296个二进制数用于表示整数4294967295是否存在。
unsigned int在32&64位编译器的范围为0～4294967295，4294967296个二进制数大约占用512M内存，是一个可以接受的范围。
题目：我们读取了3个整数：1、2、4，要判断整数3是否被读取过了。
解答过程：
1）对于40亿个unsigned int的整数，我们可以定义4294967296个二进制数，并且全部初始化值为0。
2）读取整数1：将第2个二进制数赋值为1，表示整数1是存在的，此时值为：10（高位还有4294967294个0，为了方便阅读不写出来，下文同）
3）读取整数2：将第3个二进制数赋值为1，表示整数2是存在的，此时值为：110
4）读取整数4：将第5个二进制数赋值为1，表示整数4是存在的，此时值为：1 0110
5）判断整数3是否被读取过，因为第1个二进制数表示整数0是否存在，因此整数3则通过第4个二进制数表示，此时的值为：1 0110，第4个二进制数为0，所以得出结论：整数3没有被读取过。
由于Java中无法直接操作二进制数，因此我们可以通过int来实现。1个二进制数占用1Bit；1个int占用4Byte，也就是32Bit。因此，我们可以使用1个int来表示32个二进制数。
所以，我们有以下思路：
第1个int表示：整数0~31是否存在，
第2个int表示：整数32~63是否存在，
第3个int表示：整数64~95是否存在，依此类推。
因此，我们最终可以使用一个int数组来表示4294967296个二进制数，通过数组的下标来指示第几个int。
代码如下
/**
* 位图法
*
* @author joonwhee
* @date 2019/1/22
*/
public class BitMap {
/**
* 位图提供的最大长度,
* 比如unsigned int的最大值为4294967295, 则需要的length为4294967296
*/
private long length;
/**
* 位图桶
*/
private static int[] bitmapBucket;
/**
* int用来表示32位二进制数,
* BIT_VALUE[0]表示第1个二进制数存在、
* BIT_VALUE[1]表示第2个二进制数存在，以此类推
*
* BIT_VALUE[0] = 00000000 00000000 00000000 00000001
* BIT_VALUE[1] = 00000000 00000000 00000000 00000010
* BIT_VALUE[2] = 00000000 00000000 00000000 00000100
* ...
* BIT_VALUE[31] = 10000000 00000000 00000000 00000000
*/
private static final int[] BIT_VALUE = {
0x00000001, 0x00000002, 0x00000004, 0x00000008,
0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800,
0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000,
0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000,
0x10000000, 0x20000000, 0x40000000, 0x80000000};
/**
* length为1 - 32: 需要1个桶
* length为33 - 64: 需要2个桶
* ...
* 以此类推
*
* @param length
*/
public BitMap(long length) {
this.length = length;
// 根据长度算出，所需位图桶个数
bitmapBucket = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
}
/**
* 查找number是否存在于位图桶中
*
* @param number 要查询的数字
* @return true: number在位图桶中, false: number不在位图桶中
*/
public boolean getBit(long number) {
if (number < 0 || number > length) {
throw new IllegalArgumentException("非法参数");
}
// 计算该number在哪个桶
int belowIndex = (int) (number >> 5);
// 求出该number在桶里的下标,（求出该值在32位中的哪一位, 下标0 - 31）
int offset = (int) (number & 31);
// 拿到该桶的值
int currentValue = bitmapBucket[belowIndex];
// 计算该number是否存在
return ((currentValue & BIT_VALUE[offset])) == 0 ? false : true;
}
/**
* 将number在位图桶中标记为存在
*
* @param number 要标记的数字
*/
public void setBit(long number) {
// 合法性校验
if (number < 0 || number >= length) {
throw new IllegalArgumentException("非法参数");
}
// 计算该number在哪个桶
int belowIndex = (int) (number >> 5);
// 求出该number在桶里的下标,（求出该值在32位中的哪一位, 下标0 - 31）
int offset = (int) (number & 31);
// 拿到该桶的当前值
int currentValue = bitmapBucket[belowIndex];
// 将number在桶里标记
bitmapBucket[belowIndex] = currentValue | BIT_VALUE[offset];
}
public static void main(String[] args) {
BitMap bitMap = new BitMap(4294967296L);
bitMap.setBit(4294967295L);
System.out.println(bitMap.getBit(4294967295L));
System.out.println(bitMap.getBit(4294967294L));
}
}
了解了思路后，代码就比较简单了。
1）通过构造函数传的length值，构建一个足够大的int数组bitmapBucket，对于题目的unsigned int的整数，length为4294967296刚好够用。
2）将40亿个给定的数通过setBit方法，将对应的位置的二进制数标记为1（1代表存在）。
3）通过getBit方法判断给定的number是否存在于之前的40亿个数中。
setBit例子：例如我们要将整数32标记为存在。
1）首先计算出整数32所在的位图桶下标为1，也就是bitmapBucket[1]。
2）接着计算出整数32在bitmapBucket[1]桶中的下标0（下标0代表该桶的第1个二进制数）。
3）拿到bitmapBucket[1]当前值currentValue。
4）最后我们要将bitmapBucket[1]桶中第1个二进制数标记为1，并且不影响之前已经标记的二进制数，因此将currentValue与0000 0000 0000 0000 0000 0000 0000 0001进行’或’运算即可。而对于每一个二进制数，我们通过BIT_VALUE来表示，这边的0000 0000 0000 0000 0000 0000 0000 0001，可以通过BIT_VALUE[0]来表示。
Original: https://www.cnblogs.com/ciel717/p/16673920.html
Author: 夏尔_717
Title: 【海量数据算法】如何判断一个数是否在40亿个整数中
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/598926/
转载文章受原作者版权保护。转载请注明原作者出处！