Skip to main content
Log in

Mojo struct

BitSet

struct BitSet[size: Int]

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, and toggle operations (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 (Int): The maximum number of bits the bitset can store.

Implemented traits

AnyType, Boolable, Copyable, ExplicitlyCopyable, Movable, Sized, Stringable, UnknownDestructibility, Writable

Methods

__init__

__init__(out self)

Initializes an empty BitSet with zero capacity and size.

__init__(out self, 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 from self.

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 the Writer trait.

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.