Crate bit_vec

Description

Dynamic collections implemented with compact bit vectors.

Examples

This is a simple example of the Sieve of Eratosthenes which calculates prime numbers up to a given limit.

use bit_vec::BitVec;

let max_prime = 10000;

// Store the primes as a BitVec
let primes = {
    // Assume all numbers are prime to begin, and then we
    // cross off non-primes progressively
    let mut bv = BitVec::from_elem(max_prime, true);

    // Neither 0 nor 1 are prime
    bv.set(0, false);
    bv.set(1, false);

    for i in 2.. 1 + (max_prime as f64).sqrt() as usize {
        // if i is a prime
        if bv[i] {
            // Mark all multiples of i as non-prime (any multiples below i * i
            // will have been marked as non-prime previously)
            for j in i.. {
                if i * j >= max_prime {
                    break;
                }
                bv.set(i * j, false)
            }
        }
    }
    bv
};

// Simple primality tests below our max bound
let print_primes = 20;
print!("The primes below {} are: ", print_primes);
for x in 0..print_primes {
    if primes.get(x).unwrap_or(false) {
        print!("{} ", x);
    }
}
println!();

let num_primes = primes.iter().filter(|x| *x).count();
println!("There are {} primes below {}", num_primes, max_prime);
assert_eq!(num_primes, 1_229);

Macros

• bit_block_impl 🔒

Structs

• BitVec
  The bitvector type.
• Blocks
  An iterator over the blocks of a BitVec.
• IntoIter
• Iter
  An iterator for BitVec.
• IterMut
  An iterator for mutable references to the bits in a BitVec.
• MutBorrowedBit

Statics

• FALSE 🔒
• TRUE 🔒

Traits

• BitBlock
  Abstracts over a pile of bits (basically unsigned primitives)

Functions

• blocks_for_bits 🔒
  Computes how many blocks are needed to store that many bits
• mask_for_bits 🔒
  Computes the bitmask for the final word of the vector
• reverse_bits 🔒

Type Aliases

• B 🔒
• MutBlocks 🔒