《位运算：位图》

前置知识

前置: 位运算和二进制的知识
周末摸鱼时刻…

位图引入

怎么说呢？从哈希表开始引入吧。
我们知道哈希表支持快速查询操作。
有这样一个问题，比如 我要查询[0,1e8]这个区间某个数是否出现。
显然哈希表可以解决这个问题（没超出内存容量）， 但内存开销巨大。
Java中， 1个int占32字节。遍历这个区间上的所有出现过的数， 最坏情况就是（1+1e8） * 32的数量级， 换算成GB。 好的内存也就在16GB的大小范围， 显然哈希表的做法无疑是对内存的沉重打击。
有没有一种专门的数据结构可以减少内存空间也能做到快速查询， 那就是位图（也称位集）

总结：

• 哈希表

• 优点：
  哈希表可以快速存储和查询数据。连续区间上也可以查询某个数是否存在 查询时间是$O(1)$。

• 问题：

  • 内存开销大：
    上述举的例子内存还勉强够用。如果是存储较多的区间或者在更大的范围（如 [0, 1e10]）内查询，直接出错误了。Exception in thread "main" java.lang.OutOfMemoryError: Java heap space...

    哈希表利用内存的效率低。存储稀疏数据

位图原理

位图是专门解决连续区间且整数数字是否出现过的数据结构。 它是由一个bit位表示状态， 0表示不存在，1表示存在。它利用位运算实现极高的空间使用率。
本质也是一种映射思想：
比如1个int就可以充当32长度的bit数组，
00000000 00000000 00000000 00000000 好的， 一共32位。
那么这个就适用于[0,31]范围整数的查询。
上面的位序列，从右往左看， 建立数字与bit数组的下标关系
0->bit数组的第一个下标0处
1->bit数组的第二个下标1处
2->bit数组的第三个下标2处。
…
提供的api呢？
比如我要查询15是否出现
boolean contains(int num), 那么调用这个接口函数，通过<<移位运算符取得对应位的状态， 若是1返回true， 否则返回false.

实现的接口和大致思想

Bitset(int n):初始化位图大小， 它可以支持[0,n-1]区间上数字操作
void add(int num): 把数字num添加进位图中。将其在位图中映射处的位置位标记为1.
void remove(int num): 把num从位图中删除。将其在位图中映射处的位置位标记为0.
void reverse(int num):反转操作， 若位图存在这个数字那么删除它， 否则就添加进去。
boolean contains(int num): 查询num是否在位图中。

BitSet好比Java中set，它支持查询整数数字是否存在， 而不是一种键值对关系。
编程语言中没有bit类型的数组， 因为字节是最小可寻址单位。 但好在我们可以通过其他类型的数组，比如int数组来模拟实现出一个bit数组。
Java中提供了BitSet的集合类， 就是Java内置的位集。

实现及其对数测试技巧

实现一个BitSet类
通过一个int数组实现
每一个int是32个位， 我们要对每个数字进行分区。
比如一个int[] set，100这个数字应该首先定位在数组的那个下标上， 比如100 / 32 == 3， 说明100在set数组的3下标区域内， 然后通过移位操作找到它确定的位。

如何通过int数组找到数组位的位置， 然后操作位（添加删除或者）
初始化的细节
比如给一个[0,100]区间的数组区间， 应该开一个$\lceil 100/32\rceil$大小的数组。
意思上set数组大小是n/32向上取整的结果。
可以通过向上取整公式(a+b-1)/b

add：
add操作是修改num在set对应的位为1.
set[num/32]是定位对应int区域， 然后通过(1 << (num % 32))移动具体位数.
若原先是1则保持不变， 若为0则修改为1 。 可以通过|实现

remove：
set[num/32] &= ~(1 << (num % 32)); 还是先定位， 然后& 0来将位中的1修改为0。

reverse：
反转对应位置的位， 1->0 , 0->1 。
根据异或是无进位加法的特点， ^ 1即可。1+1=0, 0+1=1二进制加法。
return ((set[num/32] >> (num % 32)) & 1) == 1;

contains:
((set[num/32] >> (num % 32)) & 1) == 1; 判断当前num数字是否存在， 就是找到其在bitset对应的位。
set[num/32]->找到对应区域， 对这个值进行右移num % 32， 然后通过& 1把位取出来， 判断是否为1。

leetcode有一道线上测试OJ，但给的条件太苛刻了， 比较有难度。
所以可以对照哈希表的解法，写一下对数器测试。
下面的类里有测试的main函数， 是根据哈希表解法和位图的解法对照的结果。

public class BitSet {public int[] set ;public BitSet(int n){set = new int[(n+31)/32];}public void add(int num){set[num/32] |= 1 << (num % 32);}public void remove(int num){set[num/32] &= ~(1 << (num % 32));}public void reverse(int num){set[num/32] ^= 1 << (num % 32);}public boolean contains(int num){return ((set[num/32] >> (num % 32)) & 1) == 1;}//哈希表写法与位图写法进行对数验证public static void main(String[] args) {//生成多大的右边界范围//范围是[0,n)int n = 1000;int testTimes = 10000;//测试10000次System.out.println("Testing begins...");// Initialize BitSet and HashSetBitSet bitset = new BitSet(n);var hashset = new HashSet<Integer>(n);System.out.println("等概率随机调用3种方法");for(int i=0;i<testTimes;i++){double decide = Math.random();int num = (int)(Math.random() * n);if(decide < 1.0/3){bitset.add(num);hashset.add(num);}else if(decide < 2.0/3){bitset.remove(num);hashset.remove(num);}else{bitset.reverse(num);if(hashset.contains(num)){hashset.remove(num);}else{hashset.add(num);}}}System.out.println("验证开始");for(int i=0;i<n;i++){if(bitset.contains(i)!=hashset.contains(i)){System.out.printf("第%d次: 出错了！\n", i);}}System.out.println("结束");}
}

leetcode上在线OJ测试

设计位集

class Bitset {public int[] set;public final int n;//位集总的个数public int exists;//不存在个数public int noexists;//存在个数public boolean reverse;//反转状态public Bitset(int size) {n = size;set = new int[(n+31)/32];noexists = n;exists = 0;reverse = false;}public void fix(int idx) {int index = idx / 32;int bit = idx % 32;//不存在->存在if(!reverse){//0表示不存在//1表示存在if((set[index] & (1 << bit)) == 0){exists++;noexists--;//0->1set[index] |= (1<<bit);}}else{//1表示不存在//0表示存在if((set[index] & (1 << bit)) != 0){exists++;noexists--;//1->0 ， ^ 解决set[index] ^= (1 << bit);}}}public void unfix(int idx) {int index = idx / 32;int bit = idx % 32;//存在->不存在if(!reverse){//0表示不存在//1表示存在if((set[index] & (1 << bit)) != 0){exists--;noexists++;//1->0set[index] ^= (1<<bit);}}else{//1表示不存在//0表示存在if((set[index] & (1 << bit)) == 0){exists--;noexists++;//0->1set[index] |= (1 << bit);}}}public void flip() {reverse = !reverse;int tmp = exists;exists = noexists;noexists = tmp;}public boolean all() {return exists == n;}public boolean one() {return exists != 0;}public int count() {return exists;}public String toString() {char[] result = new char[n];for (int i = 0, k = 0, number, status; i < n; k++) {number = set[k];for (int j = 0; j < 32 && i < n; j++, i++) {status = (number >> j) & 1; // 获取当前位status ^= reverse ? 1 : 0; // 考虑反转逻辑result[i] = (char) ('0' + status); // 转换为字符}}return String.valueOf(result);}
}