浅析bitset的实现原理:一个将非负整数映射到布尔值的位集合库

Go学堂

发布于 2023-08-29 16:50:19

2610

发布于 2023-08-29 16:50:19

文章被收录于专栏：Go工具箱

大家好，我是渔夫子。

今天我们通过开源包bitset来分析位集合的设计和实现。

一、bitset简介

1.1、主要功能

bitset包是一个将非负整数映射到布尔值的位的集合。比如我们有一个64位的二进制序列，要将第N位设置成true，对应的就是将第N位置成1。如下：

image.png

该包因为使用的是位操作，所以比使用map[uint]bool来实现非负整数到布尔值的映射会更高效。

该包不仅提供了setting、clearing、flipping和testing的方法。还提供了集合的交集、并集、差集等方法。

1.2、github上的基础属性

**项目地址: **https://github.com/bits-and-blooms/bitset星标：1.1k 贡献者人数：33 人

1.3、谁在用

image.png

二、设计与实现

在了解了bitset的基本功能之后，我们来分析bitset的设计和实现。

2.1 数据结构

在bitset包中，核心的数据结构是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的数据类型。bitset不是按位存储的集合吗，怎么set的数据类型是uint64呢？

这里就涉及到计算机的一个基础知识点：

“计算机存储和处理的信息都是以二值信号表示的。所谓的二值信号就是0和1，也就是我们常说的二进制。

所以，整数的底层也是二进制位。uint64在go语言中就代表的是用64个二进制位表示的整数值。

在bitset中，我们先假设set字段只有一个uint64的整数。那么，如果我们想将第7位设置成1，那么就如下：

但是，一个uint64的整数最多也就只有64个二进制位。那如果我们想设置第100位为true，那又该怎么表示呢？这也就是set字段的类型为什么是一个切片的原因了。既然一个uint64最多只能表示64个二进制位，那么我就用多个uint64不就能表示更多的二进制位了吗。

所以，set中第一个uint64表示前64个二进制位，第二个uint64表示65到128的二进制位，以此类推。这样就理论上就可以表示任意位数的二进制位了。

2.2 length字段代表的是什么的长度？

length字段表示在初始化一个BitSet对象时，该BitSet对象总共能容纳多少位，根据这个总位数来分配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的非负整数来表示。这里通过wordsNeeded函数来计算的，如下：

// 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位代表什么？就是代表用左边的数除以64（2的6次方）的商。这里我们要计算length个位数一共能用几个uint64来表示，就是用length除以64即可了。
wordSize常量：在bitset中的定义是uint(64)。正好表示的是64位，一个uint64类型的位数。这里要看一下为什么还要用i（也就是length）加上一个(wordSize-1)呢？。举个例子，假设i=65，即要表示65个二进制位，那需要用两个uint64的整数来表示才行。但65右移6位是1，所以需要加上wordSize-1再右移6位，结果就是2，即用2个uint64的整数才能存储65位的二进制位。

所以，wordsNeeded函数表示的就是要存储i个二进制位需要用几个uint64的整数。

2.3 如何在整数中实现位操作？

为了简便，我们用uint8来说明。uint8代表的是一个8位的非负整数。例如，要把uint8的第2位设置成1。用二进制表示就是：00000100。这个怎么得到呢？我们知道1的二进制表示是00000001，那么让这个1左移2位就能得到结果00000100。即 1<<2。

如果再把该uint8的第3位也设置成1，怎么办呢？首先让1左移3位得到00001000。因为原有uint8的第二位也是1，这里就要用uint8原有的值和00001000进行做或操作，就能保持住uint8原有的位的值不变了。如下：

原有的uint8（第二位是1）：00000100
          第三位设置成1：00001000
     -----------------------------
或的结果：              00001100

以上就是在整数中进行的位操作。

2.4 如何计算第N位落在哪个分组上？

在上面的BitSet的数据结构中，我们知道set字段是一个uint64的切片类型，相当于把每64位分成一组。那么，当设置第N位为1的时候，首先要做的是计算第N位应该落在哪个分组上。这个是怎么计算呢？就是第N位是63（因为位数是从0开始的）的多少倍，比如要设置第66位为1，那么66位是63的1倍（余数省略），所以在切片的第1个分组上（索引是从0开始，实际是切片的第二个分组）。

还是以uint8（8位）一组为例来说。如果要设置第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取余数了。如下：

你看，这样就把最高位的1给消除了，结果余数是2的1次方，即2。最后，因为一个uint8的整数的最高位是第7位（从0位开始），所以第10位应该是第二个uint8的第3位上。最后让1再左移上述结果的2位即可。

如下是bitset的实现：

// 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位从右边往左边数的
 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最基本的数据结构以及如何设置一个位为1的实现，其他的方法基本都是类似的思想来实现的，有兴趣大家可以继续研读该包的源代码。