README
¶
teivah/bitvector
Overview
A bit vector is an array data structure that compactly stores bits.
This library is based on 5 static different data structures:
- 8-bit vector: relies on an internal
uint8 - 16-bit vector: relies on an internal
uint16 - 32-bit vector: relies on an internal
uint32 - 64-bit vector: relies on an internal
uint64 - 128-bit vector: relies on two internal
uint64(for ASCII problems)
The rationale of using a static integer compared to a dynamic []byte is first of all to save memory.
There is no structure and/or slice overhead.
Hence, you might be interested in this library for memory-bound computation.
Also, the operations (get, set, etc.) are way more efficient. A simple benchmark shows that it's about 10 times more efficient than using a byte slice. Moreover, there is a guarantee that the internal bit vectors will not escape to the heap and remain only at the stack level.
Yet, the only drawback is to have a fixed-size bit vector (8, 16, 32, 64 or 128). If you require a dynamic bit vector, you should take a look at dropbox/godropbox for example.
Installation
go get github.com/teivah/bitvector
Documentation
Initialization
- 8-bit vector:
var bv bitvector.Len8
- 16-bit vector:
var bv bitvector.Len16
- 32-bit vector:
var bv bitvector.Len32
- 64-bit vector:
var bv bitvector.Len64
- 128-bit vector:
var bv bitvector.Ascii
// Or to reinitialize the bit vector
bv = bitvector.NewAscii()
Operations
- Set ith bit:
bv = bv.Set(i, true)
bv = bv.Set(i, false)
- Get ith bit:
b := bv.Get(i) // bool
- Toggle (flip) ith bit:
bv = bv.Toggle(i)
- Clear bits from index i (included) to index j (excluded):
bv = bv.Clear(i, j)
- Count the number of bits set to 1:
i := bv.Count() // uint8
- And operator:
bv := bv1.And(bv2)
- Or operator:
bv := bv1.Or(bv2)
- Xor operator:
bv := bv1.Xor(bv2)
- AndNot operator:
bv := bv1.AndNot(bv2)
- Push operator (left shift):
bv = bv.Push(2)
- Pop operator (right shift):
bv = bv.Pop(2)
- Convert the internal bit vector structure to a string:
s := bv.String() // string
Documentation
¶
Index ¶
- type Ascii
- func (bv Ascii) And(bv2 Ascii) Ascii
- func (bv Ascii) AndNot(bv2 Ascii) Ascii
- func (bv Ascii) Clear(i, j uint8) Ascii
- func (bv Ascii) Count() uint8
- func (bv Ascii) Get(i uint8) bool
- func (bv Ascii) Or(bv2 Ascii) Ascii
- func (bv Ascii) Set(i uint8, b bool) Ascii
- func (bv Ascii) String() string
- func (bv Ascii) Toggle(i uint8) Ascii
- func (bv Ascii) Xor(bv2 Ascii) Ascii
- type Len16
- func (bv Len16) And(bv2 Len16) Len16
- func (bv Len16) AndNot(bv2 Len16) Len16
- func (bv Len16) Clear(i, j uint8) Len16
- func (bv Len16) Count() uint8
- func (bv Len16) Get(i uint8) bool
- func (bv Len16) Or(bv2 Len16) Len16
- func (bv Len16) Pop(i uint8) Len16
- func (bv Len16) Push(i uint8) Len16
- func (bv Len16) Set(i uint8, b bool) Len16
- func (bv Len16) String() string
- func (bv Len16) Toggle(i uint8) Len16
- func (bv Len16) Xor(bv2 Len16) Len16
- type Len32
- func (bv Len32) And(bv2 Len32) Len32
- func (bv Len32) AndNot(bv2 Len32) Len32
- func (bv Len32) Clear(i, j uint8) Len32
- func (bv Len32) Count() uint8
- func (bv Len32) Get(i uint8) bool
- func (bv Len32) Or(bv2 Len32) Len32
- func (bv Len32) Pop(i uint8) Len32
- func (bv Len32) Push(i uint8) Len32
- func (bv Len32) Set(i uint8, b bool) Len32
- func (bv Len32) String() string
- func (bv Len32) Toggle(i uint8) Len32
- func (bv Len32) Xor(bv2 Len32) Len32
- type Len64
- func (bv Len64) And(bv2 Len64) Len64
- func (bv Len64) AndNot(bv2 Len64) Len64
- func (bv Len64) Clear(i, j uint8) Len64
- func (bv Len64) Count() uint8
- func (bv Len64) Get(i uint8) bool
- func (bv Len64) Or(bv2 Len64) Len64
- func (bv Len64) Pop(i uint8) Len64
- func (bv Len64) Push(i uint8) Len64
- func (bv Len64) Set(i uint8, b bool) Len64
- func (bv Len64) String() string
- func (bv Len64) Toggle(i uint8) Len64
- func (bv Len64) Xor(bv2 Len64) Len64
- type Len8
- func (bv Len8) And(bv2 Len8) Len8
- func (bv Len8) AndNot(bv2 Len8) Len8
- func (bv Len8) Clear(i, j uint8) Len8
- func (bv Len8) Count() uint8
- func (bv Len8) Get(i uint8) bool
- func (bv Len8) Or(bv2 Len8) Len8
- func (bv Len8) Pop(i uint8) Len8
- func (bv Len8) Push(i uint8) Len8
- func (bv Len8) Set(i uint8, b bool) Len8
- func (bv Len8) String() string
- func (bv Len8) Toggle(i uint8) Len8
- func (bv Len8) Xor(bv2 Len8) Len8
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Ascii ¶
type Ascii [2]Len64
Ascii is a 64-bit vector
type Len16 ¶
type Len16 uint16
Len16 is a 16-bit vector
type Len32 ¶
type Len32 uint32
Len32 is a 32-bit vector
type Len64 ¶
type Len64 uint64
Len64 is a 64-bit vector
Source Files