Mojo struct
BitSet
struct BitSet[size: UInt]
A grow-only set storing non-negative integers efficiently using bits.
Each integer element is represented by a single bit within an array
of 64-bit words (UInt64). This structure is optimized for:
- Compactness: Uses 64 times less memory than
List[Bool]. - Speed: Offers O(1) time complexity for
set,clear,test, andtoggleoperations (single word load/store).
Ideal for applications like data-flow analysis, graph algorithms, or any task requiring dense sets of small integers where memory and lookup speed are critical.
Parameters
- size (
UInt): The maximum number of bits the bitset can store.
Implemented traits
AnyType,
Boolable,
Copyable,
Movable,
Sized,
Stringable,
UnknownDestructibility,
Writable
Methods
__init__
__init__(out self)
Initializes an empty BitSet with zero capacity and size.
__init__(out self: BitSet[UInt(size)], init: SIMD[bool, size])
Initializes a BitSet with the given SIMD vector of booleans.
Args:
- init (
SIMD[bool, size]): A SIMD vector of booleans to initialize the bitset with.
__bool__
__bool__(self) -> Bool
Checks if the bitset is non-empty (contains at least one set bit).
Equivalent to len(self) != 0 or not self.is_empty().
Returns:
True if at least one bit is set, False otherwise.
__len__
__len__(self) -> Int
Counts the total number of bits that are set to 1 in the bitset.
Uses the efficient pop_count intrinsic for each underlying word.
The complexity is proportional to the number of words used by the
bitset's capacity (_words_size), not the logical size (len).
Returns:
The total count of set bits (population count).
is_empty
is_empty(self) -> Bool
Checks if the bitset contains any set bits.
Equivalent to len(self) == 0. Note that this checks the logical
size, not the allocated capacity.
Returns:
True if no bits are set (logical size is 0), False otherwise.
set
set(mut self, idx: UInt)
Sets the bit at the specified index idx to 1.
If idx is greater than or equal to the current logical size,
the logical size is updated. Aborts if idx is negative or
greater than or equal to the compile-time size.
Args:
- idx (
UInt): The non-negative index of the bit to set (must be <size).
clear
clear(mut self, idx: UInt)
Clears the bit at the specified index idx (sets it to 0).
Aborts if idx is negative or greater than or equal to the
compile-time size. Does not change the logical size.
Args:
- idx (
UInt): The non-negative index of the bit to clear (must be <size).
toggle
toggle(mut self, idx: UInt)
Toggles (inverts) the bit at the specified index idx.
If the bit becomes 1 and idx is greater than or equal to the
current logical size, the logical size is updated. Aborts if idx
is negative or greater than or equal to the compile-time size.
Args:
- idx (
UInt): The non-negative index of the bit to toggle (must be <size).
test
test(self, idx: UInt) -> Bool
Tests if the bit at the specified index idx is set (is 1).
Aborts if idx is negative or greater than or equal to the
compile-time size.
Args:
- idx (
UInt): The non-negative index of the bit to test (must be <size).
Returns:
True if the bit at idx is set, False otherwise.
clear_all
clear_all(mut self)
Clears all bits in the set, resetting the logical size to 0.
The allocated storage capacity remains unchanged. Equivalent to
re-initializing the set with Self().
union
union(self, other: Self) -> Self
Returns a new bitset that is the union of self and other.
Args:
- other (
Self): The bitset to union with.
Returns:
A new bitset containing all elements from both sets.
intersection
intersection(self, other: Self) -> Self
Returns a new bitset that is the intersection of self and other.
Args:
- other (
Self): The bitset to intersect with.
Returns:
A new bitset containing only the elements present in both sets.
difference
difference(self, other: Self) -> Self
Returns a new bitset that is the difference of self and other.
Args:
- other (
Self): The bitset to subtract fromself.
Returns:
A new bitset containing elements from self that are not in other.
write_to
write_to[W: Writer, //](self, mut writer: W)
Writes a string representation of the set bits to the given writer. Outputs the indices of the set bits in ascending order, enclosed in curly braces and separated by commas (e.g., "{1, 5, 42}"). Uses efficient bitwise operations to find set bits without iterating through every possible bit.
Parameters:
- W (
Writer): The type of the writer, conforming to theWritertrait.
Args:
- writer (
W): The writer instance to output the representation to.
__repr__
__repr__(self) -> String
Returns a developer-friendly string representation of the bitset.
Currently equivalent to __str__.
Returns:
A string showing the set bits (e.g., "{1, 5, 42}").
__str__
__str__(self) -> String
Returns a user-friendly string representation of the bitset.
Formats the set bits as a comma-separated list within curly braces,
like "{1, 5, 42}". Uses the write_to method internally.
Returns:
A string showing the set bits.
Was this page helpful?
Thank you! We'll create more content like this.
Thank you for helping us improve!