詳細介紹 Go 中如何實現 bitset

• 2019 年 11 月 15 日
• 筆記

最近嘗試在 B 站錄些小影片，我的 B 站主頁。錄影片當是為了徹底搞懂某個知識點的最後一步吧，同時也希望能習得一些額外的能力。在講 Go 如何實現 bitset 的時候，發現這塊內容有點難講。思考後，我決定通過文字輔以影片的方式說明，於是就寫了這篇文章。

相關程式碼已經放在了 github，地址如下：go-set-example

如果發現有什麼不妥的地方，歡迎大佬們指正，感謝。

bitset 結構

之前我已經寫過一篇題為 Go 中如何使用 Set 的文章，其中介紹了 bitset 一種最簡單的應用場景，狀態標誌位，順便還提了下 bitset 的實現思路。

狀態標誌和一般的集合有什麼區別呢？

我的總結是主要一點，那就是狀態標誌中元素個數通常是固定的。而一般的集合中，元素個數通常是動態變化的。這會導致什麼問題？

一般，我們使用一個整數就足以表示狀態標誌中的所有狀態，最大的 int64 類型，足足有 64 個二進位位，最多可以包含 64 個元素，完全足夠使用。但如果是集合，元素數量和值通常都不固定。

比如一個 bitset 集合最初可能只包含 1、2、4 幾個元素，只要一個 int64 就能表示。如下：

但如果再增加了一個元素，比如 64（一個 int64 的表示範圍是 0-63），這已經超出了一個 int64 能表示的範圍。該怎麼辦？

一個 int64 無法表示，那就用多個唄。此時的結構如下：

一個 int64 切片正好符合上面的結構。那我們就可以定義一個新的類型 BitSet，如下：

type BitSet struct {  	data []int64  	size int  }  複製程式碼

data 成員用於存放集合元素，切片的特點就是能動態擴容。

還有，因為 bitset 中元素個數無法通過 len 函數獲取，而具體的方法相對複雜一點，可增加一個 size 欄位記錄集合元素的個數。然後就可以增加一個 Size 方法。

func (set *BitSet) Size() int {  	return set.size  }  複製程式碼

元素位置

定義好了 BitSet 類型，又產生了一個新的問題，如何定位存放元素的位置？在標誌位的場景下，元素的值即是位置，所以這個問題不用考慮。但通用的集合不是如此。

先看下 BitSet 的二進位位的分布情況。

類似行列的效果，假設用 index 表示行（索引），pos 表示列（位置）。切片索引從 0 到 n，n 與集合中的最大元素有關。

接下來確定 index 和 pos 的值。其實，之前的文章已經介紹過了。

index 可通過元素值整除字長，即 value / 64，轉化為高效的位運算，即 value >> 6。

pos 可以通過元素值取模字長，即 value % 64，轉化為高效的位運算，即 value & 0x3f，獲取對應位置，然後用 1 << uint(value % 0xf) 即可將位置轉化為值。

程式碼實現

理論再多，都不如 show me your code。開始編寫程式碼吧！

先定義一些常量。

