位图
题目链接
https://leetcode-cn.com/problems/design-bitset/
Bitset 是一种能以紧凑形式存储位的数据结构
Bitset(int n) : 初始化 n 个位，所有位都是 0
void fix(int i) : 将下标 i 的位上的值更新为 1
void unfix(int i) : 将下标 i 的位上的值更新为 0
void flip() : 翻转所有位的值
boolean all() : 是否所有位都是 1
boolean one() : 是否至少有一位是 1
int count() : 返回所有位中 1 的数量
String toString() : 返回所有位的状态
存储思路
int 是 32 位，每一位有 0 和 1 两种状态，这两种状态来表示对应的数是否存在，大大的节省了存储空间
例如 0 这个数，有 32 位，其二进制位可以表示 0 - 31 这 32 个数，若需要表示 5 是否存在，只需要看 0 这个二进制位中的第五位是 0 还是 1
对于一个 int 类型的数，x / 32 表示哪个数记录了其是否存在的状态，x % 32 表示在 x / 32 这个数中的第几位表示 x 是否存在的状态
若一个数存在，则二进制位的状态为 1，若不存在，二进制位的状态为 0
💡 Tip
为了使用位运算实现某些操作，根据二进制位的特点，从右到左依次变大，取最右边的位为第 1 位
初始化位图
思路分析
若 a，b 都是非负数，且 a = k * b + 余数，则 a / b 向上取整可以写成（a + b - 1） / b
如果 a 整除 b，那么 a 加上 b - 1 这个余数也不会影响最后的结果，因为要向上取整
如果 a 不整除 b，那么 a 加上 b - 1 这个余数是为了增大分母，达到向上取整的效果
代码实现
java
// 使用时 num 不要超过初始化的大小
public static class Bitset {
public int[] set;
// n个数字 : 0 ~ n-1
public Bitset(int n) {
// a / b如果结果想向上取整，可以写成 : （a + b - 1） / b = （n + 32 - 1） / 32
// 前提是 a 和 b 都是非负数
set = new int[(n + 31) / 32];
}
}add 添加
思路分析
根据位图的存储思路，某一位存在，只需要计算出该数在哪个数的哪个二进制位，将对应的二进制位设置为 1 即可
代码实现
java
public void add(int num) {
set[num / 32] |= 1 << (num % 32);
}remove 移除
思路分析
原来的二进制位是 1，现在需要移除，则该二进制需要设置为 0，可以使用 & 运算实现，然而为了消除 & 运算对其它位的影响，可以对 & 的数取反，保留原有二进位中的 1
代码实现
java
public void remove(int num) {
set[num / 32] &= ~(1 << (num % 32));
}reverse 反转状态
思路分析
这个操作的目的是反转一个数的状态，存在 --> 不存在，不存在 --> 存在
在二进制位中即 0 --> 1，1 --> 0
可以使用异或实现，即不同位为 1，相同为 0
代码实现
java
public void reverse(int num) {
set[num / 32] ^= 1 << (num % 32);
}contains 是否存在
思路分析
存不存在，就看该数所在的二进制状态是否为 1 即可，可以通过 & 运算实现，同为 1 为 1，否则为 0
代码实现
java
public boolean contains(int num) {
// 原始是从最右边为初始位，向左开始记位
// set[num / 32] >> (num % 32) 就是把对应的二进制位移到了最低位（初始位）
return ((set[num / 32] >> (num % 32)) & 1) == 1; // 这是先移动 bit 位去跟 1 & 运算的思路
// 第二种写法：(set[index] & (1 << bit)) == 1 这是先移动 1 去跟 bit 位 & 运算的思路
}测试代码
java
package class032;
import java.util.HashSet;
// 位图的实现
// Bitset(int size)
// void add(int num)
// void remove(int num)
// void reverse(int num)
// boolean contains(int num)
public class Code01_Bitset {
// 位图的实现
// 使用时num不要超过初始化的大小
public static class Bitset {
public int[] set;
// n个数字 : 0~n-1
public Bitset(int n) {
// a/b如果结果想向上取整，可以写成 : (a+b-1)/b
// 前提是a和b都是非负数
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) {
int n = 1000;
int testTimes = 10000;
System.out.println("测试开始");
// 实现的位图结构
Bitset bitSet = new Bitset(n);
// 直接用HashSet做对比测试
HashSet<Integer> hashSet = new HashSet<>();
System.out.println("调用阶段开始");
for (int i = 0; i < testTimes; i++) {
double decide = Math.random();
// number -> 0 ~ n-1，等概率得到
int number = (int) (Math.random() * n);
if (decide < 0.333) {
bitSet.add(number);
hashSet.add(number);
} else if (decide < 0.666) {
bitSet.remove(number);
hashSet.remove(number);
} else {
bitSet.reverse(number);
if (hashSet.contains(number)) {
hashSet.remove(number);
} else {
hashSet.add(number);
}
}
}
System.out.println("调用阶段结束");
System.out.println("验证阶段开始");
for (int i = 0; i < n; i++) {
if (bitSet.contains(i) != hashSet.contains(i)) {
System.out.println("出错了!");
}
}
System.out.println("验证阶段结束");
System.out.println("测试结束");
}
}代码实现
java
// 位图的实现
// Bitset是一种能以紧凑形式存储位的数据结构
// Bitset(int n) : 初始化n个位，所有位都是0
// void fix(int i) : 将下标i的位上的值更新为1
// void unfix(int i) : 将下标i的位上的值更新为0
// void flip() : 翻转所有位的值
// boolean all() : 是否所有位都是1
// boolean one() : 是否至少有一位是1
// int count() : 返回所有位中1的数量
// String toString() : 返回所有位的状态
class Bitset {
private int[] set;
// size 的含义如下
// 假设需要表示 0 - n 个数是否存在，则 size 表示 n 个二进制位状态
// int 是 32 位，即每 32 位可以用一个整数表示
// 例如 0 - 31 这些数是否出现仅用一个 int 类型的数的二进制位就可以表示
private final int size;
// 统计位图中 0 的个数
private int zeros;
// 统计位图中 1 的个数
private int ones;
// 所有位是否经过了反转
// reverse = true --> 0 表示存在，1 表示不存在
// 巧妙的设计，通过 reverse 一个变量控制是否反转，而不用单独去变化每一位
private boolean reverse;
public Bitset(int n) {
// a / b 向上取整写法：（a + b - 1） / b = （n + 32 - 1） / 32
set = new int[(n + 31) / 32];
size = n;
zeros = n;
// 初始位图中所有位都是 0，有 0 个 1
ones = 0;
reverse = false;
}
// 把 i 这个数字加入到位图，即设置二进制状态位为 1
public void fix(int i) {
int index = i / 32;
int bit = i % 32;
// 位图维持原始含义，0 --> 不存在，1 --> 存在
if (reverse == false) {
if ((set[index] & (1 << bit)) == 0) {
// 一个新的数字进来， 0 的数量减减，1 的数量加加
zeros--;
ones++;
// 将对应的二进制位设置为 1（0 --> 1）
set[index] |= (1 << bit);
}
} else {
// 位图所有位的状态翻转了，0 --> 存在，1 --> 不存在
if ((set[index] & (1 << bit)) != 0) {
// 一个新的数字进来， 0 的数量减减，1 的数量加加
zeros--;
ones++;
// 将对应的二进制位设置为 0（1 --> 0
set[index] ^= (1 << bit);
}
}
}
// 把 i 这个数字从位图中移除，即设置二进制状态位为 0
public void unfix(int i) {
int index = i / 32;
int bit = i % 32;
if (reverse == false) {
if ((set[index] & (1 << bit)) != 0) {
ones--;
zeros++;
set[index] ^= (1 << bit);
}
} else {
if ((set[index] & (1 << bit)) == 0) {
ones--;
zeros++;
set[index] |= (1 << bit);
}
}
}
// 翻转所有位的值，核心是通过 reverse 的状态控制值的变化
public void flip() {
reverse = !reverse;
// 位图的状态反转，0 的数量和 1 的数量也要反转，交换两个数的数量
int tmp = zeros;
zeros = ones;
ones = tmp;
}
// 判断所有位是否都是 1
public boolean all() {
return ones == size;
}
// 判断是否至少有一位是 1
public boolean one() {
return ones > 0;
}
// 返回所有位中 1 的数量
public int count() {
return ones;
}
// 返回所有位当前的状态
public String toString() {
StringBuilder builder = new StringBuilder();
// size 的含义如下
// 假设需要表示 0 - n 个数是否存在，则 size 表示 n 个二进制位状态
// int 是 32 位，即每 32 位可以用一个整数表示
// 例如 0 - 31 这些数是否出现仅用一个 int 类型的数的二进制位就可以表示
// 外层的 i < size 这个条件无实际意义，这么写是因为 for 循环的语法需要终止条件
for (int i = 0, k = 0, number, status; i < size; k++) {
// 拿到每一个整数
number = set[k];
// 取出当前数的每一个二进制位，通过 reverse 的状态控制取值
for (int j = 0; j < 32 && i < size; j++, i++) {
status = (number >> j) & 1;
// 如果没有反转，reverse ? 1 : 0 的结果是 0
// 则 status ^= 0 表示原来的 0 维持 0，原来的 1 维持 1
// 换一种角度理解，异或就是无无进位相加，有性质 n ^ 0 = n
// 如果反转了，取值相反
status ^= reverse ? 1 : 0;
builder.append(status);
}
}
return builder.toString();
}
}