淺析Go語言bitset的實現(xiàn)原理

更新時間：2023年08月08日 11:32:55 作者：Go學(xué)堂

bitset包是一個將非負整數(shù)映射到布爾值的位的集合，這篇文章主要通過開源包bitset來為大家分析一下位集合的設(shè)計和實現(xiàn)，感興趣的可以學(xué)習(xí)一下

一、bitset簡介

1.1、主要功能

bitset包是一個將非負整數(shù)映射到布爾值的位的集合。比如我們有一個64位的二進制序列，要將第N位設(shè)置成true，對應(yīng)的就是將第N位置成1。如下：

該包因為使用的是位操作，所以比使用map[uint]bool來實現(xiàn)非負整數(shù)到布爾值的映射會更高效。

該包不僅提供了setting、clearing、flipping和testing的方法。還提供了集合的交集、并集、差集等方法。

1.2、github上的基礎(chǔ)屬性

項目地址: https://github.com/bits-and-blooms/bitset

1.3、誰在用

二、設(shè)計與實現(xiàn)

在了解了bitset的基本功能之后，我們來分析bitset的設(shè)計和實現(xiàn)。

2.1 數(shù)據(jù)結(jié)構(gòu)

在bitset包中，核心的數(shù)據(jù)結(jié)構(gòu)是BitSet。其定義如下：

// A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.
type BitSet struct {
	length uint
	set    []uint64
}

set字段為什么是一個切片？

首先來看為什么使用uint64的數(shù)據(jù)類型。bitset不是按位存儲的集合嗎，怎么set的數(shù)據(jù)類型是uint64呢？

這里就涉及到計算機的一個基礎(chǔ)知識點：

計算機存儲和處理的信息都是以二值信號表示的。所謂的二值信號就是0和1，也就是我們常說的二進制。

所以，整數(shù)的底層也是二進制位。uint64在go語言中就代表的是用64個二進制位表示的整數(shù)值。

在bitset中，我們先假設(shè)set字段只有一個uint64的整數(shù)。那么，如果我們想將第7位設(shè)置成1，那么就如下：

但是，一個uint64的整數(shù)最多也就只有64個二進制位。那如果我們想設(shè)置第100位為true，那又該怎么表示呢？這也就是set字段的類型為什么是一個切片的原因了。既然一個uint64最多只能表示64個二進制位，那么我就用多個uint64不就能表示更多的二進制位了嗎。

所以，set中第一個uint64表示前64個二進制位，第二個uint64表示65到128的二進制位，以此類推。這樣就理論上就可以表示任意位數(shù)的二進制位了。

2.2 length字段代表的是什么的長度

length字段表示在初始化一個BitSet對象時，該BitSet對象總共能容納多少位，根據(jù)這個總位數(shù)來分配set字段的切片長度。如下：

// New creates a new BitSet with a hint that length bits will be required
func New(length uint) (bset *BitSet) {
	defer func() {
		if r := recover(); r != nil {
			bset = &BitSet{
				0,
				make([]uint64, 0),
			}
		}
	}()
	bset = &BitSet{
		length,
		make([]uint64, wordsNeeded(length)),
	}
	return bset
}

看代碼的第12到15行。在第14行中，需要計算的是要表示length個二進制位需要幾個uint64的非負整數(shù)來表示。這里通過wordsNeeded函數(shù)來計算的，如下：

// wordsNeeded calculates the number of words needed for i bits
func wordsNeeded(i uint) int {
	if i > (Cap() - wordSize + 1) {
		return int(Cap() >> log2WordSize)
	}
	return int((i + (wordSize - 1)) >> log2WordSize)
}

這里主要看第6行的int((i + (wordSize - 1)) >> log2WordSize)。這里有幾個常量，如下：

