一、 bitmap 是什么东东

简单且抽象来说bitmap用一个bit位来标记某个元素所对应的value，而key就是该元素。而它主要用来解决海量数据中元素查询，去重、以及排序等问题。

二、基本概念梳理

#  存储单位
#  换算的方式GB=>MB=>KB=>Byte=>Bit
#  1、 1 G = 1024 M ; 1M = 1024 KB; 1 KB = 1024 Bytes ; 1 Byte = 8 bit
#  2、 1 G = 1024 M = 1024 * 1024 KB = 1024 * 1024 * 1024 Byte = 1024 * 1024 * 1024 * 8 bit
#  3、 1024 = 2^10 --> 1GB = 2^30 bit

一个整数型的数字在一台31位的计算机中占4个字节，也就是32个bit;而bitmap算法就是用对应的32个bit位来表示十进制的0-31个数。

比如这么一个场景：有一台内存为 2 GB 的 PC，其硬盘中的一个存储了 30 亿个无符号整型数据文件(数据无重复)，我们要对其进行排序。

我们来简单估算一下，这个数据文件的大小为 2 * 3 * 10^9 /2^30 约为 5.6 GB，,而我们的计算机就只有2G的内容，显然将这个数据文件直接读入内存是办不到的。我们来看一下如果用bitmap的思想，假设能用一个 bit 位来标示一个 int 整数，30亿个整数需要的内存空间为 3 * 10^9/8/2^20 大概为 357.6 MB，这样需要的存储空间将大大减少，我们可以轻易将这 30 亿个 int 数放到内存中进行排序了。

具体的做法就是，申请一个 int 长度为 N//32 + 1 的数组。N 表示要进行查找的最大整数，我们可以遍历一轮数据获得，通过数组中的每个元素在内存在占 32 位对应表示十进制数 0-31，如何在用bit表示这个具体的数字就是将二进制中对应该自然数字的位置的值设置成1即可。

array[0] 可表示 0-31
array[1] 可表示 32-63
array[2] 可表示 64-95
…

思想相对比较简单，关键是十进制和二进制bit位需要一个 map 映射表，把10进制映射到bit位上。

（1）如何确定十进制的数值在数组的那个位置？也就是数组的下标该怎么计算。基本公式是 loc_index = (int_value <= N / 32) ，loc_index即为n对应的数组下标,什么意思呢？就是用数字去除一个32，然后取不大于结果的最大整数。例如n = 59, 则 59 / 32 = 1.84375，而不大于1.84的最大整数是1 ,因此59在a[1]中。

（2）接下来是确定一个数字在对应数组内的bit位置。利用的是求模公式；同样的数字59 bit_loc = N % 32 ，例如 n = 59, bit_loc = 59 % 32 = 27

三、python 知识回顾

python世界中10进制转换成其他进制的内置函数
# 1、十进制转二进制：bin(10) --> 输出：'0b1010' 前缀:是字符串类型 0b：表示2进制
# 2、十进制转八进制：oct(10) --> 输出：'0o12'   前缀:是字符串类型 0o：表示8进制
# 3、十进制转十六进制：hex(10) --> 输出：'0xa'  前缀:是字符串类型 0x：表示16进制
#    可以通过format函数把输出的前缀去掉，例如 format(64, 'b') --> 1000000 或者 '{:b}'.format(64) --> 1000000
#   '{:o}'.format(10) --> 12 ;'{:x}'.format(10) -->a
注意： 到bin函数返回二进制数字表示的形式是采用了负号，而不是补码的形式。通过 bin(-27 & 0b1111111111111111)

<< 运算数的各二进位全部左移若干位; >> 运算数的各二进位全部右移若干位
# print(64 << 2) --> 256
# 移动过程逻辑上解释：
#   我们通过函数 format(64, 'b') --> 1000000；其实二进制 1000000 相当于 1000000.0, 小数点位在末尾直接省略了形式；
#   我们上学时学习的时候听到过这样一种描述：数字的左移相当于小数点位的右移，所以 1000000.0 小数点位右移两位变成 100000000.0
#   再次通过二进制转换十进制 int('0b100000000', 2) --> 256
#   print(64 >> 2) --> 16
#   同样的道理 1000000.0 的数字右移相当于小数点位左移， 1000000.0 左移小数点变成了 10000.00; 我们不用函数直接用数学的逻辑来做转换
#   1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0  = 16

取模， 除法
#  1、二进制的基础上，与n取模其实就是和n-1相与 ；a%(2^n) 等价于 a&(2^n-1),而&操作比%操作具有更高的效率
#  2、“ / ” 为浮点数除法，返回浮点结果 ; “ // ” 表示整数除法，返回不大于结果的一个最大整数
#    print(10 / 3) --> 3.333333; print(10 // 3) --> 3

class BitMap2(object):
    def __init__(self):
        self.n = 5
        self.bitsize = 1 << self.n
        self.typecode = 'I'  
        self.lowerbound = 0  # 若数组中有负数，则所有数都减去最小的那个负数

    def load(self, inp):
        mini = min(inp)
        if mini < 0:
            self.lowerbound = -mini  # 如果数组中有<0的数，则所有数都要减去最小的那个负数
            inp = [i + self.lowerbound for i in inp]
        maxi = max(inp)
        # 确定数字在数组中的位置
        num_arr = math.floor(maxi / self.bitsize) + 1
        self.arr = array(self.typecode, [0] * num_arr)
        for x in inp:
            self._set(x)

    def _set(self, x):
        '''
        将x在数组中对应元置为1
        '''
        arr_idx = x >> self.n  # 元素在第几个数组中，等价于x // 2**self.n
        bit_idx = x & (self.bitsize - 1)  # 元素在相应数组中的第几个bit位，等价于x % 2**self.n
        self.arr[arr_idx] |= 1 << bit_idx  # 在这个数组里的不断的累加 2**n 最终的结果其实就是二进制转换成十进制的值

    def search(self, x):
        if self.lowerbound != 0:
            x += self.lowerbound
        arr_idx = x >> self.n
        bit_idx = x & (self.bitsize - 1)
        # 这里有问题，正常情况需要做数组长度的前置验证逻辑
        existence = True if self.arr[arr_idx] & (1 << bit_idx) else False
        return existence

    def sort(self):
        sorted_seq = []
        for arr_idx, a in enumerate(self.arr):
            for bit_idx in range(self.bitsize):
                if a & (1 << bit_idx):
                    sorted_seq.append(arr_idx * self.bitsize + bit_idx - self.lowerbound)
        return sorted_seq

if __name__ == '__main__':
    bitMap = BitMap()
    bitMap.load([3, 2, 4])
    print(bitMap.search(3))