readme.adoc
1= Bits
2
3Bits provides methods on a bit array type.
4
5The Bits type holds a fixed size array of bits, numbered consecutively
6from zero. Some set-like operations are possible, but the API is more
7array-like or register-like.
8
9image:https://godoc.org/github.com/soniakeys/bits?status.svg[link=https://godoc.org/github.com/soniakeys/bits] image:https://travis-ci.org/soniakeys/bits.svg[link=https://travis-ci.org/soniakeys/bits]
10
11== Motivation and history
12
13This package evolved from needs of my library of
14https://github.com/soniakeys/graph[graph algorithms]. For graph algorithms
15a common need is to store a single bit of information per node in a way that
16is both fast and memory efficient. I began by using `big.Int` from the standard
17library, then wrapped big.Int in a type. From time to time I considered
18other publicly available bit array or bit set packages, such as Will
19Fitzgerald's popular https://github.com/willf/bitset[bitset], but there were
20always little reasons I preferred my own type and methods. My type that
21wrapped `big.Int` met my needs until some simple benchmarks indicated it
22might be causing performance problems. Some further experiments supported
23this hypothesis so I ran further tests with a prototype bit array written
24from scratch. Then satisfied that my custom bit array was solving the graph
25performance problems, I decided to move it to a separate package with the
26idea it might have more general utility. For the initial version of this
27package I did the following:
28
29- implemented a few tests to demonstrate fundamental correctness
30- brought over most methods of my type that wrapped big.Int
31- changed the index type from the graph-specific node index to a general `int`
32- replaced some custom bit-twiddling with use of the new `math/bits` package
33 in the standard library
34- renamed a few methods for clarity
35- added a few methods for symmetry
36- added a few new methods I had seen a need for in my graph library
37- added doc, examples, tests, and more tests for 100% coverage
38- added this readme
39