Documentation
¶
Overview ¶
Package bitset provides a compact and efficient implementation of a fixed-length bitset for the range [0..255].
This implementation is optimized for internal use in a compressed routing trie and prioritizes minimal allocation, performance, and inlining. It supports constant-time set/test operations, iteration over set bits, ranking, and masked intersections.
Internally, the bitset is represented by four uint64 words, providing fast bit-level access through direct indexing and hardware-accelerated primitives.
If Go eventually supports SIMD intrinsics, this can be further optimized.
For external consumers, the API intentionally avoids dynamic allocation except when explicitly requested (via Bits()).
Index ¶
- type BitSet256
- func (b *BitSet256) AsSlice(buf *[256]uint8) []uint8
- func (b *BitSet256) Bits() []uint8
- func (b *BitSet256) Clear(bit uint8)
- func (b *BitSet256) FirstSet() (first uint8, ok bool)
- func (b *BitSet256) Intersection(c *BitSet256) (bs BitSet256)
- func (b *BitSet256) IntersectionTop(c *BitSet256) (top uint8, ok bool)
- func (b *BitSet256) Intersects(c *BitSet256) bool
- func (b *BitSet256) IsEmpty() bool
- func (b *BitSet256) LastSet() (last uint8, ok bool)
- func (b *BitSet256) NextSet(bit uint8) (next uint8, ok bool)
- func (b *BitSet256) Rank(idx uint8) (rnk int)
- func (b *BitSet256) Set(bit uint8)
- func (b *BitSet256) Size() (cnt int)
- func (b *BitSet256) Test(bit uint8) (ok bool)
- func (b *BitSet256) Union(c *BitSet256)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BitSet256 ¶ added in v0.19.0
type BitSet256 [4]uint64
BitSet256 represents a fixed size bitset from [0..255]
func (*BitSet256) AsSlice ¶ added in v0.19.0
AsSlice returns a slice containing all set bits in the BitSet256.
The bits are returned in ascending order as uint8 values. The provided buf must be a pointer to an array of 256 uint8s; it is used as backing storage for the result to avoid heap allocations. The returned slice shares its backing array with buf and is only valid until buf is modified or reused.
func (*BitSet256) Bits ¶ added in v0.20.5
Bits returns a slice containing all set bits in the BitSet256.
The bits are returned in ascending order as uint8 values. Bits allocates a new slice on the heap for the result. For allocation-free collection, use [AsSlice] with a pre-allocated buffer.
Example usage:
bits := b.Bits() // bits now contains the indices of all set bits in b
func (*BitSet256) FirstSet ¶ added in v0.19.0
FirstSet returns the index of the lowest (first) bit that is set in the BitSet256.
It searches the 256-bit set in ascending order and returns the position of the first bit with value 1. If at least one bit is set, ok is true. If no bits are set, ok is false and first is undefined.
Example:
var bs BitSet256 bs.Set(17) bs.Set(42) bs.Set(130) bs.Set(255) index, ok := bs.FirstSet() // index == 17, ok == true
Note: This implementation avoids a for loop for optimal speed. On modern CPUs, computing all four trailing-zero counts up front allows the CPU to parallelize these operations internally (pipelining), avoiding branch misprediction and maximizing instruction throughput. This technique is especially effective for bitsets with known, fixed word count.
func (*BitSet256) Intersection ¶ added in v0.19.0
Intersection computes the intersection of base set with the compare set. This is the BitSet equivalent of & (and).
func (*BitSet256) IntersectionTop ¶ added in v0.19.0
IntersectionTop computes the intersection of base set with the compare set. If the result set isn't empty, it returns the top most set bit and true.
func (*BitSet256) Intersects ¶ added in v0.20.5
Intersects returns true if the intersection of base set with the compare set is not the empty set.
func (*BitSet256) LastSet ¶ added in v0.23.1
LastSet returns the index of the highest (last) bit that is set in the BitSet256.
It searches the bitset in descending order and returns the position of the first bit (top bit) with value 1. If at least one bit is set, ok is true. If no bits are set, ok is false and last is undefined.
Example:
var bs BitSet256 bs.Set(2) bs.Set(130) bs.Set(214) index, ok := bs.LastSet() // index == 214, ok == true
func (*BitSet256) NextSet ¶ added in v0.19.0
NextSet returns the index of the next set bit that is greater than or equal to bit.
If such a bit exists, it returns its index as next and ok=true. Otherwise, ok is false and next is undefined.
The search starts at the given bit index and proceeds toward higher indices, scanning across all four 64-bit segments of the internal bitset representation.
Example:
b.Set(5) b.Set(130) b.NextSet(0) -> 5, true b.NextSet(5) -> 5, true b.NextSet(6) -> 130, true b.NextSet(200) -> 0, false
func (*BitSet256) Rank ¶ added in v0.20.3
Rank returns the number of bits set (i.e., value 1) in the BitSet256 up to and including the provided index.
The rank is computed efficiently using precomputed bitmasks (rankMask), which mask out all bits above the index. For example:
b.Set(3) b.Set(5) b.Set(120) b.Rank(5) -> 2 // only bits 3 and 5 are ≤ 5 b.Rank(119) -> 2 // only bits 3 and 5 are ≤ 119 b.Rank(120) -> 3 // bit 120 is included here
Rank is particularly useful in prefix trees, indexing schemes, and data compression techniques where ordinal positions matter.
Internally, the function performs four bitwise-and operations between the bitset words and a precomputed mask covering bits 0..idx, followed by popcount operations (via bits.OnesCount64).
This avoids dynamic mask construction and enables branch-free, highly predictable performance.
Source Files