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 for the range [0..255], stored as four uint64 words (256 bits total).
func (*BitSet256) AsSlice ¶ added in v0.19.0
AsSlice extracts the indices of all set bits in the BitSet256, returning them as uint8 values in strictly ascending order.
Performance Considerations: To guarantee zero heap allocations and enable compiler inlining, the caller must provide a pointer to a 256-byte array (`buf`) as backing storage. The method populates this array in-place and returns a sliced view (`[]uint8`) tailored to the actual number of set bits.
Safety and Lifecycle: The returned slice directly shares the underlying storage of `buf` and is only valid until `buf` is modified or reused. This pattern is highly recommended for hot paths and performance-critical loops where heap churn must be avoided.
func (*BitSet256) Bits ¶ added in v0.20.5
Bits returns a slice containing the indices of all set bits in strictly ascending order as uint8 values.
Performance Considerations: Unlike [AsSlice], this method dynamically allocates a new slice on the heap to store the result. It is designed for convenience and APIs where the lifecycle of the returned slice needs to outlive the immediate caller's stack frame.
Usage Guidance: Use Bits when convenience is preferred over raw performance, or when the result must be returned across boundaries where stack-allocated buffers cannot safely escape. For high-throughput or allocation-free processing, prefer [AsSlice].
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 returns a new BitSet256 containing only the bits that are set in both the receiver and c (bitwise AND).
func (*BitSet256) IntersectionTop ¶ added in v0.19.0
IntersectionTop computes the intersection of the receiver with c and returns the highest (top-most) set bit of the result. If the intersection is non-empty, it returns the top bit index and true. If the intersection is empty, ok is false and top is 0.
func (*BitSet256) Intersects ¶ added in v0.20.5
Intersects reports whether the receiver and c have at least one bit in common.
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 0.
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.
func (*BitSet256) Size ¶ added in v0.19.0
Size returns the population count, i.e. the number of set bits.
Source Files