由于 Go 没有现成的 bitmap ，要使用时需要自己造一个。我们可以使用多个 uint 来组装一个 bitmap，同时为了节约空间，避免浪费，可以使用 uint8。
代码比较简单，如下：
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package main
import (
"fmt"
)
type BitMap struct {
data []byte
length uint64
}
// 创建 bitmap 对象，length 为 bitmap 长度
func NewBitMap(length uint64) *BitMap {
// 使用 byteCnt := (length + 7) / 8 更直接，但可能出现超出 uint64范围的情况
byteCnt := length / 8
if length%8 != 0 {
byteCnt += 1
}
return &BitMap{data: make([]byte, byteCnt, byteCnt), length: byteCnt * 8}
}
// 添加数值
func (b *BitMap) Add(number uint64) error {
if number > b.length {
return fmt.Errorf("number %d is out of bitmap range", number)
}
tmp1 := number / 8
tmp2 := number % 8
b.data[tmp1] = b.data[tmp1] | 1<<tmp2
return nil
}
// 删除数值
func (b *BitMap) Del(number uint64) error {
if number > b.length {
return fmt.Errorf("number %d is out of bitmap range", number)
}
tmp1 := number / 8
tmp2 := number % 8
b.data[tmp1] = b.data[tmp1] & ^(1 << tmp2)
return nil
}
// 检查是否含有某个数值
func (b *BitMap) Contains(number uint64) bool {
tmp1 := number / 8
tmp2 := number % 8
return (number < b.length) && (b.data[tmp1]&(1<<tmp2) != 0)
}
// 列出所有数值
func (b *BitMap) List() []uint64 {
var result []uint64
var tmp = []uint64{0, 1, 2, 3, 4, 5, 6, 7}
for idx, d := range b.data {
for _, t := range tmp {
if d&(1<<t) != 0 {
result = append(result, uint64(idx)*8+t)
}
}
}
return result
}
func main() {
bm := NewBitMap(10)
err := bm.Add(1)
if err != nil {
fmt.Println(err)
}
err = bm.Add(4)
if err != nil {
fmt.Println(err)
}
err = bm.Add(7)
if err != nil {
fmt.Println(err)
}
err = bm.Add(9)
if err != nil {
fmt.Println(err)
}
err = bm.Add(11)
if err != nil {
fmt.Println(err)
}
err = bm.Add(18)
if err != nil {
fmt.Println(err)
}
fmt.Println("data:", bm.List())
fmt.Println("data contains 1?", bm.Contains(1))
fmt.Println("data contains 3?", bm.Contains(3))
fmt.Println("data contains 4?", bm.Contains(4))
fmt.Println("data contains 11?", bm.Contains(11))
fmt.Println("data contains 18?", bm.Contains(18))
err = bm.Del(11)
if err != nil {
fmt.Println(err)
}
fmt.Println("del 11,data:", bm.List())
err = bm.Del(4)
if err != nil {
fmt.Println(err)
}
fmt.Println("del 4,data:", bm.List())
}
输出：
1
2
3
4
5
6
7
8
9
number 18 is out of bitmap range
data: [1 4 7 9 11]
data contains 1? true
data contains 3? false
data contains 4? true
data contains 11? true
data contains 18? false
del 11,data: [1 4 7 9]
del 4,data: [1 7 9]