python实现bitmap数据结构详解

bitmap是很常用的数据结构,比如用于Bloom Filter中;用于无重复整数的排序等等。bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二进制集合。对于Python来说,整数类型默认是有符号类型,所以一个整数的可用位数为31位。bitmap实现思路 bitmap是用于对每一位进行操作。举例来说,一个Python数组包含4个32位有符号整型,则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作,则要先获取到操作数组的第几个元素,再获取相应的位索引,然后执行操作。上图所示为一个32位整型,在Python中默认是有符号类型,最高位为