https://leetcode.com/problems/design-bitset/
bitset的实现，可能和自己想的不一样

个人解答

  1. class Bitset:
  3.     def __init__(self, size: int):
  4.         self.setBits = set()
  5.         self.size = size
  6.         self.isFlip = False
  8.     def fix(self, idx: int) -> None:
  9.         if not self.isFlip:
  10.             self.setBits.add(idx)
  11.         else:
  12.             self.setBits.discard(idx)
  15.     def unfix(self, idx: int) -> None:
  16.         if not self.isFlip:
  17.             self.setBits.discard(idx)
  18.         else:
  19.             self.setBits.add(idx)        
  21.     def flip(self) -> None:
  22.         self.isFlip = not self.isFlip
  25.     def all(self) -> bool:
  26.         if not self.isFlip:
  27.             return len(self.setBits) == self.size
  28.         else:
  29.             return len(self.setBits) == 0
  32.     def one(self) -> bool:
  33.         if not self.isFlip:
  34.             return len(self.setBits) > 0
  35.         else:
  36.             return len(self.setBits) < self.size       
  38.     def count(self) -> int:
  39.         if not self.isFlip:
  40.             return len(self.setBits)
  41.         else:
  42.             return self.size - len(self.setBits)
  45.     def toString(self) -> str:
  46.         if not self.isFlip:
  47.             return ''.join(['1' if (i in self.setBits) else '0' for i in range(self.size)])
  48.         else:
  49.             return ''.join(['0' if (i in self.setBits) else '1' for i in range(self.size)])

题目分析

自己本以为是位运算操作，但发现反而更慢。
不过位运算也需要一些注意的地方：

  • count操作需要O(1)的复杂度，因此不能简单的bin(x).count('1')，可以采用内置的bit_count()函数，也可以在每个操作的过程中记录

  • toString中，可以学习一些字符串格式化的方法 ```python class Bitset:

    def init(self, size: int):

    1.   self.x = 0
    2.   self.size = size
    3.   self.cnt = 0
  1. def fix(self, idx: int) -> None:
  2.     if (self.x & (1 << idx)) == 0:
  3.         self.cnt += 1
  5.     self.x |= 1 << idx
  8. def unfix(self, idx: int) -> None:
  9.     if (self.x & (1 << idx)) != 0:
  10.         self.cnt -= 1
  12.     self.x &= ((1 << self.size) - 1) - (1 << idx)
  14. def flip(self) -> None:
  15.     self.cnt = self.size - self.cnt
  17.     self.x ^= ((1 << self.size) - 1)
  20. def all(self) -> bool:
  21.     return self.x == ((1 << self.size) - 1)
  24. def one(self) -> bool:
  25.     return self.x != 0
  28. def count(self) -> int:
  29.     # return bin(self.x).count('1')
  30.     # return self.x.bit_count()
  31.     return self.cnt
  34. def toString(self) -> str:
  35.     return f'{self.x:0b}'.zfill(self.size)[::-1]

``` 然而，看了题解之后，发现效率更高的方法是采用set来实现。
出于题目的特性，其它的都要保证O(1)的操作，toString可以不用管，那么讲道理用集合的方式更靠谱一点。
而且，python语言帮忙处理了很长的数，但其它的语言还要考虑越界等问题，所以set的方式实现是更合理的。