const (  	shift = 6    // 2^n = 64 的 n  	mask  = 0x3f // n=6，即 2^n - 1 = 63，即 0x3f  )  複製程式碼

就是前面提到的用於計算 index 和 pos 的兩個常量。

提供兩個函數，用於方便 index 和 pos 上對應值的計算，程式碼如下：

func index(n int) int {  	return n >> shift  }    // 相對於標誌位使用場景中某個標誌的值  func posVal(n int) uint64 {  	return 1 << uint(n&mask)  }  複製程式碼

構造函數

提供了一個函數，用於創建初始 BitSet，且支援設置初始的元素。

函數原型如下：

func NewBitSet(ns ...int) *BitSet {  	// ...  }  複製程式碼

輸出參數 ns 是一個 int 類型的變長參數，用於設置集合中的初始值。

如果輸入參數 ns 為空的話，new(BitSet) 返回空集合即可。

if len(ns) == 0 {  	return new(BitSet)  }  複製程式碼

如果長度非空，則要計算要開闢的空間，通過計算最大元素的 index 可確定。

// 計算多 bitset 開闢多個空間  max := ns[0]  for _, n := range ns {  	if n > max {  		max = n  	}  }    // 如果 max < 0，直接返回空。  if max < 0 {  	return new(BitSet)  }    // 通過 max >> shift+1 計算最大值 max 所在 index  // 而 index + 1 即為要開闢的空間  s := &BitSet{  	data: make([]int64, index(max)+1),  }  複製程式碼

現在，可以向 BitSet 中添加元素了。

for _, n := range ns {  	if n >= 0 {  		// e >> shift 獲取索引位置，即行，一般叫 index  		// e&mask 獲取所在列，一般叫 pos，F1 0 F2 1  		s.data[n>>shift] |= posVal(n)  		// 增加元素個數  		s.size++  	}  }    // 返回創建的 BitSet  return s  複製程式碼

元素已經全部添加完成！

BitSet 的方法

接下來是重點了，為 BitSet 增加一些方法。主要是分成兩類，一是常見的增刪查等基礎方法，二是集合的特有操作，交並差。

基礎方法

主要是幾個方法，分別是 Add（增加）、Clear（清除） 、Contains（檢查）以及返回元素個數。如果要有更好的性能和空間使用率，Add 和 Clear 還有考慮靈活的。

contains

先講 Contains，即檢查是否存在某個元素。

函數定義如下：

func (set *BitSet) Contains(n int) bool {  	...  }  複製程式碼

輸入參數即是要檢查的元素，輸出是檢查結果。

實現程式碼如下：

// 獲取元素對應的 int64 的位置，如果超出 data 能表示的範圍，直接返回。  i := index(n)  if i >= len(set.data) {  	return false  }    return set.data[i]&posVal(n) != 0  複製程式碼

核心就是 set.data[i]&posVal(n) != 0 這句程式碼，通過它判斷是否存在指定元素。

clear

再談 Clear，從集合中清除某個元素，

函數定義如下：

func (set *BitSet) Clear(n int) *BitSet {  	// ...  }  複製程式碼

實現程式碼如下：

// 元素不能小於 0  if n < 0 {  	return set  }    // 計算切片索引位置，如果超出當前索引表示的範圍，返回即可。  i := index(n)  if i >= len(set.data) {  	return set  }    // 檢查是否存在元素  if d[i]&posVal(n) != 0 {  	set.data[i] &^= posVal(n)  	set.size--  }  複製程式碼

通過 &^ 實現指定位清除。同時要記得set.size-- 更新集合中元素的值。

上面的實現中有個瑕疵，就是如果一些為被置零後，可能會出現高位全部為 0，此時應要通過 reslice 收縮 data 空間。

具體怎麼操作呢？

通過對 set.data 執行檢查，從高位檢查首個不為 0 的 uint64，以此為基準進行 reslice。假設，這個方法名為 trim。

實現程式碼如下：

func (set *Set) trim() {  	d := set.data  	n := len(d) - 1  	for n >= 0 && d[n] == 0 {  		n--  	}  	set.data = d[:n+1]  }  複製程式碼

add

接著，再說 Add 方法，向集合中添加某個元素。

函數定義如下：

func (set *BitSet) Add(n int) *BitSet {  	...  }  複製程式碼

增加元素的話，先檢查下是否有足夠空間存放新元素。如果新元素的索引位置不在當前 data 表示的範圍，則要進行擴容。

實現如下：

// 檢測是否有足夠的空間存放新元素  i := index(n)  if i >= len(set.data) {  	// 擴容大小為 i+1  	ndata := make([]uint64, i+1)  	copy(ndata, set.data)  	set.data = ndata  }  複製程式碼

一切準備就緒後，接下來就可以進行置位添加了。在添加前，先檢測下集合是否已經包含了該元素。在添加完成後，還要記得要更新下 size。

實現程式碼如下：

if set.data[i]&posVal(n) == 0 {  	// 設置元素到集合中  	set.data[i] |= posVal(n)  	s.size++  }  複製程式碼

好了！基礎的方法就介紹這麼多吧。

當然，這裡的方法還可以增加更多，比如查找當前元素的下一個元素，將某個範圍值都添加進集合等等等。

集合方法

介紹完了基礎的方法，再繼續介紹集合一些特有的方法，交並差。

computeSize

在正式介紹這些方法前，先引入一個輔助方法，用於計算集合中的元素個數。之所以要引入這個方法，是因為交並差沒有辦法像之前在增刪的時候更新 size，要重新計算一下。

實現程式碼如下：

func (set *BitSet) computeSize() int {  	d := set.data  	n := 0  	for i, len := 0, len(d); i < len; i++ {  		if w := d[i]; w != 0 {  			n += bits.OnesCount64(w)  		}  	}    	return n  }  複製程式碼

這是一個不可導出的方法，只能內部使用。遍歷 data 的每個 uint64，如果非 0，則統計其中的元素個數。元素個數統計用到了標準庫中的 bits.OnesCount64 方法。

方法定義

繼續介紹集合的幾個方法，它們的定義類似，都是一個 BitSet 與另一個 BitSet 的運算，如下：

// 交集  func (set *BitSet) Intersect(other *BitSet) *BitSet {  	// ...  }  // 並集  func (set *BitSet) Union(other *BitSet) *BitSet {  	// ...  }  // 差集  func (set *BitSet) Difference(other *BitSet) *BitSet {  	// ...  }  複製程式碼

intersect

先介紹 Intersect，即計算交集的方法。

一個重要前提，因為交集是 與運算，結果肯定位於兩個參與運算的那個小範圍集合中，所以，開闢空間和遍歷可以縮小到這個範圍進行。

實現程式碼如下：

// 首先，獲取這個小範圍的集合的長度  minLen := min(len(set.data), len(other.data))    // 以 minLen 開闢空間  intersectSet := &BitSet{  	data: make([]uint64, minLen),  }    // 以 minLen 進行遍歷計算交集  for i := minLen - 1; i >= 0; i-- {  	intersectSet.data[i] = set.data[i] & other.data[i]  }    intersectSet.size = set.computeSize()  複製程式碼

這裡通過遍歷逐一對每個 uint64 執行 與運算 實現交集。在完成操作後，記得計算下 intersectSet 中元素個數，即 size 的值。

union

再介紹並集 Union 方法。

它的計算邏輯和 Intersect 相反。並集結果所佔據的空間和以參與運算的兩個集合的較大集合為準。

實現程式碼如下：

var maxSet, minSet *BitSet  if len(set.data) > len(other.data) {  	maxSet, minSet = set, other  } else {  	maxSet, minSet = other, set  }    unionSet := &BitSet{  	data: make([]uint64, len(maxSet.data)),  }  複製程式碼

創建的 unionSet 中，data 分配空間是 len(maxSet.data)。

因為兩個集合中的所有元素滿足最終結果，但 maxSet 的高位部分無法通過遍歷和 minSet 執行運算，直接拷貝進結果中即可。

minLen := len(minSet.data)  copy(unionSet.data[minLen:], maxSet.data[minLen:])  複製程式碼

最後，遍歷兩個集合 data，通過 或運算 計算剩餘的部分。

for i := 0; i < minLen; i++ {  	unionSet.data[i] = set.data[i] | other.data[i]  }    // 更新計算 size  unionSet.size = unionSet.computeSize()  複製程式碼

difference

介紹最後一個與集合相關的方法，Difference，即差集操作。

差集計算結果 differenceSet 的分配空間由被減集合 set 決定。其他的操作和 Intersect 和 Union 類似，位運算通過 &^ 實現。

setLen := len(set.data)    differenceSet := &BitSet{  	data: make([]uint64, setLen),  }  複製程式碼

如果 set 的長度大於 other，則需要先將無法進行差集運算的內容拷貝下。

minLen := setLen  if setLen > otherLen {  	copy(differenceSet.data[otherLen:], set.data[otherLen:])  	minLen = otherLen  }  複製程式碼

記錄下 minLen 用於接下來的位運算。

// 遍歷 data 執行位運算。  for i := 0; i < minLen; i++ {  	differenceSet.data[i] = set.data[i] &^ other.data[i]  }    differenceSet.size = differenceSet.computeSize()  複製程式碼

遍歷集合的元素

單獨說下集合元素的遍歷，之前查看集合元素一直都是通過 Contains 方法檢查是否存在。能不能把集合中的每個元素全部遍歷出來呢？

再看下 bitset 的結構，如下：

上面的集合中，第一行 int64 的第一個元素是 1，尾部有一位被置零。通過觀察發現，前面有幾個 0，第一個元素就是什麼值。

第二行 int64 的第一元素尾部沒有 0，那它的值就是 0 嗎？當然不是，還有前面一行的 64 位基礎，所以它的值是 64+0。

總結出什麼規律了嗎？笨，理論功底太差，滿腦子明白，就是感覺寫不清楚。看程式碼吧！

先看函數定義：

func (set *BitSet) Visit(do func(int) (skip bool)) (aborted bool) {  	//...  }  複製程式碼

輸入參數是一個回調函數，通過它獲取元素的值，不然每次都要寫一大串循環運算邏輯，不太可能。回調函數的返回值 bool，表明是否繼續遍歷。Visit 的返回值表明是函數是非正常結束的。

實現程式碼如下：

d := set.data  for i, len := 0, len(d); i < len; i++ {  	w := d[i]  	if w == 0 {  		continue  	}    	// 理論功力不好，不知道怎麼描述了。哈哈  	// 這小段程式碼可以理解為從元素值到 index 的逆運算，  	// 只不過得到的值是諸如 0、64、128 的第一個位置的值。  	// 0 << 6，還是 0，1 << 6 就是 64，2 << 6 的就是 128  	n := i << shift  	for w != 0 {  		// 000.....000100 64~128 的話，表示 66，即 64 + 2，這個 2 可以由結尾 0 的個數確定  		// 那怎麼獲取結果 0 的個數呢？可以使用 bits.TrailingZeros64 函數  		b := bits.TrailingZeros64(w)  		if do(n + b) {  			return true  		}  		// 將已經檢查的位清零  		// 為了保證尾部 0 的個數能代表元素的值  		w &^= 1 << uint64(b)  	}  }  複製程式碼

使用也非常方便，示例程式碼如下：

set := NewBitSet(1, 2, 10, 99)  set.Visit(func(n int) bool {  	fmt.Println(n)  	return false  })  複製程式碼

好了，就說這麼多吧！

總結

本篇文章主要是參考了幾個開源包的基礎上，介紹了 bitset 的實現，比如 bit 和 bitset 等。總的來說，位運算就是沒有那麼直觀，感覺腦子不夠用了。

感悟

最近在深挖 Go 語言，漸漸發現了自己的一些短板，理論知識的缺失漸漸顯現。比如，我在寫這篇文章的時候，了解到 bits 標準庫中用到了 德布魯因序列，此前並不清楚。前幾天在研究如何進行 JSON 解析時，了解到了有限狀態機這個知識，Go 的源碼中簡直完美體現了這個知識的重要性。在學習 Go 語言組成的時候，知道了 擴展巴克斯範式，很多語言的文檔都是這種方式來表現語法，一門瞭然。

作為一名電子資訊專業畢業的專科生，算不上電腦的科班出生，工作六年才了解到這些知識，有點煩悶，也有點興奮。如果說前六年是廣度的提升，那麼，接下來就應該是更加專註的研究了。