bitset
The bitset module is a set of small non-negative ints, one bit each: a sieve, a visited set, a set of flags. Setting a bit past the end grows the set.
import bitset
fn main():
seen = bitset.new(100)
for x in [3, 64, 7, 3, 99]:
seen.set(x)
print(seen.count(), seen.has(7), seen.has(8), seen.ones())
seen.unset(64)
other = bitset.new(10)
other.set(3)
other.set(4)
both = seen
both.intersect_with(other)
print(seen.ones(), both.ones())Output
4 true false [3, 7, 64, 99]
[3, 7, 99] [3]Functions
fn new(n: int) Bitset room for bits 0..n-1 (it grows past that)
fn set(b: mut Bitset, i: int) fn unset(b: mut Bitset, i: int)
fn toggle(b: mut Bitset, i: int) fn has(b: Bitset, i: int) bool (false outside it)
fn count(b: Bitset) int how many bits are set (the CPU's popcount)
fn ones(b: Bitset) [int] the set bits, ascending
fn size(b: Bitset) int how many bits it has room for (a multiple of 64)
fn union_with(b: mut Bitset, o: Bitset) fn intersect_with(b: mut Bitset, o: Bitset)
fn subtract(b: mut Bitset, o: Bitset) each changes bSpeed
bench/std sieves the primes up to 100 million and sums them: Tern 366 ms, Rust's fixedbitset 366 ms, Go's bits-and-blooms/bitset 445 ms.