Go語言里的集合一般會用map[T]bool這種形式來表示，T代表元素類型。集合用map類型來表示雖然非常靈活，但我們可以以一種更好的形式來表示它。
例如在數據流分析領域，集合元素通常是一個非負整數，集合會包含很多元素，并且集合會經常進行并集、交集操作，這種情況下，bit數組會比map表現更加理想。
一個bit數組通常會用一個無符號數或者稱之為“字”的slice來表示，每一個元素的每一位都表示集合里的一個值。當集合的第i位被設置時，我們才說這個集合包含元素i。
下面的這個程序展示了一個簡單的bit數組類型，并且實現了三個函數來對這個bit數組來進行操作：
|
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
|
package mainimport ( "bytes" "fmt")// An IntSet is a set of small non-negative integers.// Its zero value represents the empty set.type IntSet struct { words []uint}const ( bitNum = (32 << (^uint(0) >> 63)) //根據平臺自動判斷決定是32還是64)// Has reports whether the set contains the non-negative value x.func (s *IntSet) Has(x int) bool { word, bit := x/bitNum, uint(x%bitNum) return word < len(s.words) && s.words[word]&(1<<bit) != 0}// Add adds the non-negative value x to the set.func (s *IntSet) Add(x int) { word, bit := x/bitNum, uint(x%bitNum) for word >= len(s.words) { s.words = append(s.words, 0) } s.words[word] |= 1 << bit}//A與B的交集，合并A與B// UnionWith sets s to the union of s and t.func (s *IntSet) UnionWith(t *IntSet) { for i, tword := range t.words { if i < len(s.words) { s.words[i] |= tword } else { s.words = append(s.words, tword) } }} |
因為每一個字都有64個二進制位，所以為了定位x的bit位，我們用了x/64的商作為字的下標，并且用x%64得到的值作為這個字內的bit的所在位置。
例如，對于數字1，將其加入比特數組：
|
1
2
3
4
5
6
7
8
|
func (s *IntSet) Add(x int) { word, bit := x/bitNum, uint(x%bitNum) //0, 1 := 1/64, uint(1%64) for word >= len(s.words) { // 條件不滿足 s.words = append(s.words, 0) } s.words[word] |= 1 << bit // s.words[0] |= 1 << 1}// 把1存入后，words數組變為了[]uint64{2} |
同理，假如我們再將66加入比特數組：
|
1
2
3
4
5
6
7
8
|
func (s *IntSet) Add(x int) { word, bit := x/bitNum, uint(x%bitNum) //1, 2 := 66/64, uint(66%64) for word >= len(s.words) { // 條件滿足 s.words = append(s.words, 0) // 此時s.words = []uint64{2, 0} } s.words[word] |= 1 << bit // s.words[1] |= 1 << 2}// 繼續把66存入后，words數組變為了[]uint64{2, 4} |
所以，對于words，每個元素可存儲的值有64個，每超過64個則進位，即添加一個元素。（注意，0也占了一位，所以64才要進位，第一個元素可存儲0-63）。
所以，對于words中的一個元素，要轉換為具體的值時：首先取到其位置i，用 64 * i 作為已進位數（類似于每10位要進位）， 然后將這個元素轉換為二進制數，從右往左數，第多少位為1則表示相應的有這個值，用這個位數 x+64 *i 即為我們存入的值。
相應的，可有如下String()函數
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// String returns the set as a string of the form "{1 2 3}".func (s *IntSet) String() string { var buf bytes.Buffer buf.WriteByte('{') for i, word := range s.words { if word == 0 { continue } for j := 0; j < bitNum; j++ { if word&(1<<uint(j)) != 0 { if buf.Len() > len("{") { buf.WriteByte(' ') } fmt.Fprintf(&buf, "%d", bitNum*i+j) } } } buf.WriteByte('}') return buf.String()} |
例如，前面存入了1和66后，轉換過程為：
|
1
2
3
4
|
// []uint64{2 4}// 對于2: 1 << 1 = 2; 所以 x = 0 * 64 + 1 // 對于4: 1 << 2 = 4; 所以 x = 1 * 64 + 2// 所以轉換為String為{1 66} |
實現比特數組的其他方法函數
|
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
|
func (s *IntSet) Len() int { var len int for _, word := range s.words { for j := 0; j < bitNum; j++ { if word&(1<<uint(j)) != 0 { len++ } } } return len}func (s *IntSet) Remove(x int) { word, bit := x/bitNum, uint(x%bitNum) if s.Has(x) { s.words[word] ^= 1 << bit }}func (s *IntSet) Clear() { s.words = append([]uint{})}func (s *IntSet) Copy() *IntSet { intSet := &IntSet{ words: []uint{}, } for _, value := range s.words { intSet.words = append(intSet.words, value) } return intSet}func (s *IntSet) AddAll(args ...int) { for _, x := range args { s.Add(x) }}//A與B的并集，A與B中均出現func (s *IntSet) IntersectWith(t *IntSet) { for i, tword := range t.words { if i >= len(s.words) { continue } s.words[i] &= tword }}//A與B的差集，元素出現在A未出現在Bfunc (s *IntSet) DifferenceWith(t *IntSet) { t1 := t.Copy() //為了不改變傳參t，拷貝一份 t1.IntersectWith(s) for i, tword := range t1.words { if i < len(s.words) { s.words[i] ^= tword } }}//A與B的并差集，元素出現在A沒有出現在B，或出現在B沒有出現在Afunc (s *IntSet) SymmetricDifference(t *IntSet) { for i, tword := range t.words { if i < len(s.words) { s.words[i] ^= tword } else { s.words = append(s.words, tword) } }}//獲取比特數組中的所有元素的slice集合func (s *IntSet) Elems() []int { var elems []int for i, word := range s.words { for j := 0; j < bitNum; j++ { if word&(1<<uint(j)) != 0 { elems = append(elems, bitNum*i+j) } } } return elems} |
至此，比特數組的常用方法函數都已實現，現在可以來使用它。
|
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
|
func main() { var x, y IntSet x.Add(1) x.Add(144) x.Add(9) fmt.Println("x:", x.String()) // "{1 9 144}" y.Add(9) y.Add(42) fmt.Println("y:", y.String()) // "{9 42}" x.UnionWith(&y) fmt.Println("x unionWith y:", x.String()) // "{1 9 42 144}" fmt.Println("x has 9,123:", x.Has(9), x.Has(123)) // "true false" fmt.Println("x len:", x.Len()) //4 fmt.Println("y len:", y.Len()) //2 x.Remove(42) fmt.Println("x after Remove 42:", x.String()) //{1 9 144} z := x.Copy() fmt.Println("z copy from x:", z.String()) //{1 9 144} x.Clear() fmt.Println("clear x:", x.String()) //{} x.AddAll(1, 2, 9) fmt.Println("x addAll 1,2,9:", x.String()) //{1 2 9} x.IntersectWith(&y) fmt.Println("x intersectWith y:", x.String()) //{9} x.AddAll(1, 2) fmt.Println("x addAll 1,2:", x.String()) //{1 2 9} x.DifferenceWith(&y) fmt.Println("x differenceWith y:", x.String()) //{1 2} x.AddAll(9, 144) fmt.Println("x addAll 9,144:", x.String()) //{1 2 9 144} x.SymmetricDifference(&y) fmt.Println("x symmetricDifference y:", x.String()) //{1 2 42 144} for _, value := range x.Elems() { fmt.Print(value, " ") //1 2 42 144 }} |
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持服務器之家。如有錯誤或未考慮完全的地方，望不吝賜教。
原文鏈接：https://blog.csdn.net/qq_34434641/article/details/80418124
