在处理大规模布尔数组时,我们经常面临空间和时间效率的双重挑战。
如果用普通的 boolean 数组,每个元素至少占用 1 字节,当数据量达到百万级别时,内存开销会非常可观。
而位集合(Bitset)通过将每个布尔值压缩为一个比特位,可以将空间占用降低到原来的 1/32。
以下是一个支持延迟翻转优化的高效 Bitset 实现。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
class Bitset{
private int[] set;//整形数组，用于存储位信息
private final int size;//位集合的逻辑大小（用户视角的位数）
private int zeros;//统计当前值为0的位的数量
private int ones;//统计当前值为1的位的数量
private boolean reverse;//反转标志
//构造函数
public Bitset(int n){
set = new int[(n+31)/32];
size = n;
zeros = n;
ones = 0;
reverse = false;
}
public void fix(int i){
int index = i/32;
int bit = i%32;
if(!reverse){
//正常模式reverse=false，将0改为1
if((set[index]&(1<<bit))==0){
zeros--;
ones++;
set[index]|=(1<<bit);
}
}else{
//反转模式reverse=true，将1改为0
if((set[index]&(1<<bit))!=0){
zeros--;
ones++;
set[index]^=(1<<bit);
}
}
}
public void unfix(int i){
int index = i/32;
int bit = i%32;
if(!reverse){
//正常模式reverse=false，将1改为0
if((set[index]&(1<<bit))!=0){
ones--;
zeros++;
set[index]^=(1<<bit);
}
}else{
//反转模式reverse=true，将0改为1
if((set[index]&(1<<bit))==0){
ones--;
zeros++;
set[index]|=(1<<bit);
}
}
}
//翻转所有位（0变1，1变0）
public void flip(){
reverse = !reverse;
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();
for(int i=0,k=0,number,status;i<size;k++){
number = set[k];
for(int j=0;j<32&&i<size;j++,i++){
status = (number>>j)&1;
status ^= reverse?1:0;
builder.append(status);
}
}
return builder.toString();
}
}
|