題目
最近看到一個(gè)題目：給40億個(gè)不重復(fù)的 unsigned int 的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中？
解法
搜了一下資料，該題目是騰訊的一道面試題，目前網(wǎng)上普遍給出的答案有兩種。
1.《編程珠璣》給出的方案
我們把40億個(gè)數(shù)中的每一個(gè)用32位的二進(jìn)制來表示，假設(shè)這40億個(gè)數(shù)開始放在一個(gè)文件中。
然后將這40億個(gè)數(shù)分成兩類：
1.最高位為0。
2.最高位為1。
并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)<=20億，而另一個(gè)>=20億（這相當(dāng)于折半了）。
與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找。
再然后把這個(gè)文件為又分成兩類：1.次最高位為0；2.次最高位為1。
并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)<=10億，而另一個(gè)>=10億（這相當(dāng)于折半了）。與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找。
.......
以此類推，就可以找到了,而且時(shí)間復(fù)雜度為O(logn)。
此方案不是本文要講的重點(diǎn)，只是把思路放在這邊供大家參考。
2.位圖法
思路
我們之所以無法將40億個(gè)數(shù)字直接讀取到內(nèi)存去進(jìn)行處理，是因?yàn)?0億個(gè) unsigned int 的整數(shù)大約要占15G內(nèi)存，正常情況下，沒有這么大的內(nèi)存，也不可能這樣做。
這種情況是因?yàn)橐粋€(gè)整數(shù)占用了4個(gè)字節(jié)（Byte），而在本題中，我們其實(shí)只關(guān)心某個(gè)數(shù)字是否存在，在這種情況下，我們可以通過位圖法來解決該問題。
位圖法思想：對(duì)于40億個(gè) unsigned int 的整數(shù)，每個(gè)數(shù)字用1個(gè)二進(jìn)制數(shù)（一個(gè)二進(jìn)制數(shù)占用1Bit，1Byte = 8Bit）來表示該數(shù)字是否存在，0為不存在，1為存在。從低位開始數(shù)：
第1個(gè)二進(jìn)制數(shù)表示整數(shù)0是否存在
第2個(gè)二進(jìn)制數(shù)表示整數(shù)1是否存在
第3個(gè)二進(jìn)制數(shù)表示整數(shù)2是否存在
依次類推 ... ...
第4294967296個(gè)二進(jìn)制數(shù)用于表示整數(shù)4294967295是否存在。
unsigned int 在32&64位編譯器的范圍為 0～4294967295，4294967296個(gè)二進(jìn)制數(shù)大約占用512M內(nèi)存，是一個(gè)可以接受的范圍。
例子
題目：我們讀取了3個(gè)整數(shù)：1、2、4，要判斷整數(shù)3是否被讀取過了。
解答過程：
1）對(duì)于40億個(gè) unsigned int 的整數(shù)，我們可以定義4294967296個(gè)二進(jìn)制數(shù)，并且全部初始化值為0。
2）讀取整數(shù)1：將第2個(gè)二進(jìn)制數(shù)賦值為1，表示整數(shù)1是存在的，此時(shí)值為：10（高位還有4294967294個(gè)0，為了方便閱讀不寫出來，下文同）。
3）讀取整數(shù)2：將第3個(gè)二進(jìn)制數(shù)賦值為1，表示整數(shù)2是存在的，此時(shí)值為：110。
4）讀取整數(shù)4：將第5個(gè)二進(jìn)制數(shù)賦值為1，表示整數(shù)4是存在的，此時(shí)值為：1 0110。
5）判斷整數(shù)3是否被讀取過，因?yàn)榈?個(gè)二進(jìn)制數(shù)表示整數(shù)0是否存在，因此整數(shù)3則通過第4個(gè)二進(jìn)制數(shù)表示，此時(shí)的值為：1 0110，第4個(gè)二進(jìn)制數(shù)為0，所以得出結(jié)論：整數(shù)3沒有被讀取過。
JAVA實(shí)現(xiàn)
由于Java中無法直接操作二進(jìn)制數(shù)，因此我們可以通過 int 來實(shí)現(xiàn)。1個(gè)二進(jìn)制數(shù)占用1 Bit；1個(gè) int 占用4 Byte，也就是32 Bit。因此，我們可以使用1個(gè)int來表示32個(gè)二進(jìn)制數(shù)。
所以，我們有以下思路：
第1個(gè)int表示：整數(shù)0 ~ 31是否存在
第2個(gè)int表示：整數(shù)32 ~ 63是否存在
第3個(gè)int表示：整數(shù)64 ~ 95是否存在，依此類推。
因此，我們最終可以使用一個(gè)int數(shù)組來表示4294967296個(gè)二進(jìn)制數(shù)，通過數(shù)組的下標(biāo)來指示第幾個(gè)int。
代碼如下
package com.joonwhee.open.leetcode.temp;
/**
* 位圖法
*
* @author joonwhee
* @date 2019/1/22
*/
public class BitMap {
/**
* 位圖提供的最大長(zhǎng)度,
* 比如unsigned int的最大值為4294967295,
* 則需要的length為4294967296
*/
private long length;
/**
* 位圖桶
*/
private static int[] bitmapBucket;
/**
* int用來表示32位二進(jìn)制數(shù),
* BIT_VALUE[0]表示第1個(gè)二進(jìn)制數(shù)存在、
* BIT_VALUE[1]表示第2個(gè)二進(jìn)制數(shù)存在，以此類推
* <p>
* 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個(gè)桶
* length為33 - 64: 需要2個(gè)桶
* ...
* 以此類推
*
* @param length
*/
public BitMap(long length) {
this.length = length;
// 根據(jù)長(zhǎng)度算出，所需位圖桶個(gè)數(shù)
bitmapBucket = new int[(int) (length >> 5) +
((length & 31) > 0 ? 1 : 0)];
}
/**
* 查找number是否存在于位圖桶中
*
* @param number 要查詢的數(shù)字
* @return true: number在位圖桶中, 否則false
*/
public boolean getBit(long number) {
if (number < 0 || number > length) {
throw new IllegalArgumentException("非法參數(shù)");
}
// 計(jì)算該number在哪個(gè)桶
int belowIndex = (int) (number >> 5);
// 求出該number在桶里的下標(biāo)（下標(biāo)0 - 31）
int offset = (int) (number & 31);
// 拿到該桶的值
int currentValue = bitmapBucket[belowIndex];
// 計(jì)算該number是否存在
return ((currentValue & BIT_VALUE[offset])) == 0 ? false : true;
}
/**
* 將number在位圖桶中標(biāo)記為存在
*
* @param number 要標(biāo)記的數(shù)字
*/
public void setBit(long number) {
// 合法性校驗(yàn)
if (number < 0 || number >= length) {
throw new IllegalArgumentException("非法參數(shù)");
}
// 計(jì)算該number在哪個(gè)桶
int belowIndex = (int) (number >> 5);
// 求出該number在桶里的下標(biāo)（下標(biāo)0 - 31）
int offset = (int) (number & 31);
// 拿到該桶的當(dāng)前值
int currentValue = bitmapBucket[belowIndex];
// 將number在桶里標(biāo)記
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));
}
}
了解了思路后，代碼就比較簡(jiǎn)單了。
1）通過構(gòu)造函數(shù)傳的 length 值，構(gòu)建一個(gè)足夠大的 int數(shù)組 bitmapBucket，對(duì)于題目的unsigned int 的整數(shù)，length為4294967296剛好夠用。
2）將40億個(gè)給定的數(shù)通過 setBit 方法，將對(duì)應(yīng)的位置的二進(jìn)制數(shù)標(biāo)記為1（1代表存在）。
3）通過 getBit 方法判斷給定的 number 是否存在于之前的40億個(gè)數(shù)中。
setBit 例子：例如我們要將整數(shù) 32 標(biāo)記為存在。
1）首先計(jì)算出整數(shù) 32 所在的位圖桶下標(biāo)為1，也就是bitmapBucket[1]。
2）接著計(jì)算出整數(shù) 32 在bitmapBucket[1] 桶中的下標(biāo)0（下標(biāo)0代表該桶的第1個(gè)二進(jìn)制數(shù)）。
3）拿到bitmapBucket[1]當(dāng)前值currentValue。
4）最后我們要將 bitmapBucket[1] 桶中第1個(gè)二進(jìn)制數(shù)標(biāo)記為1，并且不影響之前已經(jīng)標(biāo)記的二進(jìn)制數(shù)，因此將 currentValue 與0000 0000 0000 0000 0000 0000 0000 0001 進(jìn)行 ‘或’ 運(yùn)算即可。而對(duì)于每一個(gè)二進(jìn)制數(shù)，我們通過 BIT_VALUE來表示，這邊的 0000 0000 0000 0000 0000 0000 0000 0001 ，可以通過 BIT_VALUE[0] 來表示。
