题目
给一台普通PC，2G内存，要求处理一个包含20亿个不重复并且没有排过序的Int整数，给出一个整数，问如果快速地判断这个整数是否在文件20亿个数据当中？
分析
由于一个Int整数为4个字节（Byte），那所需要的内存空间为 20亿 * 4字节 ≈ 7.45 GB。由于电脑内存只有2GB，无法一次性加载整个数据集到内存中进行查找，所以我们得换个思路。
已知一个字节由八个二进制位组成（如：10101001），因此我们可以用一个二进制位（Bit）标记一个整数是否存在，存在标记为1，不存在标记为0，具体如下：
| Number | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| Bit | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
表格标记了0到7的数字，其中 0、3、5和7被标记为1，即集合中存在0、3、5和7，可表示为：int[ ] a = { 0, 3, 5, 7 }，这种 位映射 的方式被称为 bit-map（位图） 。 因为1Int = 4Bytet = 32Bit，所以一个Int所占的二进制位可以映射32个数字，相当于压缩了32倍，那么之前20亿个整数所需要的7.45GB内存可缩减至238.41MB，至此该数据集可以一次性加载到2G内存的电脑上。
详解
一个Int可以映射32个数，那我们最大可申请(n / 32) + 1个容量的数组，即：
int[] arr = new int[(n / 32) + 1];
其中：
arr[0]:可映射0~31的数
arr[1]:可映射32~63的数
arr[2]:可映射64~95的数
...
添加数字number到数组
- 首先计算数字number在arr数组中的下标index，解：
// 数字number除以int的位数32，得到arr数组中的下标index，使用位运算优化可得:
int index = number >> 5;
- 其次计算数字number在arr[index]中的二进制位position，解：
// 数字number模以int的位数32，得到元素的二进制位position，使用位运算优化可得:
int position = number & (32 - 1);
- 最后取出 之前存放的元素 和 新的元素 进行| 或运算，相当于取两边二进制位的并集，然后再赋值给数组。
arr[index] = arr[index] | (1 << position);
最终的函数可为:
public void add(int number){
int index = number >> 5;
int position = number & 31;
arr[index] |= 1 << position;
}
注: | 或运算相当于取并集，列：0101 | 0011 = 0111
从数组中移除数字number
标记一个数是否存在，是将其二进制位设为1，如果要移除就把该位置设为0，相当于位运算中的 ~ 取反。最后在和 之前存放的元素 进行 & 与运算，相当于取两边二进制位的交集，然后再赋值给数组。
arr[index] = arr[index] & ~(1 << position);
最终的函数可为:
public void remove(int number){
int index = number >> 5;
int position = number & 31;
arr[index] &= ~(1 << position);
}
注: & 与运算相当于取交集，列：0101 & 0011 = 0001
判断数字number是否存在
确认该数字的位置，把这个数无符号右移到最低位，然后在和1进行 & 与运算，去除高位的数，最后判断这个数是1还是0，即存在还是不存在。
public boolean contains(int number) {
int index = number >> 5;
int position = number & 31;
return ((arr[index] >>> position) & 1) == 1;
}
应用
位图算法应用场景，例如：
- 布尔型集合操作：位图还可以进行位运算，如 & 与（AND）、| 或（OR）、^ 异或（XOR）、~ 取反（NOT）等操作，以支持高效的集合运算，比如并集、交集、差集等。
- 数据压缩：位图算法可以用于数据的压缩和压缩索引，例如在索引大量文本数据时，可以将每个单词使用位图表示，从而减少索引的存储空间。
- 布隆过滤器（Bloom Filter）：布隆过滤器是一种概率型数据结构，利用位图算法和多个哈希函数，可以高效地判断一个元素是否属于一个集合。
- 数据去重：通过位图算法可以快速地判断一个元素是否已经存在于一个数据集合中，从而实现数据去重的功能。
场景
1.判断用户是否登录
思路： 使用redis的bitmap结构存储，只需要一个key，然后用户id为偏移量offset，如果在线就设置为1，不在线就设置为0。
2.统计用户打卡情况
思路： 使用时间作为缓存的key，然后用户id为偏移量offset，如果当日打过卡就设置为1。之后通过bitOp进行二进制计算算出在某段时间内用户的活跃情况。
3.视频属性的扩展
思路： 一个拥有亿级数据量的短视频app，视频存在各种属性(是否加锁、是否特效等等)，需要做各种标记。key由属性的type组成。然后视频id为偏移量offset。
