算法【位图】

特别提醒：Python同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题。比如：

(n << shift_amount) & 0xFFFFFFFF

一、位图原理

其实就是用bit组成的数组来存放值，用bit状态1、0代表存在、不存在，取值和存值操作都用位运算。限制是必须为连续范围且不能过大。好处是极大的节省空间，因为1个数字只占用1个bit的空间。

二、位图的实现

一个位图有以下几个函数：

// 初始化位图 只支持0~n-1所有数字的增删改查 Bitset(int n); // 把num加入到位图 void add(int num); // 把num从位图中删除 void remove(int num); // 如果位图里没有num 就加入  如果位图里有num 就删除 void reverse(int num); // 查询num是否在位图中 bool contains(int num);

代码如下。

class Bitset { public:     int *arr;     Bitset(int n);     ~Bitset();     void add(int num);     void remove(int num);     void reverse(int num);     bool contains(int num); };  Bitset::Bitset(int n) {     // 数组大小为n/32向上取整 可写成(n+31)/32     arr = new int[(n+31)/32]; }  Bitset::~Bitset() {     delete [] arr; }  void Bitset::add(int num){     arr[num/32] |= (1 << (num % 32)); }  void Bitset::remove(int num){     arr[num/32] &= ~(1 << (num % 32)); }  bool Bitset::contains(int num){     return ~((arr[num/32] & (1 << (num % 32))) == 0); }  void Bitset::reverse(int num){     if(contains(num)){         remove(num);     }else{         add(num);     } }

由于是用位代表一个数是否存在，所以一个int可代表32个数，则需要的int个数为n/32向上取整。对此可用(a + b -1)/b为a/b的向上取整来计算。对于一个数num，它被哪一个int代表由num/32得到下标，而具体的位则是由num%32得到。add方法中得到具体位数直接或进去，remove方法中得到具体的位数直接与进去。

下面有一个相关测试可以检验一下，按照题目要求修改部分即可。

测试链接：https://leetcode-cn.com/problems/design-bitset/

代码如下。

class Bitset { public:     // 根据数据量提前申请     int arr[3126] = {0};     // 是否翻转 false为没翻转 true为翻转     bool f;     // 记录1的个数     int cnt;     // 能代表多少个数     int nums;     Bitset(int size) {         f = false;         cnt = 0;         nums = size;     }      void fix(int idx) {         if(!f){             if(((arr[idx/32] >> (idx % 32)) & 1) == 0){                 arr[idx/32] |= (1 << (idx % 32));                 cnt++;             }         }else{             if(((arr[idx/32] >> (idx % 32)) & 1) == 1){                 arr[idx/32] &= ~(1 << (idx % 32));                 cnt++;             }         }     }          void unfix(int idx) {         if(!f){             if(((arr[idx/32] >> (idx % 32)) & 1) == 1){                 arr[idx/32] &= ~(1 << (idx % 32));                 cnt--;             }         }else{             if(((arr[idx/32] >> (idx % 32)) & 1) == 0){                 arr[idx/32] |= (1 << (idx % 32));                 cnt--;             }         }     }          void flip() {         f = !f;         cnt = nums - cnt;     }          bool all() {         return cnt == nums;     }          bool one() {         return cnt != 0;     }          int count() {         return cnt;     }          string toString() {         string s = "";         for(int i = 0;i < (nums + 31)/32;++i){             int cons = nums - i * 32 < 32 ? nums - i * 32 : 32;             for(int j = 0;j < cons;++j){                 if((!f && ((arr[i] >> j) & 1) == 1) || (f && ((arr[i] >> j) & 1) == 0)){                     s += '1';                 }else{                     s += '0';                 }             }         }         return s;     } };

其中，翻转使用一个变量代表，不需要每次遍历位图实现翻转。fix和unfix方法均分为翻转和未翻转两种情况。