自己实现：好丑啊

  1. class BitMap():
  2.     def __init__(self, max):
  3.         self.size = self.calculate_index(max)
  4.         self.array = [0 for i in range(self.size + 1)]
  5.     def calculate_index(self, num):
  6.         return (num//31)
  7.     def calculate_elem(self, num):
  8.         return (num%31)
  9.     def insert_bit(self, num):
  10.         index = self.calculate_index(num)
  11.         elem = self.calculate_elem(num)
  12.         now_index = self.array[index]
  13.         self.array[index] = now_index | (1<<elem)
  14.     def test_bit(self, num):
  15.         index = self.calculate_index(num)
  16.         elem = self.calculate_elem(num)
  17.         if self.array[index] & (1<<elem):
  18.             return True
  19.         return False
  20.     def sort(self):
  21.         list1 = []
  22.         for i in range(self.size + 1):
  23.             if self.array[i]:
  24.                 x = bin(self.array[i])[::-1]
  25.                 n = len(str(x))
  26.                 print(x, n)
  27.                 for j in range(n-2):
  28.                     print(x[j])
  29.                     if x[j] == '1':
  30.                         list1.append(j+(2**5-1)*i)
  31.                         print(list1)
  32.         self.array = list1
  33.     def delete_bit(self, num):
  34.         if self.test_bit(num):
  35.             print(num)
  36.             index = self.calculate_index(num)
  37.             elem = self.calculate_elem(num)
  38.             print(self.array[index], elem)
  39.             self.array[index] = self.array[index] & (~(1<<elem))
  40. suffle_array = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
  41. max = 879
  42. b = BitMap(max)
  43. for num in suffle_array:
  44.     # print(num)
  45.     b.insert_bit(num)
  46. print(b.array)
  47. # c = b.test_bit(15)
  48. # print(c)
  49. b.delete_bit(35)
  50. print(b.array)

抄袭版本：

  1. #!/usr/bin/env python
  2. #coding: utf8
  3. # class Bitmap(object):
  4. #   def __init__(self, max):
  5. #       self.size  = self.calcElemIndex(max, True)
  6. #       self.array = [0 for i in range(self.size)]
  7. #   def calcElemIndex(self, num, up=False):
  8. #       '''up为True则为向上取整, 否则为向下取整'''
  9. #       if up:
  10. #           return int((num + 31 - 1) / 31) #向上取整
  11. #       return int(num / 31)
  12. #   def calcBitIndex(self, num):
  13. #       return num % 31
  14. #   def set(self, num):
  15. #       elemIndex = self.calcElemIndex(num)
  16. #       byteIndex = self.calcBitIndex(num)
  17. #       elem = self.array[elemIndex]
  18. #       self.array[elemIndex] = elem | (1 << byteIndex)
  19. #   def clean(self, i):
  20. #       elemIndex = self.calcElemIndex(i)
  21. #       byteIndex = self.calcBitIndex(i)
  22. #       elem = self.array[elemIndex]
  23. #       self.array[elemIndex] = elem & (~(1 << byteIndex))
  24. #   def test(self, i):
  25. #       elemIndex = self.calcElemIndex(i)
  26. #       byteIndex = self.calcBitIndex(i)
  27. #       if self.array[elemIndex] & (1 << byteIndex):
  28. #           return True
  29. #       return False
  30. # if __name__ == '__main__':
  31. #   MAX = 879
  32. #   suffle_array = [45, 2, 78, 35, 67, 90, 879, 0, 340, 123, 46]
  33. #   result = []
  34. #   from ipdb import set_trace
  35. #   set_trace()
  36. #   bitmap = Bitmap(MAX)
  37. #   for num in suffle_array:
  38. #       print(bitmap.array)
  39. #       print(num)
  40. #       bitmap.set(num)
  42. #   for i in range(MAX + 1):
  43. #       if bitmap.test(i):
  44. #           result.append(i)
  45. #   print('原始数组为:    %s' % suffle_array)
  46. #   print('排序后的数组为: %s' % result)