Skip to content

BitSet ​

BitSet implements a compact set of bits over a fixed capacity, backed by an array of 64-bit words, with set-theoretic operations.

Construction ​

SyntaxDescription
BitSet(n)Create a bit set with capacity for n bits, all initially cleared
BitSet.fromArray(arr)Create a bit set with the bits at the positions in arr set

fromArray requires a usize[] argument. Bit positions are zero-indexed from 0 to n - 1.

Methods ​

MethodSignatureReturnsDescription
set(index: usize, value?: boolean) => voidvoidSet, clear, or conditionally set the bit at index (default: true)
flip(index: usize) => voidvoidToggle the bit at index
get(index: usize) => booleanbooleanWhether the bit at index is set
count() => usizeusizeNumber of set bits
isEmpty() => booleanbooleanWhether no bits are set
isSubset(other: BitSet) => booleanbooleanWhether every set bit is also set in other
isSuperset(other: BitSet) => booleanbooleanWhether every set bit in other is also set
union(other: BitSet) => BitSetBitSetBit set with all bits from both sets
intersection(other: BitSet) => BitSetBitSetBit set with bits set in both sets
difference(other: BitSet) => BitSetBitSetBit set with bits set here but not in other
complement() => BitSetBitSetBit set with every bit flipped over the capacity
clear() => voidvoidClear all bits

union, intersection, difference, and complement return a fresh BitSet owned by the caller; it is released automatically when its binding goes out of scope.

Complexity ​

OperationTime Complexity
setO(1)
flipO(1)
getO(1)
countO(n), number of machine words
isEmptyO(n), number of machine words
isSubsetO(n), number of machine words
isSupersetO(n), number of machine words
unionO(n), number of machine words
intersectionO(n), number of machine words
differenceO(n), number of machine words
complementO(n), number of machine words
clearO(n), number of machine words

Examples ​

Construction ​

tyrus
import { BitSet } from "tyrus:algorithm";

const bs = BitSet(100);

set and get ​

tyrus
const bs = BitSet(100);

bs.set(5);
bs.set(10, true);
bs.set(3, false);

print(bs.get(5));   // true
print(bs.get(3));   // false
print(bs.get(10));  // true

flip ​

tyrus
const bs = BitSet(100);

bs.set(3);

print(bs.get(3));  // true

bs.flip(3);

print(bs.get(3));  // false

count and isEmpty ​

tyrus
const bs = BitSet(100);

print(bs.count());     // 0
print(bs.isEmpty());   // true

bs.set(1);
bs.set(2);

print(bs.count());    // 2
print(bs.isEmpty());  // false

isSubset and isSuperset ​

tyrus
const a = BitSet(100);
a.set(1);
a.set(3);

const b = BitSet(100);
b.set(1);
b.set(3);
b.set(5);

print(a.isSubset(b));    // true
print(b.isSuperset(a));  // true
print(b.isSubset(a));    // false

union, intersection, and difference ​

tyrus
const a = BitSet(100);
a.set(1);
a.set(3);
a.set(5);

const b = BitSet(100);
b.set(3);
b.set(5);
b.set(7);

print(a.union(b).count());        // 4
print(a.intersection(b).count()); // 2
print(a.difference(b).count());   // 1

complement ​

tyrus
const bs = BitSet(100);
bs.set(3);
bs.set(5);
bs.set(7);

print(bs.complement().count());  // 97
print(bs.complement().get(1));   // true

fromArray ​

tyrus
const indexes: usize[] = [3, 5, 10];
const bs = BitSet.fromArray(indexes);

print(bs.count());  // 3
print(bs.get(10));  // true
print(bs.get(4));   // false

clear ​

tyrus
const bs = BitSet(100);
bs.set(1);
bs.set(2);

print(bs.isEmpty());  // false

bs.clear();

print(bs.isEmpty());  // true