极客笔记Go语言程序实现位集合（BitSet）
BitSet是一种数据结构，用于表示一组固定大小的二进制值，每个值可以是0或1。它通常用于高效存储和操作大量布尔值的集合。在本文中，我们将使用两种不同的方法在Go语言中实现位集合，第一种方法涉及使用布尔切片，第二种方法涉及使用无符号整数进行位操作。在这里，实现指的是在位集合数据结构中执行设置、清除和测试单个位的各种操作。
解释
BitSet是一种用于高效存储和操作一组二进制值的数据结构，其中每个值可以是0或1。它特别适用于需要跟踪大量布尔值的场景，如表示集合中元素的成员或存在性。
Bitset: [0, 1, 0, 1, 0, 0, 1, 0]
Index: 0 1 2 3 4 5 6 7
语法
type BitSet struct{ data []uint64; size int }
Syntax BitSet结构体表示使用uint64切片实现的BitSet。data字段是存储BitSet实际位的uint64切片。size字段指示BitSet中的总位数。这种方法在处理大量位时具有内存效率，并且通过对uint64元素执行位操作来有效地操作个别位。
算法
- 使用空的uint64数据切片创建BitSet结构体，并将大小设置为BitSet中所需位数。
-
要在特定位置pos设置位，请使用pos / 64计算数据切片中uint64元素的索引，并使用pos％64计算该uint64元素中位的位置。使用按位或（|）在计算的位置上设置位于uint64元素。
-
要在特定位置pos清除位，请类似于设置操作，计算uint64元素的索引和位于该元素中的位的位置。使用按位与（&）与位掩码的否定来清除在计算位置处的位。
-
要在特定位置pos切换位，请类似于设置操作，计算uint64元素的索引和位于该元素中的位的位置。使用按位异或（^）与位掩码来切换计算位置处的位。
-
并集、交集和差集：要对两个BitSet执行并集、交集和差集等集合操作，在两个BitSet的数据切片的元素之间应用相应的位操作（OR、AND和XOR）。
-
要对BitSet执行位移和旋转操作，请在数据切片元素上使用位移和旋转操作将位左移或右移。
示例1
在这个示例中，我们将使用uint64切片在Go中实现一个BitSet。切片中的每个uint64元素可以表示64位，使我们能够高效处理大量的位。NewBitSet函数使用指定的大小初始化BitSet。Set函数在给定的索引处设置特定的位，Clear函数清除给定索引处的位，而Test函数检查给定索引处的位是否设置。
package main
import "fmt"
type BitSet struct {
bitArray []uint64
size int
}
func NewBitSet(size int) *BitSet {
sliceSize := (size + 63) / 64
return &BitSet{
bitArray: make([]uint64, sliceSize),
size: size,
}
}
func (bs *BitSet) Set(bit int) {
if bit < 0 || bit >= bs.size {
return
}
index := bit / 64
offset := bit % 64
bs.bitArray[index] |= 1 << offset
}
func (bs *BitSet) Clear(bit int) {
if bit < 0 || bit >= bs.size {
return
}
index := bit / 64
offset := bit % 64
bs.bitArray[index] &= ^(1 << offset)
}
func (bs *BitSet) Test(bit int) bool {
if bit < 0 || bit >= bs.size {
return false
}
index := bit / 64
offset := bit % 64
return (bs.bitArray[index] & (1 << offset)) != 0
}
func main() {
bitSet := NewBitSet(128)
bitSet.Set(1)
bitSet.Set(3)
bitSet.Set(5)
bitSet.Set(120)
fmt.Println("Bit at position 1 is set:", bitSet.Test(1))
fmt.Println("Bit at position 10 is set:", bitSet.Test(10))
fmt.Println("Bit at position 3 is set:", bitSet.Test(3))
}
输出
Bit at position 1 is set: true
Bit at position 10 is set: false
Bit at position 3 is set: true
Example 2
在这个例子中，我们将使用固定大小的整数数组来在Go语言中实现一个BitSet。在这里，每个整数表示固定数量的位。例如，使用32位整数，我们可以表示32位。我们将演示如何设置、清除和测试BitSet中的单个位。我们将使用32位整数数组来表示BitSet，每个元素可以容纳32位。
package main
import (
"fmt"
)
type BitSet struct {
bitArray []uint32
size int
}
func NewBitSet(size int) *BitSet {
numElements := (size + 31) / 32
return &BitSet{
bitArray: make([]uint32, numElements),
size: size,
}
}
func (bs *BitSet) Set(bit int) {
if bit < 0 || bit >= bs.size {
return
}
element := bit / 32
bitWithinElement := bit % 32
bs.bitArray[element] |= (1 << uint32(bitWithinElement))
}
func (bs *BitSet) Clear(bit int) {
if bit < 0 || bit >= bs.size {
return
}
element := bit / 32
bitWithinElement := bit % 32
bs.bitArray[element] &= ^(1 << uint32(bitWithinElement))
}
func (bs *BitSet) Test(bit int) bool {
if bit < 0 || bit >= bs.size {
return false
}
element := bit / 32
bitWithinElement := bit % 32
return bs.bitArray[element]&(1<<uint32(bitWithinElement)) != 0
}
func main() {
bitSet := NewBitSet(128)
bitSet.Set(1)
bitSet.Set(3)
bitSet.Set(5)
bitSet.Set(120)
fmt.Println("Bit at position 1 is set:", bitSet.Test(1))
fmt.Println("Bit at position 10 is set:", bitSet.Test(10))
fmt.Println("Bit at position 3 is set:", bitSet.Test(3))
}
输出
Bit at position 1 is set: true
Bit at position 10 is set: false
Bit at position 3 is set: true
真实生活中的应用
网络包过滤
BitSet 在网络中用于数据包过滤，路由器和防火墙使用它来匹配传入的数据包和规则。每个规则都表示为一个 BitSet，其中的位表示源 IP 范围、协议或数据标志等条件。高效的位操作有助于快速决定是否允许传递的数据包。
稀疏数据索引
在数据库和搜索引擎中，BitSet 的索引用于稀疏数据。它将属性压缩为位，节省内存空间。例如，在搜索引擎中，BitSet 用于标识包含特定术语的文档。设置为 1 的位表示术语的存在，可以加快索引和查询的速度。
结论
BitSet 是一种用于高效存储和操作一组二进制值的数据结构，每个值可以为 0 或 1。在本文中，我们介绍了如何在 Go 中实现 BitSet：一种使用 uint64 切片的方法，另一种使用固定大小的整数数组的方法。第一个示例适用于处理大量位的情况下，内存效率更高，而第二个示例则更适用于少量位的情况下，尤其是在内存有限的情况下。