腾讯算法：判断一个数是否在40亿个整数中？最后附java代码( 二 ) _算法

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
*/
public boolean getBit(long number) {
if (number < 0 || number > length) {
throw new IllegalArgumentException("非法参数");
}
// 计算该number在哪个桶
int belowIndex = (int) (number >> 5);
// 求出该number在桶里的下标（下标0 - 31）
int offset = (int) (number & 31);
// 拿到该桶的值
int currentValue = https://www.isolves.com/it/cxkf/sf/2020-08-10/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在桶里的下标（下标0 - 31）
int offset = (int) (number & 31);
// 拿到该桶的当前值
int currentValue = https://www.isolves.com/it/cxkf/sf/2020-08-10/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] 来表示。

【腾讯算法：判断一个数是否在40亿个整数中？最后附java代码】