20 releases
0.5.7 | May 25, 2024 |
---|---|
0.5.6 | Mar 22, 2023 |
0.5.4 | Jan 18, 2023 |
0.4.3 | Dec 7, 2022 |
0.1.1 | Mar 31, 2021 |
#353 in Data structures
48 downloads per month
Used in 2 crates
130KB
2K
SLoC
bittle
Zero-cost bitsets over native Rust types.
The name bittle
comes from bit
and little
. Small bitsets!
Usage
Add bittle
as a dependency in your Cargo.toml
:
[dependencies]
bittle = "0.5.7"
Guide
A bit is always identified by a u32
by its index, and the exact location
for a bit in a primitive numbers is defined by its endianness, which is
BigEndian
by default.
BigEndian
indexing grows from right to left, such as the following
u8
literal:
0b0010_0010u8
^ ^- index 1
'------ index 5
To interact with these bits we define the Bits
, BitsMut
, and
BitsOwned
traits. These traits are implemented for primitive types such
as u32
, [u32; 4]
, or &[u32]
:
use bittle::Bits;
let array: [u32; 4] = [0, 1, 2, 3];
assert!(array.iter_ones().eq([32, 65, 96, 97]));
let n = 0b00000000_00000000_00000000_00010001u32;
assert!(n.iter_ones().eq([0, 4]));
let array_of_arrays: [[u8; 4]; 2] = [[16, 0, 0, 0], [0, 0, 1, 0]];
assert!(array_of_arrays.iter_ones().eq([4, 48]));
let mut vec: Vec<u32> = vec![0, 1, 2, 3];
assert!(vec.iter_ones().eq([32, 65, 96, 97]));
We also provide the set!
macro, which is a zero-cost convenience method
for constructing primitive forms of bit sets:
use bittle::Bits;
let array: [u32; 4] = bittle::set![32, 65, 96, 97];
assert!(array.iter_ones().eq([32, 65, 96, 97]));
let n: u32 = bittle::set![0, 4];
assert!(n.iter_ones().eq([0, 4]));
let array_of_arrays: [[u8; 4]; 2] = bittle::set![4, 48];
assert!(array_of_arrays.iter_ones().eq([4, 48]));
Since a vector is not a primitive bit set, it could instead make use of
BitsMut
directly:
use bittle::{Bits, BitsMut};
let mut vec: Vec<u32> = vec![0u32; 4];
vec.set_bit(32);
vec.set_bit(65);
vec.set_bit(96);
vec.set_bit(97);
assert!(vec.iter_ones().eq([32, 65, 96, 97]));
assert_eq!(vec, [0, 1, 2, 3]);
Due to how broadly these traits are implemented, we also try to avoid using names which are commonly used in other APIs, instead opt for bit-specific terminology such as:
- Something like
is_empty
becomesall_zeros
- since with bits you're thinking about "ones and zeros". - Testing if a bit is set is
test_bit
, or in general adding the*_bit
suffix to operations over individual bits. - Clearing all bits becomes
clear_bits
, or in general adding the*_bits
suffix when operating over all bits.
use bittle::{Bits, BitsMut};
let mut set = [0u16; 2];
set.set_bit(15);
assert!(set.test_bit(15));
set.union_assign(&bittle::set![31, 7]);
assert!(set.test_bit(31) && set.test_bit(7));
set.clear_bit(31);
assert!(!set.test_bit(31));
set.clear_bits();
assert!(set.all_zeros());
Some other interesting operations, such as Bits::join_ones
are available,
allowing bitsets to act like masks over other iterators:
use bittle::{Bits, BitsMut};
let elements = vec![10, 48, 101];
let mut m = 0u128;
m.set_bit(0);
assert!(m.join_ones(&elements).eq([&10]));
m.set_bit(2);
assert!(m.join_ones(&elements).eq([&10, &101]));