快捷導(dǎo)航

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

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

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

一、bitset簡(jiǎn)介

1.1、主要功能

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

該包因?yàn)槭褂玫氖俏徊僮鳎员仁褂胢ap[uint]bool來(lái)實(shí)現(xiàn)非負(fù)整數(shù)到布爾值的映射會(huì)更高效。

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

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

項(xiàng)目地址: https://github.com/bits-and-blooms/bitset

1.3、誰(shuí)在用

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

在了解了bitset的基本功能之后，我們來(lái)分析bitset的設(shè)計(jì)和實(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字段為什么是一個(gè)切片？

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

這里就涉及到計(jì)算機(jī)的一個(gè)基礎(chǔ)知識(shí)點(diǎn)：

計(jì)算機(jī)存儲(chǔ)和處理的信息都是以二值信號(hào)表示的。所謂的二值信號(hào)就是0和1，也就是我們常說(shuō)的二進(jìn)制。

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

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

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

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

2.2 length字段代表的是什么的長(zhǎng)度

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

// 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行中，需要計(jì)算的是要表示length個(gè)二進(jìn)制位需要幾個(gè)uint64的非負(fù)整數(shù)來(lái)表示。這里通過(guò)wordsNeeded函數(shù)來(lái)計(jì)算的，如下：

// 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)。這里有幾個(gè)常量，如下：

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

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

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

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

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

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

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

2.4 如何計(jì)算第N位落在哪個(gè)分組上

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

還是以u(píng)int8（8位）一組為例來(lái)說(shuō)。如果要設(shè)置第10位，則落在第二個(gè)uint8的分組上。如下：

按位操作來(lái)計(jì)算除法就是右移操作。這里讓N右移3位，因?yàn)橐苿?dòng)3位，代表的2的3次方，即8。也是用10除以8的商是1，即在set切片的第1個(gè)索引上，也就是第二個(gè)uint8上。

2.5 如何計(jì)算第N位落在分組的第幾位上

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

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

如下是bitset的實(shí)現(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)
	}
	// 說(shuō)明第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)
}

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