一、位图算法
使用位运算来表示和操作数据集的方法。它最常用于处理包含大量唯一元素的数据集，并且可以在常数时间内执行插入、删除和查找操作。位图算法使用一个位数组来表示数据集，其中每个位对应一个元素。如果对应位为1，表示该元素在数据集中；如果对应位为0，表示该元素不在数据集中。
二、位图算法特点
位图适用于处理大规模数据集合，并且具有空间和时间效率高的特点。它常用于解决各种数据处理问题，例如判重、快速查找、去重、排序等。
需要注意的是，位图适用于数据范围较小且离散的情况，如果数据范围很大或者连续，则位图可能不适用，因为会占用过多的内存空间。
三、 位图数据存储
int类型占4个字节，而1个字节占8位，那么int型是 32个字节，表示0–31的数
(在Python3中，int既可以表示整型，也可以表示长整型。)
长整类型占8个字节，而1个字节占8位，那么长整型是64个字节，表示0–63的数
如图，数组的范围只是在2–21之间，那么只用到前3个字节就可描述。如21这个数 ：21/8=2；得到22在第3个字节（下标从0 开始），然后再用21%8=5，得到21在该字节中8个比特位里的具体位置，把该位置比特位设置位1表示存在，0表示不存在。
四、海量数据处理
（1）如果40亿个不重复的无符号整数，且为乱序，如何将其排序？
（2）如果40亿个不重复的无符号整数，且为乱序，给一个无符号整数，如何找出这个数是否在40亿数据中？
使用快速排序然后采用二分法查找，时间复杂度O(nlogn).或者是将一堆数存入unordered_set容器中，使用find进行查找，时间复杂度为O(n)。
单位换算
1字节= 8比特位
1KB = 1024B（字节）
1MB = 1024KB
1GB = 1024 MB
但是内存空间存不下这么多的数字：
40亿个无符号整数，每个大小4个字节，则一共占用160亿字节。
40亿≈16000000000/1024/1024/1024≈16G
而一台32位机的内存地址有32位，每个地址指向1字节（8bits）的数据，其内存地址空间的大小只有2^32=4G字节的空间大小，由于系统本身要占据一部分内存，我们可用的内存只有3.2G左右。
使用位图算法解决
无符号整型的数据范围是0~2^32-1,一共占用(2^32-1)/8/1024/1024/1024=0.5GB=512MB.
我们开好空间以后，我们只需要将数对应的位置为1即可.
class BitMap():def __init__(self, maxValue):# 向上取正 确定数组大小self._size = int((maxValue + 31 - 1) / 31)# 初始化为0self.array = [0 for i in range(self._size)]def getElemIndex(self, num):# 获取该数的数组下标return num // 31def getBitIndex(self, num):# 获取该数所在数组的位下标return num % 31def set(self, num):# 将该数所在的位置设为1elemIndex = self.getElemIndex(num)bitIndex = self.getBitIndex(num)self.array[elemIndex] = self.array[elemIndex] | (1 << bitIndex)def clean(self, num):# 将该数所在的位置0elemIndex = self.getElemIndex(num)bitIndex = self.getBitIndex(num)self.array[elemIndex] = self.array[elemIndex] & (~(1 << bitIndex))def find(self, num):# 查找该数是否存在elemIndex = self.getElemIndex(num)bitIndex = self.getBitIndex(num)if self.array[elemIndex] & (1 << bitIndex):return Truereturn Falseif __name__ == '__main__':ll = [120, 5, 56, 25, 60, 92, 356, 0, 410, 78, 506]results = []bitmap = BitMap(max(ll))for num in ll:bitmap.set(num)for i in range(max(ll) + 1):if bitmap.find(i):results.append(i)print(ll)print(results)# 查找print(bitmap.find(356))print(bitmap.find(16))
