題目
最近看到一個題目：給40億個不重復的 unsigned int 的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？
解法
搜了一下資料，該題目是騰訊的一道面試題，目前網上普遍給出的答案有兩種。
1.《編程珠璣》給出的方案
我們把40億個數中的每一個用32位的二進制來表示，假設這40億個數開始放在一個文件中。
然后將這40億個數分成兩類：
1.最高位為0。
2.最高位為1。
并將這兩類分別寫入到兩個文件中，其中一個文件中數的個數<=20億，而另一個>=20億（這相當于折半了）。
與要查找的數的最高位比較并接著進入相應的文件再查找。
再然后把這個文件為又分成兩類：1.次最高位為0；2.次最高位為1。
并將這兩類分別寫入到兩個文件中，其中一個文件中數的個數<=10億，而另一個>=10億（這相當于折半了）。與要查找的數的次最高位比較并接著進入相應的文件再查找。
.......
以此類推，就可以找到了,而且時間復雜度為O(logn)。
此方案不是本文要講的重點，只是把思路放在這邊供大家參考。
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實現
由于Java中無法直接操作二進制數，因此我們可以通過 int 來實現。1個二進制數占用1 Bit；1個 int 占用4 Byte，也就是32 Bit。因此，我們可以使用1個int來表示32個二進制數。
所以，我們有以下思路：
第1個int表示：整數0 ~ 31是否存在
第2個int表示：整數32 ~ 63是否存在
第3個int表示：整數64 ~ 95是否存在，依此類推。
因此，我們最終可以使用一個int數組來表示4294967296個二進制數，通過數組的下標來指示第幾個int。
代碼如下
package com.joonwhee.open.leetcode.temp;
/**
* 位圖法
*
* @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個二進制數存在，以此類推
* <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個桶
* 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 = 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 = 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] 來表示。
