Golang 程序实现位集
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 }
语法 BitSet 结构表示使用 uint64 切片实现的 BitSet。 data 字段是一个 uint64 切片，用于存储 BitSet 的实际位。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("位置 1 的位被设置:", bitSet.Test(1))
fmt.Println("位置 10 的位被设置:", bitSet.Test(10))
fmt.Println("位置 3 的位被设置:", bitSet.Test(3))
}
输出
位置 1 的位被设置:true 位置 10 的位被设置:false 位置 3 的位被设置:true
示例 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("位置 1 的位已设置:", bitSet.Test(1))
fmt.Println("位置 10 的位已设置:", bitSet.Test(10))
fmt.Println("位置 3 的位已设置:", bitSet.Test(3))
}
输出
位置 1 的位已设置:true 位置 10 的位已设置:false 位置 3 的位已设置:true
实际实现
网络数据包过滤
BitSet 在网络中用于数据包过滤，路由器和防火墙将传入的数据包与规则进行匹配。每条规则都表示为一个 BitSet，其中的位表示条件，如源 IP 范围、协议或数据标志。高效的按位运算有助于快速决定是否允许数据包。
稀疏数据索引
在数据库和搜索引擎中，BitSet 索引用于稀疏数据。它将属性压缩为位，从而节省内存。例如，在搜索引擎中，BitSet 识别包含特定术语的文档。设置位表示术语存在，使索引和查询更快。
结论
BitSet 是一种数据结构，用于高效存储和操作一组二进制值，其中每个值可以是 0 或 1。在本文中，我们研究了如何在 Go 中实现 BitSet:一个使用 uint64 切片，另一个使用固定大小的整数数组。第一个例子在处理大量位数时内存效率较高，而第二个例子在处理较少位数时内存效率更高。