**log2WordSize常量：**在bitset中的定義是uint(6)。為什么是6呢？因為2的6次方是64，而我們在set字段中又是用uint64來表示一組二進制位的。同時看這個計算右移6位，右移6位代表什么？就是代表用左邊的數(shù)除以64（2的6次方）的商。這里我們要計算length個位數(shù)一共能用幾個uint64來表示，就是用length除以64即可了。
**wordSize常量：在bitset中的定義是uint(64)。**正好表示的是64位，一個uint64類型的位數(shù)。這里要看一下為什么還要用i（也就是length）加上一個(wordSize-1)呢？。舉個例子，假設(shè)i=65，即要表示65個二進制位，那需要用兩個uint64的整數(shù)來表示才行。但65右移6位是1，所以需要加上wordSize-1再右移6位，結(jié)果就是2，即用2個uint64的整數(shù)才能存儲65位的二進制位。

所以，wordsNeeded函數(shù)表示的就是要存儲i個二進制位需要用幾個uint64的整數(shù)。

2.3 如何在整數(shù)中實現(xiàn)位操作

為了簡便，我們用uint8來說明。uint8代表的是一個8位的非負整數(shù)。例如，要把uint8的第2位設(shè)置成1。用二進制表示就是：00000100。這個怎么得到呢？我們知道1的二進制表示是00000001，那么讓這個1左移2位就能得到結(jié)果00000100。即 1<<2。

如果再把該uint8的第3位也設(shè)置成1，怎么辦呢？首先讓1左移3位得到00001000。因為原有uint8的第二位也是1，這里就要用uint8原有的值和00001000進行做或操作，就能保持住uint8原有的位的值不變了。如下：

原有的uint8（第二位是1）：00000100
第三位設(shè)置成1：00001000
-----------------------------
或的結(jié)果： 00001100

以上就是在整數(shù)中進行的位操作。

2.4 如何計算第N位落在哪個分組上

在上面的BitSet的數(shù)據(jù)結(jié)構(gòu)中，我們知道set字段是一個uint64的切片類型，相當于把每64位分成一組。那么，當設(shè)置第N位為1的時候，首先要做的是計算第N位應(yīng)該落在哪個分組上。這個是怎么計算呢？就是第N位是63（因為位數(shù)是從0開始的）的多少倍，比如要設(shè)置第66位為1，那么66位是63的1倍（余數(shù)省略），所以在切片的第1個分組上（索引是從0開始，實際是切片的第二個分組）。

還是以uint8（8位）一組為例來說。如果要設(shè)置第10位，則落在第二個uint8的分組上。如下：

按位操作來計算除法就是右移操作。這里讓N右移3位，因為移動3位，代表的2的3次方，即8。也是用10除以8的商是1，即在set切片的第1個索引上，也就是第二個uint8上。

2.5 如何計算第N位落在分組的第幾位上

其次，要計算第N位是在第2個分組的第幾位上。簡單點就是取余操作。用10%8，就是第2位上（因為從0開始，所以是第3位）。同樣，這里還有一種按位移操作的方法：10&7。我們解釋下這個與操作。我們看下8的二進制表示：1000。要想讓10除以8，就是將第3位的1抹掉，并保持其他位不變。要想保持原有位保持不變，就和1進行與操作。所以，讓二進制的1000變成0111，再和10的二進制進行與操作，就相當于除以8取余數(shù)了。如下：

你看，這樣就把最高位的1給消除了，結(jié)果余數(shù)是2的1次方，即2。最后，因為一個uint8的整數(shù)的最高位是第7位（從0位開始），所以第10位應(yīng)該是第二個uint8的第3位上。最后讓1再左移上述結(jié)果的2位即可。

如下是bitset的實現(xiàn)：

// log2WordSize is lg(wordSize)
const log2WordSize = uint(6)
func (b *BitSet) Set(i uint) *BitSet {
	if i >= b.length { // if we need more bits, make 'em
		b.extendSet(i)
	}
	// 說明第0位從右邊往左邊數(shù)的
	b.set[i>>log2WordSize] |= 1 << wordsIndex(i)
	return b
}
// the wordSize of a bit set
const wordSize = uint(64)
// wordsIndex calculates the index of words in a `uint64`
func wordsIndex(i uint) uint {
	return i & (wordSize - 1)
}

以上就是針對BitSet最基本的數(shù)據(jù)結(jié)構(gòu)以及如何設(shè)置一個位為1的實現(xiàn)，其他的方法基本都是類似的思想來實現(xiàn)的，有興趣大家可以繼續(xù)研讀該包的源代碼。