bitmap是很常用的數據結構，比如用于Bloom Filter中；用于無重復整數的排序等等。bitmap通?；跀到M來實現，數組中每個元素可以看成是一系列二進制數，所有元素組成更大的二進制集合。對于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并向上取整則可得知需要幾個數組元素。代碼如下：

代碼如下:
#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
 def __init__(self, max):
  self.size = int((max + 31 - 1) / 31) #向上取整

if __name__ == '__main__':
 bitmap = Bitmap(90)
 print '需要 %d 個元素。' % bitmap.size

代碼如下:
$ python bitmap.py
需要 3 個元素。

計算在數組中的索引

計算在數組中的索引其實是跟之前計算數組大小是一樣的。只不過之前是對最大數計算，現在換成任一需要存儲的整數。但是有一點不同，計算在數組中的索引是向下取整，所以需要修改calcElemIndex方法的實現。代碼改為如下：

代碼如下:
#!/usr/bin/env python
#coding: utf8

class Bitmap(object):
 def __init__(self, max):
  self.size  = self.calcElemIndex(max, True)
  self.array = [0 for i in range(self.size)]

 def calcElemIndex(self, num, up=False):
  '''up為True則為向上取整, 否則為向下取整'''
  if up:
   return int((num + 31 - 1) / 31) #向上取整
  return num / 31

if __name__ == '__main__':
 bitmap = Bitmap(90)
 print '數組需要 %d 個元素。' % bitmap.size
 print '47 應存儲在第 %d 個數組元素上。' % bitmap.calcElemIndex(47)

代碼如下:
$ python bitmap.py
數組需要 3 個元素。
47 應存儲在第 1 個數組元素上。

所以獲取最大整數很重要，否則有可能創建的數組容納不下某些數據。