-
Notifications
You must be signed in to change notification settings - Fork 133
/
Code02_DesignBitset.java
95 lines (83 loc) · 1.81 KB
/
Code02_DesignBitset.java
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
package class_2022_02_2_week;
// 测试链接 : https://leetcode-cn.com/problems/design-bitset/
public class Code02_DesignBitset {
class Bitset {
// size int 32
// size / 32 向上取整
private int[] bits;
private final int size;
private int zeros;
private int ones;
private boolean reverse;
public Bitset(int n) {
bits = new int[(n + 31) / 32];
size = n;
zeros = n;
ones = 0;
reverse = false;
}
// 把idx位置的状态,如果是0,变成1;如果是1,没有变化!
public void fix(int idx) {
int index = idx / 32;
int bit = idx % 32;
if (!reverse) {
if ((bits[index] & (1 << bit)) == 0) {
zeros--;
ones++;
bits[index] |= (1 << bit);
}
} else {
if ((bits[index] & (1 << bit)) != 0) {
zeros--;
ones++;
bits[index] ^= (1 << bit);
}
}
}
// 1 > 0
public void unfix(int idx) {
int index = idx / 32;
int bit = idx % 32;
if (!reverse) {
if ((bits[index] & (1 << bit)) != 0) {
ones--;
zeros++;
bits[index] ^= (1 << bit);
}
} else {
if ((bits[index] & (1 << bit)) == 0) {
ones--;
zeros++;
bits[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位是1
public boolean one() {
return ones > 0;
}
// 返回1的数量!
public int count() {
return ones;
}
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < size; i++) {
int status = bits[i / 32] & (1 << (i % 32));
builder.append(reverse ? (status == 0 ? '1' : '0') : (status == 0 ? '0' : '1'));
}
return builder.toString();
}
}
}