位图算法

位图算法(bitMap)

内存中连续的二进制位(bit) 所组成的数据结构,主要用于大量整数数据去重查询操作

举例

要插入 1,2,3,4 的数字、先在内存中申请长度为 10 位的 bitMap,所有 bit 位分别对应 0 ~ 9 的整型值。

判断 4 是否在 bitMap 中
我们知道,在二进制中,0 代表 false 、1 true
将上面的位图用二进制表示:
将其做与(&)运算:0000011110 & 0000010000 = 0000010000

添加值到 bitMap 中
即并集; 做或(|)运算: 0000001110 | 0000010000 = 0000011110

不包括 4 的值
做异或(^)运算:0000011110 ^ 0000010000 = 0000001110


删除位图中值
对需要删的数做非(~)运算:~0000010000 = 1111101111
再进行与运算:0000011110 & 1111101111 = 0000001110

代码实现

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
public class Mybitmap {

//每一个word是一个long类型元素,对应64位二进制
private final long[] words;
//bitmap的位数大小
private final int size;

public Mybitmap(int size) {
this.size = size;
this.words = new long[(getWordIndex(size-1) + 1)];
}

/**
* 判断bitmap某一位的状态
* @param bitIndex 位图的第bitIndex位
*/
public boolean getBit(int bitIndex) {
if(bitIndex<0 || bitIndex>size-1){
throw new IndexOutOfBoundsException("超过bitmap有效范围");
}
int wordIndex = getWordIndex(bitIndex);
return (words[wordIndex] & (1L << bitIndex)) != 0;
}

/**
* 把bitmap某一位设为真
* @param bitIndex 位图的第bitIndex位
*/
public void setBit(int bitIndex) {
if(bitIndex<0 || bitIndex>size-1){
throw new IndexOutOfBoundsException("超过bitmap有效范围");
}
int wordIndex = getWordIndex(bitIndex);
words[wordIndex] |= (1L << bitIndex);
}

/**
* 把bitmap某一位设为假
* @param bitIndex 位图的第bitIndex位
*/
public void removeBit(int bitIndex) {
if(bitIndex<0 || bitIndex>size-1){
throw new IndexOutOfBoundsException("超过bitmap有效范围");
}
int wordIndex = getWordIndex(bitIndex);
words[wordIndex] &= (~(1L << bitIndex));
}

/**
* 定位bitmap某一位所对应的word
* @param bitIndex 位图的第bitIndex位
*/
private int getWordIndex(int bitIndex) {
//右移6位,相当于除以64
return bitIndex >> 6;
}

public static void main(String[] args) {
Mybitmap bitMap = new Mybitmap(128);
bitMap.setBit(1);
bitMap.setBit(2);
bitMap.setBit(3);
bitMap.setBit(4);
System.out.println(bitMap.getBit(1));
System.out.println(bitMap.getBit(2));
bitMap.removeBit(2);
System.out.println(bitMap.getBit(2));
System.out.println(bitMap.getBit(3));
System.out.println(bitMap.getBit(4));
}
}