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.
For external consumers, the API intentionally avoids dynamic allocation except when explicitly requested (via Bits()).
Index ¶
- type BitSet256
- func (b *BitSet256) AlignedPairs() BitSet256
- func (b *BitSet256) All() iter.Seq[uint8]
- func (b *BitSet256) AllEnumerate() iter.Seq2[uint8, uint8]
- func (b *BitSet256) And(c *BitSet256) (bs BitSet256)
- func (b *BitSet256) AndTop(c *BitSet256) (top uint8, ok bool)
- func (b *BitSet256) AppendBits(buf []uint8) []uint8
- func (b *BitSet256) Bits() []uint8
- func (b *BitSet256) Clear(bit uint8)
- func (b *BitSet256) FirstSet() (first uint8, ok bool)
- func (b *BitSet256) IsEmpty() bool
- func (b *BitSet256) LastSet() (last uint8, ok bool)
- func (b *BitSet256) LeftShift()
- func (b *BitSet256) NextSet(bit uint8) (next uint8, ok bool)
- func (b *BitSet256) OnesCount() int
- func (b *BitSet256) Or(c *BitSet256) (bs BitSet256)
- func (b *BitSet256) Overlaps(c *BitSet256) bool
- func (b *BitSet256) Rank(idx uint8) int
- func (b *BitSet256) RightShift()
- func (b *BitSet256) Set(bit uint8)
- func (b *BitSet256) Test(bit uint8) (ok bool)
- func (b *BitSet256) Xor(c *BitSet256) (bs 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) AlignedPairs ¶ added in v0.29.1
AlignedPairs returns a new BitSet256 where bit n is set if and only if n is EVEN, and both bit n and bit n+1 were set in the original bitset.
func (*BitSet256) All ¶ added in v0.19.0
All returns an iterator over the indices of all set bits in the BitSet256 in strictly ascending order.
Note on Dense BitSets: While iter.Seq provides clean iterator semantics and supports early breaking, calling yield() in a dense iteration loop introduces slight state-machine and yield-inlining overhead compared to batch writes. For maximum throughput in dense bitsets, consider using AppendBits with a pre-allocated slice buffer.
func (*BitSet256) AllEnumerate ¶ added in v0.29.1
AllEnumerate returns a pair iterator yielding a zero-based iteration sequence number and the bit index for each set bit in the BitSet256 in strictly ascending order.
See BitSet256.All for performance considerations on dense bitsets.
func (*BitSet256) And ¶ added in v0.30.0
And returns a new BitSet256 representing the bitwise intersection (AND) of b and c. It performs a component-wise bitwise AND operation across all words and leaves the original receiver unchanged.
func (*BitSet256) AndTop ¶ added in v0.30.0
AndTop 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) AppendBits ¶ added in v0.29.1
AppendBits appends the indices of all set bits in the BitSet256 to buf in strictly ascending order and returns the extended slice.
Performance Considerations: To achieve zero heap allocations in performance-critical loops, the caller should pass a slice backed by stack memory (e.g., slicing a local array `buf[:0]` or a pre-allocated buffer). The function appends directly to `buf`, avoiding heap churn if `cap(buf)` is sufficient.
Safety and Lifecycle: If `buf` has sufficient capacity, the returned slice shares its underlying storage. If capacity is exceeded, standard slice growth rules apply and a new backing array will be allocated.
func (*BitSet256) Bits ¶ added in v0.20.5
Bits returns a newly allocated slice containing the indices of all set bits in strictly ascending order as uint8 values.
Performance Considerations: Unlike [AppendBits], this method allocates backing storage on the heap. It is designed for convenience when caller lifecycle management across stack boundaries is required.
For high-throughput or allocation-free processing in hot paths, prefer [AppendBits].
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) 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) LeftShift ¶ added in v0.29.1
func (b *BitSet256) LeftShift()
LeftShift shifts all bits in the bitset to the left by exactly 1 bit in-place.
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) OnesCount ¶ added in v0.29.1
OnesCount returns the population count, i.e. the number of set bits.
func (*BitSet256) Or ¶ added in v0.30.0
Or returns a new BitSet256 representing the bitwise union (OR) of b and c. It performs a component-wise bitwise OR operation across all words and leaves the original receiver unchanged.
func (*BitSet256) Overlaps ¶ added in v0.30.0
Overlaps reports whether the receiver and c have at least one bit in common.
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) RightShift ¶ added in v0.29.1
func (b *BitSet256) RightShift()
RightShift shifts all bits in the bitset to the right by exactly 1 bit in-place.
Source Files