bitset: a Go library for dense, fast integer-to-boolean sets

What this repository is

bits-and-blooms/bitset is a Go package that implements a *dense* bitset: a mapping between non-negative integers and boolean values. The README states plainly what it competes with — "It should be more efficient than map[uint] bool." The README says it should be more efficient than map[uint] bool; this library packs one bit per integer into a slice of 64-bit words.

The zero value is an empty set of length 0. Internally the type is small:

type BitSet struct {
	length uint
	set    []uint64
}

Bitsets grow to fit their largest set bit and are never shrunk automatically; Shrink and Compact exist for when you want memory back. A creation hint (New(length)) sizes the backing array up front, so callers who know their working range can avoid reallocation.

The package is BSD-3-Clause licensed, declares Go 1.16 in its module file, and tracks at release v1.29.0 with a last commit of October 2026.

What it does

Individual operations cover the expected surface: Set, Clear, Flip and Test. Many methods, including Set, Clear and Flip, return a *BitSet pointer, which enables chaining:

b.Set(10).Set(11)

Beyond single bits there is real set algebra — intersection, union, difference, complement and symmetric difference — plus predicates to ask whether any, all or no bits are set, and queries for current length (Len) and number of positive bits (Count).

Navigation methods such as NextSet and PreviousClear navigate the bitset in either direction. On Go 1.23+ there is also a range-over-function iterator:

for i := range b.EachSet() {}

The implementation leans on hardware-friendly primitives. Population counting (popcnt.go) uses math/bits.OnesCount64 with four independent accumulators to break the dependency chain and let the CPU run several popcounts in parallel. A rank/select helper (select.go) finds the position of a given set bit through divide-and-conquer over 32-, 16- and 8-bit halves rather than scanning word by word.

A generated file, pext.gen.go, holds precomputed lookup tables for parallel bit extraction (pextLUT), its inverse pdepLUT, and a byte population-count table popLUT. It is produced by the small generator in cmd/pextgen/main.go:

go run cmd/pextgen/main.go -pkg=bitset

The file carries the standard "DO NOT EDIT" header, so contributors regenerate rather than hand-edit tables.

Serialization and interop

Bitsets serialize portably to a stream of bytes through WriteTo and read back with ReadFrom. The README shows the round trip: write into a buffer (or file), later read it back. ReadFrom tries to reuse the existing backing array "to minimize memory allocations." For network or disk use, the docs recommend wrapping streams in bufio.

The package also implements Go's standard marshaling interfaces — MarshalBinary/UnmarshalBinary, and JSON via base64-encoded bytes. Byte order defaults to big-endian but can be switched with LittleEndian(); JSON uses URL-safe base64 by default, changeable through Base64StdEncoding(). These are package-level switches that affect subsequent marshal/unmarshal calls.

For large bitsets, the README suggests compressed alternatives such as Roaring bitmaps. The companion RoaringBitmap/roaring library converts both ways (ToBitSet() and FromBitSet), so dense and compressed representations can hand off to each other.

Concurrency

The package is deliberately unsynchronized. "In general, it's not safe to access the same BitSet using different goroutines — they are unsynchronized for performance." The guidance is either to pass a single *BitSet around by channel (one owner at a time) or to guard operations with a sync.Mutex.

Testing

The repository takes verification seriously. Beyond the main test file there is a dedicated fuzz suite (bitset_fuzz_test.go, gated on Go 1.18+) and a shell script, run_fuzz_tests.sh, that runs twelve named fuzz targets — among them FuzzBasicOps, FuzzSetOperations, FuzzNavigation, FuzzShift, FuzzSerialization and FuzzRandomOperations. The generator in cmd/pextgen has its own tests, including a round-trip check that pdepByte(pextByte(b, m), m) returns the original byte masked by m.

The README's contribution note asks for GitHub Flow — branch and pull request against master — and to run go test (and go test -cover) before committing.

Who uses it

The README lists a long roster of production users across categories: databases and storage (milvus-io/milvus, cubefs/cubefs, defradb), search and indexing (blevesearch/bleve, bluge), blockchain and cryptography (consensys/gnark, cosmos-sdk, onflow/cadence), infrastructure and networking (Docker's swarmkit, coredhcp, Alibaba's terway), distributed systems (apache/pulsar-client-go, dragonfly), machine learning vector search, and developer tools including Hugo. The listed uses include IP allocation bitmaps, ID management, the Cosmos SDK slashing module, and AST traversal.

Getting started

go get github.com/bits-and-blooms/bitset

A minimal program from the README plays a card game to demonstrate Set, Test and Clear, then chains Set calls and walks the bitset with NextSet. The package documentation lives on pkg.go.dev.

The trade-off worth remembering before adopting it: memory is proportional to the *largest* bit you touch, not how many bits are set. A single high index costs as much as a full range up to it. For sparse or enormous universes, Roaring-style compression — with which this library interoperates directly — may be the better fit.