1# bitset
2
3*Go language library to map between non-negative integers and boolean values*
4
5[](https://github.com/willf/bitset/actions?query=workflow%3ATest)
6[](https://goreportcard.com/report/github.com/willf/bitset)
7[](https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc)
8
9
10## Description
11
12Package bitset implements bitsets, a mapping between non-negative integers and boolean values.
13It should be more efficient than map[uint] bool.
14
15It provides methods for setting, clearing, flipping, and testing individual integers.
16
17But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of positive bits.
18
19BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.
20
21Many of the methods, including Set, Clear, and Flip, return a BitSet pointer, which allows for chaining.
22
23### Example use:
24
25```go
26package main
27
28import (
29 "fmt"
30 "math/rand"
31
32 "github.com/bits-and-blooms/bitset"
33)
34
35func main() {
36 fmt.Printf("Hello from BitSet!\n")
37 var b bitset.BitSet
38 // play some Go Fish
39 for i := 0; i < 100; i++ {
40 card1 := uint(rand.Intn(52))
41 card2 := uint(rand.Intn(52))
42 b.Set(card1)
43 if b.Test(card2) {
44 fmt.Println("Go Fish!")
45 }
46 b.Clear(card1)
47 }
48
49 // Chaining
50 b.Set(10).Set(11)
51
52 for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
53 fmt.Println("The following bit is set:", i)
54 }
55 if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {
56 fmt.Println("Intersection works.")
57 } else {
58 fmt.Println("Intersection doesn't work???")
59 }
60}
61```
62
63As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.
64
65Package documentation is at: https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc
66
67## Memory Usage
68
69The memory usage of a bitset using N bits is at least N/8 bytes. The number of bits in a bitset is at least as large as one plus the greatest bit index you have accessed. Thus it is possible to run out of memory while using a bitset. If you have lots of bits, you might prefer compressed bitsets, like the [Roaring bitmaps](http://roaringbitmap.org) and its [Go implementation](https://github.com/RoaringBitmap/roaring).
70
71## Implementation Note
72
73Go 1.9 introduced a native `math/bits` library. We provide backward compatibility to Go 1.7, which might be removed.
74
75It is possible that a later version will match the `math/bits` return signature for counts (which is `int`, rather than our library's `unit64`). If so, the version will be bumped.
76
77## Installation
78
79```bash
80go get github.com/bits-and-blooms/bitset
81```
82
83## Contributing
84
85If you wish to contribute to this project, please branch and issue a pull request against master ("[GitHub Flow](https://guides.github.com/introduction/flow/)")
86
87## Running all tests
88
89Before committing the code, please check if it passes tests, has adequate coverage, etc.
90```bash
91go test
92go test -cover
93```
View as plain text