1
// 位图的实现
2
// Bitset(int size)
3
// void add(int num)
4
// void remove(int num)
5
// void reverse(int num)
6
// boolean contains(int num)
7
public class Code01_Bitset {
8

9
  // 位图的实现
10
  // 使用时num不要超过初始化的大小
11
  public static class Bitset {
12
    public int[] set;
13

14
    // n个数字 : 0~n-1
15
    public Bitset(int n) {
16
      // a/b如果结果想向上取整，可以写成 : (a+b-1)/b
17
      // 前提是a和b都是非负数
18
      set = new int[(n + 31) / 32];
19
    }
20

21
    public void add(int num) {
22
      set[num / 32] |= 1 << (num % 32);
23
    }
24

25
    public void remove(int num) {
26
      set[num / 32] &= ~(1 << (num % 32));
27
    }
28

29
    public void reverse(int num) {
30
      set[num / 32] ^= 1 << (num % 32);
31
    }
32

33
    public boolean contains(int num) {
34
      return ((set[num / 32] >> (num % 32)) & 1) == 1;
35
    }
36

37
  }
38

39
  // 对数器测试
40
  public static void main(String[] args) {
41
    int n = 1000;
42
    int testTimes = 10000;
43
    System.out.println("测试开始");
44
    // 实现的位图结构
45
    Bitset bitSet = new Bitset(n);
46
    // 直接用HashSet做对比测试
47
    HashSet<Integer> hashSet = new HashSet<>();
48
    System.out.println("调用阶段开始");
49
    for (int i = 0; i < testTimes; i++) {
50
      double decide = Math.random();
51
      // number -> 0 ~ n-1，等概率得到
52
      int number = (int) (Math.random() * n);
53
      if (decide < 0.333) {
54
        bitSet.add(number);
55
        hashSet.add(number);
56
      } else if (decide < 0.666) {
57
        bitSet.remove(number);
58
        hashSet.remove(number);
59
      } else {
60
        bitSet.reverse(number);
61
        if (hashSet.contains(number)) {
62
          hashSet.remove(number);
63
        } else {
64
          hashSet.add(number);
65
        }
66
      }
67
    }
68
    System.out.println("调用阶段结束");
69
    System.out.println("验证阶段开始");
70
    for (int i = 0; i < n; i++) {
71
      if (bitSet.contains(i) != hashSet.contains(i)) {
72
        System.out.println("出错了!");
73
      }
74
    }
75
    System.out.println("验证阶段结束");
76
    System.out.println("测试结束");
77
  }
78

79
}