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
| Syntax | Description |
|---|---|
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
| Method | Signature | Returns | Description |
|---|---|---|---|
set | (index: usize, value?: boolean) => void | void | Set, clear, or conditionally set the bit at index (default: true) |
flip | (index: usize) => void | void | Toggle the bit at index |
get | (index: usize) => boolean | boolean | Whether the bit at index is set |
count | () => usize | usize | Number of set bits |
isEmpty | () => boolean | boolean | Whether no bits are set |
isSubset | (other: BitSet) => boolean | boolean | Whether every set bit is also set in other |
isSuperset | (other: BitSet) => boolean | boolean | Whether every set bit in other is also set |
union | (other: BitSet) => BitSet | BitSet | Bit set with all bits from both sets |
intersection | (other: BitSet) => BitSet | BitSet | Bit set with bits set in both sets |
difference | (other: BitSet) => BitSet | BitSet | Bit set with bits set here but not in other |
complement | () => BitSet | BitSet | Bit set with every bit flipped over the capacity |
clear | () => void | void | Clear 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
| Operation | Time Complexity |
|---|---|
set | O(1) |
flip | O(1) |
get | O(1) |
count | O(n), number of machine words |
isEmpty | O(n), number of machine words |
isSubset | O(n), number of machine words |
isSuperset | O(n), number of machine words |
union | O(n), number of machine words |
intersection | O(n), number of machine words |
difference | O(n), number of machine words |
complement | O(n), number of machine words |
clear | O(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)); // trueflip
tyrus
const bs = BitSet(100);
bs.set(3);
print(bs.get(3)); // true
bs.flip(3);
print(bs.get(3)); // falsecount 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()); // falseisSubset 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)); // falseunion, 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()); // 1complement
tyrus
const bs = BitSet(100);
bs.set(3);
bs.set(5);
bs.set(7);
print(bs.complement().count()); // 97
print(bs.complement().get(1)); // truefromArray
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)); // falseclear
tyrus
const bs = BitSet(100);
bs.set(1);
bs.set(2);
print(bs.isEmpty()); // false
bs.clear();
print(bs.isEmpty()); // true