bitmap是很常用的数据结构，比如用于Bloom Filter中；用于无重复整数的排序等等。bitmap通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。对于Python来说，整数类型默认是有符号类型，所以一个整数的可用位数为31位。bitmap实现思路 bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。上图所示为一个32位整型，在Python中默认是有符号类型，最高位为符号位，bitmap不能使用它。左边是高位，右边是低位，最低位为第0位。 bitmap是用于对每一位进行操作。举例来说，一个Python数组包含4个32位有符号整型，则总共可用位为4 * 31 = 124位。如果要在第90个二进制位上操作，则要先获取到操作数组的第几个元素，再获取相应的位索引，然后执行操作。 初始化bitmap 首先需要初始化bitmap。拿90这个整数来说，因为单个整型只能使用31位，所以90除以31并向上取整则可得知需要几个数组元素。代码如下： 计算在数组中的索引 计算在数组中的索引其实是跟之前计算数组大小是一样的。只不过之前是对最大数计算，现在换成任一需要存储的整数。但是有一点不同，计算在数组中的索引是向下取整，所以需要修改calcElemIndex方法的实现。代码改为如下： 所以获取最大整数很重要，否则有可能创建的数组容纳不下某些数据。 计算在数组元素中的位索引 数组元素中的位索引可以通过取模运算来得到。令需存储的整数跟31取模即可得到位索引。代码改为如下： 别忘了是从第0位算起哦。 置1操作 二进制位默认是0，将某位置1则表示在此位存储了数据。代码改为如下： 因为从第0位算起，所以如需要存储0，则需要把第0位置1。 清0操作 将某位置0，也即丢弃已存储的数据。代码如下： 清0和置1是互反操作。 测试某位是否为1 判断某位是否为1是为了取出之前所存储的数据。代码如下： 接下来实现一个不重复数组的排序。已知一个无序非负整数数组的最大元素为879，请对其自然排序。代码如下： bitmap实现了，则利用其进行排序就非常简单了。其它语言也同样可以实现bitmap，但对于静态类型语言来说，比如C/Golang这样的语言，因为可以直接声明无符号整型，所以可用位就变成32位，只需将上述代码中的31改成32即可，这点请大家注意。 您可能感兴趣的文章:Python集合魔法解锁数据去重技巧应用实例Python列表去重的几种方法整理python列表去重的5种常见方法实例Python数据分析之 Pandas Dataframe合并和去重操作Python教程pandas数据分析去重复值python BitMap算法处理20亿随机整数去重