| 1 |
<!DOCTYPE html> |
| 2 |
<html lang="en"> |
| 3 |
<head> |
| 4 |
<meta charset="UTF-8"> |
| 5 |
<meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| 6 |
<title>bitset — fast Go bitsets</title> |
| 7 |
<meta name="description" content="A high-performance Go library that maps between non-negative integers and boolean values. Set operations, serialization, and SIMD-accelerated routines."> |
| 8 |
<meta name="theme-color" content="#0d1117"> |
| 9 |
|
| 10 |
<!-- Open Graph --> |
| 11 |
<meta property="og:title" content="bitset — fast Go bitsets"> |
| 12 |
<meta property="og:description" content="A high-performance Go library mapping non-negative integers to boolean values, with rich set operations and portable serialization."> |
| 13 |
<meta property="og:type" content="website"> |
| 14 |
<meta property="og:url" content="https://bits-and-blooms.github.io/bitset/"> |
| 15 |
|
| 16 |
<link rel="preconnect" href="https://fonts.googleapis.com"> |
| 17 |
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin> |
| 18 |
<link href="https://fonts.googleapis.com/css2?family=Inter:wght@400;500;600;700;800&family=JetBrains+Mono:wght@400;500;700&display=swap" rel="stylesheet"> |
| 19 |
|
| 20 |
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/styles/github-dark.min.css"> |
| 21 |
<link rel="stylesheet" href="style.css"> |
| 22 |
</head> |
| 23 |
<body> |
| 24 |
|
| 25 |
<header class="nav" id="top"> |
| 26 |
<div class="wrap nav-inner"> |
| 27 |
<a class="brand" href="#top"> |
| 28 |
<span class="brand-mark" aria-hidden="true"> |
| 29 |
<span></span><span></span><span></span><span></span> |
| 30 |
<span></span><span></span><span></span><span></span> |
| 31 |
</span> |
| 32 |
<span class="brand-name">bitset</span> |
| 33 |
</a> |
| 34 |
<nav class="nav-links"> |
| 35 |
<a href="#features">Features</a> |
| 36 |
<a href="#usage">Usage</a> |
| 37 |
<a href="#serialization">Serialization</a> |
| 38 |
<a href="#usedby">Used by</a> |
| 39 |
<a class="nav-cta" href="https://github.com/bits-and-blooms/bitset" target="_blank" rel="noopener">GitHub ↗</a> |
| 40 |
</nav> |
| 41 |
<button class="nav-toggle" id="navToggle" aria-label="Toggle menu" aria-expanded="false"> |
| 42 |
<span></span><span></span><span></span> |
| 43 |
</button> |
| 44 |
</div> |
| 45 |
</header> |
| 46 |
|
| 47 |
<main> |
| 48 |
|
| 49 |
<!-- HERO --> |
| 50 |
<section class="hero"> |
| 51 |
<div class="hero-bg" aria-hidden="true"></div> |
| 52 |
<div class="wrap hero-inner"> |
| 53 |
<div class="hero-copy"> |
| 54 |
<p class="eyebrow">Go library · BSD-style license</p> |
| 55 |
<h1>Bitsets, done <span class="grad">fast</span> in Go.</h1> |
| 56 |
<p class="lede"> |
| 57 |
A compact, high-performance mapping between non-negative integers and boolean |
| 58 |
values — far leaner than <code>map[uint]bool</code>. Set, clear, flip, test, |
| 59 |
and run union / intersection / difference at native speed. |
| 60 |
</p> |
| 61 |
|
| 62 |
<div class="cta-row"> |
| 63 |
<a class="btn btn-primary" href="#usage">Get started</a> |
| 64 |
<a class="btn btn-ghost" href="https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc" target="_blank" rel="noopener">API docs ↗</a> |
| 65 |
</div> |
| 66 |
|
| 67 |
<div class="install"> |
| 68 |
<code id="installCmd">go get github.com/bits-and-blooms/bitset</code> |
| 69 |
<button class="copy" data-copy="go get github.com/bits-and-blooms/bitset" aria-label="Copy install command">Copy</button> |
| 70 |
</div> |
| 71 |
|
| 72 |
<div class="badges"> |
| 73 |
<a href="https://github.com/bits-and-blooms/bitset/actions?query=workflow%3ATest" target="_blank" rel="noopener"> |
| 74 |
<img src="https://github.com/bits-and-blooms/bitset/workflows/Test/badge.svg" alt="Test status" loading="lazy"></a> |
| 75 |
<a href="https://goreportcard.com/report/github.com/bits-and-blooms/bitset" target="_blank" rel="noopener"> |
| 76 |
<img src="https://goreportcard.com/badge/github.com/bits-and-blooms/bitset" alt="Go Report Card" loading="lazy"></a> |
| 77 |
<a href="https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc" target="_blank" rel="noopener"> |
| 78 |
<img src="https://pkg.go.dev/badge/github.com/bits-and-blooms/bitset?tab=doc" alt="Go Reference" loading="lazy"></a> |
| 79 |
</div> |
| 80 |
</div> |
| 81 |
|
| 82 |
<div class="hero-card" aria-hidden="false"> |
| 83 |
<div class="code-card"> |
| 84 |
<div class="code-head"> |
| 85 |
<span class="dot r"></span><span class="dot y"></span><span class="dot g"></span> |
| 86 |
<span class="code-file">main.go</span> |
| 87 |
</div> |
| 88 |
<pre><code class="language-go">var b bitset.BitSet |
| 89 |
b.Set(10).Set(11).Set(1000) |
| 90 |
|
| 91 |
if b.Test(11) { |
| 92 |
fmt.Println("bit 11 is set") |
| 93 |
} |
| 94 |
|
| 95 |
// rich set algebra |
| 96 |
hits := b.Intersection(other).Count() |
| 97 |
|
| 98 |
// iterate set bits (Go 1.23+) |
| 99 |
for i := range b.EachSet() { |
| 100 |
fmt.Println("set:", i) |
| 101 |
}</code></pre> |
| 102 |
</div> |
| 103 |
</div> |
| 104 |
</div> |
| 105 |
|
| 106 |
<div class="wrap stats"> |
| 107 |
<div class="stat"><span class="num">1 bit</span><span class="lbl">per element</span></div> |
| 108 |
<div class="stat"><span class="num">60+</span><span class="lbl">methods</span></div> |
| 109 |
<div class="stat"><span class="num">SIMD</span><span class="lbl">accelerated</span></div> |
| 110 |
<div class="stat"><span class="num">Go 1.16+</span><span class="lbl">supported</span></div> |
| 111 |
</div> |
| 112 |
</section> |
| 113 |
|
| 114 |
<!-- FEATURES --> |
| 115 |
<section id="features" class="section"> |
| 116 |
<div class="wrap"> |
| 117 |
<p class="kicker">Why bitset</p> |
| 118 |
<h2 class="section-title">Everything you need to push bits around</h2> |
| 119 |
<div class="grid features"> |
| 120 |
|
| 121 |
<article class="feat"> |
| 122 |
<div class="feat-ico">⚡</div> |
| 123 |
<h3>Memory efficient</h3> |
| 124 |
<p>Roughly one bit of storage per element — orders of magnitude smaller than a hash map of booleans, with cache-friendly word layout.</p> |
| 125 |
</article> |
| 126 |
|
| 127 |
<article class="feat"> |
| 128 |
<div class="feat-ico">🧮</div> |
| 129 |
<h3>Full set algebra</h3> |
| 130 |
<p>Union, intersection, difference, symmetric difference and complement — each with in-place and cardinality-only variants.</p> |
| 131 |
</article> |
| 132 |
|
| 133 |
<article class="feat"> |
| 134 |
<div class="feat-ico">🔗</div> |
| 135 |
<h3>Chainable API</h3> |
| 136 |
<p><code>Set</code>, <code>Clear</code>, and <code>Flip</code> return the bitset, so mutations read naturally: <code>b.Set(10).Set(11)</code>.</p> |
| 137 |
</article> |
| 138 |
|
| 139 |
<article class="feat"> |
| 140 |
<div class="feat-ico">🔁</div> |
| 141 |
<h3>Fast iteration</h3> |
| 142 |
<p>Walk set or clear bits with <code>NextSet</code> / <code>NextClear</code>, or range over <code>EachSet()</code> on Go 1.23+.</p> |
| 143 |
</article> |
| 144 |
|
| 145 |
<article class="feat"> |
| 146 |
<div class="feat-ico">💾</div> |
| 147 |
<h3>Portable serialization</h3> |
| 148 |
<p><code>WriteTo</code> / <code>ReadFrom</code> give a stable byte layout across platforms, plus <code>MarshalBinary</code> and JSON support.</p> |
| 149 |
</article> |
| 150 |
|
| 151 |
<article class="feat"> |
| 152 |
<div class="feat-ico">🚀</div> |
| 153 |
<h3>Battle-tested</h3> |
| 154 |
<p>Fuzz-tested and used in production by databases, search engines, blockchains and CNCF projects worldwide.</p> |
| 155 |
</article> |
| 156 |
|
| 157 |
</div> |
| 158 |
</div> |
| 159 |
</section> |
| 160 |
|
| 161 |
<!-- USAGE --> |
| 162 |
<section id="usage" class="section section-alt"> |
| 163 |
<div class="wrap"> |
| 164 |
<p class="kicker">Quick start</p> |
| 165 |
<h2 class="section-title">From zero to bits in seconds</h2> |
| 166 |
|
| 167 |
<div class="steps"> |
| 168 |
<div class="step"> |
| 169 |
<span class="step-n">1</span> |
| 170 |
<div> |
| 171 |
<h3>Install</h3> |
| 172 |
<div class="code-card mini"> |
| 173 |
<pre><code class="language-bash">go get github.com/bits-and-blooms/bitset</code></pre> |
| 174 |
</div> |
| 175 |
</div> |
| 176 |
</div> |
| 177 |
|
| 178 |
<div class="step"> |
| 179 |
<span class="step-n">2</span> |
| 180 |
<div> |
| 181 |
<h3>Use it</h3> |
| 182 |
<div class="code-card mini"> |
| 183 |
<pre><code class="language-go">package main |
| 184 |
|
| 185 |
import ( |
| 186 |
"fmt" |
| 187 |
"math/rand" |
| 188 |
|
| 189 |
"github.com/bits-and-blooms/bitset" |
| 190 |
) |
| 191 |
|
| 192 |
func main() { |
| 193 |
var b bitset.BitSet |
| 194 |
|
| 195 |
// play some Go Fish |
| 196 |
for i := 0; i < 100; i++ { |
| 197 |
card1 := uint(rand.Intn(52)) |
| 198 |
card2 := uint(rand.Intn(52)) |
| 199 |
b.Set(card1) |
| 200 |
if b.Test(card2) { |
| 201 |
fmt.Println("Go Fish!") |
| 202 |
} |
| 203 |
b.Clear(card1) |
| 204 |
} |
| 205 |
|
| 206 |
// chaining |
| 207 |
b.Set(10).Set(11) |
| 208 |
|
| 209 |
for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) { |
| 210 |
fmt.Println("the following bit is set:", i) |
| 211 |
} |
| 212 |
|
| 213 |
if b.Intersection(bitset.New(100).Set(10)).Count() == 1 { |
| 214 |
fmt.Println("intersection works.") |
| 215 |
} |
| 216 |
}</code></pre> |
| 217 |
</div> |
| 218 |
</div> |
| 219 |
</div> |
| 220 |
</div> |
| 221 |
</div> |
| 222 |
</section> |
| 223 |
|
| 224 |
<!-- SERIALIZATION --> |
| 225 |
<section id="serialization" class="section"> |
| 226 |
<div class="wrap two-col"> |
| 227 |
<div class="two-col-text"> |
| 228 |
<p class="kicker">Serialization</p> |
| 229 |
<h2 class="section-title">Save and restore, portably</h2> |
| 230 |
<p class="prose"> |
| 231 |
Serialize a bitset to a stable, platform-independent stream of bytes with |
| 232 |
<code>WriteTo</code>, then read it back with <code>ReadFrom</code> — which |
| 233 |
reuses the existing instance to minimize allocations. |
| 234 |
</p> |
| 235 |
<p class="prose tip"> |
| 236 |
<strong>Performance tip:</strong> wrap files and network connections in |
| 237 |
<code>bufio</code> readers and writers for the best throughput. |
| 238 |
</p> |
| 239 |
<a class="btn btn-ghost" href="https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc" target="_blank" rel="noopener">Full API reference ↗</a> |
| 240 |
</div> |
| 241 |
<div class="two-col-code"> |
| 242 |
<div class="code-card"> |
| 243 |
<div class="code-head"> |
| 244 |
<span class="dot r"></span><span class="dot y"></span><span class="dot g"></span> |
| 245 |
<span class="code-file">serialize.go</span> |
| 246 |
</div> |
| 247 |
<pre><code class="language-go">bs := bitset.New(9585) |
| 248 |
for i := uint(0); i < 9585; i += 97 { |
| 249 |
bs = bs.Set(i) |
| 250 |
} |
| 251 |
|
| 252 |
// write |
| 253 |
var buf bytes.Buffer |
| 254 |
n, err := bs.WriteTo(&buf) |
| 255 |
|
| 256 |
// read back into an existing bitset |
| 257 |
bs = bitset.New() |
| 258 |
n, err = bs.ReadFrom(&buf)</code></pre> |
| 259 |
</div> |
| 260 |
</div> |
| 261 |
</div> |
| 262 |
</section> |
| 263 |
|
| 264 |
<!-- USED BY --> |
| 265 |
<section id="usedby" class="section section-alt"> |
| 266 |
<div class="wrap"> |
| 267 |
<p class="kicker">In production</p> |
| 268 |
<h2 class="section-title">Trusted by demanding systems</h2> |
| 269 |
<p class="prose center"> |
| 270 |
Part of the <a href="https://github.com/avelino/awesome-go" target="_blank" rel="noopener">awesome-go</a> |
| 271 |
collection and depended on across databases, search, blockchain and infrastructure. |
| 272 |
</p> |
| 273 |
|
| 274 |
<div class="grid logos"> |
| 275 |
<a class="logo" href="https://github.com/milvus-io/milvus" target="_blank" rel="noopener"><b>Milvus</b><span>Vector database</span></a> |
| 276 |
<a class="logo" href="https://github.com/blevesearch/bleve" target="_blank" rel="noopener"><b>Bleve</b><span>Full-text search</span></a> |
| 277 |
<a class="logo" href="https://github.com/consensys/gnark" target="_blank" rel="noopener"><b>gnark</b><span>zk-SNARKs</span></a> |
| 278 |
<a class="logo" href="https://github.com/cosmos/cosmos-sdk" target="_blank" rel="noopener"><b>Cosmos SDK</b><span>Blockchain SDK</span></a> |
| 279 |
<a class="logo" href="https://github.com/gohugoio/hugo" target="_blank" rel="noopener"><b>Hugo</b><span>Static sites</span></a> |
| 280 |
<a class="logo" href="https://github.com/moby/swarmkit" target="_blank" rel="noopener"><b>SwarmKit</b><span>Docker Swarm</span></a> |
| 281 |
<a class="logo" href="https://github.com/apache/pulsar-client-go" target="_blank" rel="noopener"><b>Apache Pulsar</b><span>Messaging</span></a> |
| 282 |
<a class="logo" href="https://github.com/cubefs/cubefs" target="_blank" rel="noopener"><b>CubeFS</b><span>CNCF storage</span></a> |
| 283 |
<a class="logo" href="https://github.com/NVIDIA/dcgm-exporter" target="_blank" rel="noopener"><b>NVIDIA DCGM</b><span>GPU metrics</span></a> |
| 284 |
<a class="logo" href="https://github.com/pomerium/pomerium" target="_blank" rel="noopener"><b>Pomerium</b><span>Access proxy</span></a> |
| 285 |
<a class="logo" href="https://github.com/RoaringBitmap/roaring" target="_blank" rel="noopener"><b>Roaring</b><span>Compressed bitmaps</span></a> |
| 286 |
<a class="logo" href="https://github.com/zhenghaoz/gorse" target="_blank" rel="noopener"><b>gorse</b><span>Recommenders</span></a> |
| 287 |
</div> |
| 288 |
<p class="prose center muted small">…and many more across the Go ecosystem.</p> |
| 289 |
</div> |
| 290 |
</section> |
| 291 |
|
| 292 |
<!-- MEMORY / ROARING NOTE --> |
| 293 |
<section class="section"> |
| 294 |
<div class="wrap callout"> |
| 295 |
<div> |
| 296 |
<h2 class="section-title small-title">Working with billions of bits?</h2> |
| 297 |
<p class="prose"> |
| 298 |
A bitset of <code>N</code> bits uses at least <code>N/8</code> bytes and grows to fit the |
| 299 |
largest index you touch. For very large, sparse sets, consider compressed |
| 300 |
<a href="https://roaringbitmap.org" target="_blank" rel="noopener">Roaring bitmaps</a> — you can convert |
| 301 |
freely between the two. |
| 302 |
</p> |
| 303 |
</div> |
| 304 |
<a class="btn btn-primary" href="https://github.com/RoaringBitmap/roaring" target="_blank" rel="noopener">Roaring for Go ↗</a> |
| 305 |
</div> |
| 306 |
</section> |
| 307 |
|
| 308 |
<!-- BOOK AD --> |
| 309 |
<section class="section section-alt" id="book"> |
| 310 |
<div class="wrap book"> |
| 311 |
<a class="book-cover" href="https://www.amazon.com/dp/B0FMPGSWR5" target="_blank" rel="noopener"> |
| 312 |
<img src="https://m.media-amazon.com/images/I/61feneHS7kL._SL1499_.jpg" |
| 313 |
alt="Mastering Programming: From Testing to Performance in Go — book cover"> |
| 314 |
</a> |
| 315 |
<div class="book-copy"> |
| 316 |
<p class="kicker">Go deeper</p> |
| 317 |
<h2 class="section-title small-title">Mastering Programming:<br>From Testing to Performance in Go</h2> |
| 318 |
<p class="prose"> |
| 319 |
Want to write Go like the code behind <strong>bitset</strong>? This book takes you |
| 320 |
from solid testing practices all the way to squeezing real performance out of Go — |
| 321 |
the same techniques used to keep this library fast. |
| 322 |
</p> |
| 323 |
<a class="btn btn-primary" href="https://www.amazon.com/dp/B0FMPGSWR5" target="_blank" rel="noopener">Get the book on Amazon ↗</a> |
| 324 |
</div> |
| 325 |
</div> |
| 326 |
</section> |
| 327 |
|
| 328 |
</main> |
| 329 |
|
| 330 |
<footer class="footer"> |
| 331 |
<div class="wrap footer-inner"> |
| 332 |
<div class="footer-brand"> |
| 333 |
<span class="brand-mark small" aria-hidden="true"> |
| 334 |
<span></span><span></span><span></span><span></span> |
| 335 |
<span></span><span></span><span></span><span></span> |
| 336 |
</span> |
| 337 |
<div> |
| 338 |
<strong>bitset</strong> |
| 339 |
<p class="muted small">Map non-negative integers to booleans, fast.</p> |
| 340 |
</div> |
| 341 |
</div> |
| 342 |
<nav class="footer-links"> |
| 343 |
<a href="https://github.com/bits-and-blooms/bitset" target="_blank" rel="noopener">GitHub</a> |
| 344 |
<a href="https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc" target="_blank" rel="noopener">Documentation</a> |
| 345 |
<a href="https://github.com/bits-and-blooms/bitset/issues" target="_blank" rel="noopener">Issues</a> |
| 346 |
<a href="https://github.com/bits-and-blooms/bitset/blob/master/LICENSE" target="_blank" rel="noopener">License</a> |
| 347 |
</nav> |
| 348 |
</div> |
| 349 |
<div class="wrap footer-bottom"> |
| 350 |
<p class="muted small">BSD-style license</p> |
| 351 |
</div> |
| 352 |
</footer> |
| 353 |
|
| 354 |
<a class="totop" href="#top" id="toTop" aria-label="Back to top">↑</a> |
| 355 |
|
| 356 |
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.9.0/highlight.min.js"></script> |
| 357 |
<script src="main.js"></script> |
| 358 |
</body> |
| 359 |
</html> |