Expand description
bitm
is the Rust library by Piotr Beling for bit and bitmap (bit vector) manipulation.
Example
use bitm::{BitAccess, BitVec, Rank, ArrayWithRank101111};
let mut b = Box::<[u64]>::with_zeroed_bits(2048); // b can store 2048 bits
assert_eq!(b.get_bit(100), false); // b is zeroed so bit at index 100 is not set
b.set_bit(100); // set the bit
assert_eq!(b.get_bit(100), true); // now it is set
assert_eq!(b.get_bits(99, 5), 0b00010); // 5 bits, beginning from index 99, should be 00010
let (r, ones) = ArrayWithRank101111::build(b);
assert_eq!(ones, 1); // one bit is set in b
assert_eq!(r.rank(100), 0); // no ones in the first 100 bits of b
assert_eq!(r.rank(101), 1); // 1 one in the first 101 bits of b
assert_eq!(r.rank(999), 1); // 1 one in the first 999 bits of b
Structs
- The structure that holds array of bits
content
andranks
structure that takes no more than 3.125% extra space. It can return the number of ones (or zeros) in firstindex
bits of thecontent
(seerank
andrank0
method) in O(1) time. In addition, it supports select queries utilizing binary search over ranks (seeBinaryRankSearch
) or (optionally, at the cost of about 0.39% extra space overhead) combined sampling (which is usually faster; seeCombinedSampling
). - The structure that holds array of bits
content
andranks
structure that takes no more than 6.25% extra space. It can returns the number of ones in firstindex
bits of thecontent
(seerank
method) in O(1) time. Onlycontent
with less than 2^32 bit ones is supported. - A select strategy for
ArrayWithRankSelect101111
that does not introduce any overhead (on space or construction speed) and is based on a binary search over ranks. - Iterator over indices of bits set to 1 (if
B
istrue
) or 0 (ifB
isfalse
) in slice ofu64
. - Iterator over bits in slice of
u64
. It yieldstrue
for bit 1 andfalse
for 0. - Fast select strategy for
ArrayWithRankSelect101111
with about 0.39% space overhead.
Traits
- The trait that is implemented for the array of
u64
and extends it with methods for accessing and modifying single bits or arbitrary fragments consisted of few (up to 63) bits. - The trait that is implemented for
Box<[u64]>
and extends it with bit-oriented constructors. - Trait for rank queries on bit vector. Rank query returns the number of ones (or zeros) in requested number of the first bits.
- Trait implemented by the types that support select (one) queries, i.e. can (quickly) find the position of the n-th one in the bitmap.
- Trait implemented by the types that support select zero queries, i.e. can (quickly) find the position of the n-th zero in the bitmap.
- Trait implemented by strategies for select zeros operations for
ArrayWithRank101111
. - Trait implemented by strategies for select (ones) operations for
ArrayWithRank101111
.
Functions
- Calculates the minimal number of bits needed to store values from
0
to givenmax_value
. - Returns ceil of
n/d
. - Returns the largest
how_many
-bit number, i.e. 0..01..1 mask withhow_many
ones.how_many
must be in range [0, 63]. - Returns the largest
how_many
-bit number, i.e. 0..01..1 mask withhow_many
ones.how_many
must be in range [0, 64]. - Returns the largest
how_many
-bit number, i.e. 0..01..1 mask withhow_many
ones.how_many
must be in range [1, 64]. - Returns the position of the
rank
-th (counting from 0) one in the bit representation ofn
, i.e. the index of the one with the given rank.
Type Aliases
ArrayWithRankSelect101111
withBinaryRankSearch
(which does not introduce a space overhead) for select queries.- Iterator over bits set to 1 in slice of
u64
. - Iterator over bits set to 0 in slice of
u64
.