BitVec

Mojo struct 🡭

`BitVec`

@memory_only
struct BitVec

A growable bitfield.

This uses one bit per bool for storage.

The bits are stored in Self.WORD_DTYPE words. This is optimized for compactness and speed.

Aliases

WORD_DTYPE = DType.uint64 if not is_gpu().__bool__() else DType.uint32
WORD_BYTEWIDTH = (bit_width_of[DType.uint64 if (xor is_gpu(), True) else DType.uint32]() // Int(8))
WORD = Scalar[BitVec.WORD_DTYPE]
WORD_PTR = Pointer[Scalar[BitVec.WORD_DTYPE], MutUntrackedOrigin]

Fields

data (BitVec.WORD_PTR): The data storage.

Implemented traits

AnyType, Boolable, Copyable, Deinitable, Movable, Sized, Writable

Methods

➕ ➖

`init`

def __init__(out self)

Details

Args:

self (Self)

Returns:

Self

def __init__(out self, *, capacity: UInt)

Capacity measured in bits.

Args:

capacity (UInt)
self (Self)

Returns:

Self

def __init__(out self, *, length: UInt, fill: Bool = False)

Create a new bitvec with a known length and fill.

Args:

length (UInt): Known length in bits.
fill (Bool): The value to fill the bitvec with.
self (Self)

Returns:

Self

def __init__(out self, var *values: Bool, *, __list_literal__: NoneType)

Constructs a BitVec from the given values.

Args:

*values (Bool): The values to populate the BitVec with.
list_literal (NoneType): Tell Mojo to use this method for list literals.
self (Self)

Returns:

Self

def __init__(out self, *, var elements: VariadicList[Bool])

Constructs a BitVec from the given values.

Args:

elements (VariadicList[Bool]): The values to populate the list with.
self (Self)

Returns:

Self

def __init__(out self, *, deinit move: Self)

Details

Args:

move (Self)
self (Self)

Returns:

Self

`deinit`

def __deinit__(deinit self)

Details

Args:

self (Self)

`bool`

def __bool__(self) -> Bool

Checks if the BitVec is non-empty (contains at least one value).

Equivalent to len(self) != 0 or not self.is_empty().

Args:

self (Self)

Returns:

Bool: True if at least one value is in BitVec., False otherwise.

`getitem`

def __getitem__(self, idx: UInt) -> Bool

Get the bit at the given index.

Args:

self (Self)
idx (UInt): The index of the bit.

Returns:

Bool

`setitem`

def __setitem__(mut self, idx: UInt, value: Bool)

Set the bit at the given index.

Args:

self (Self)
idx (UInt): The index of the bit to set.
value (Bool): The value to set the bit to.

`eq`

def __eq__(self, other: Self) -> Bool

Check the equality of self and other.

Args:

self (Self)
other (Self): The BitVec to compare against.

Returns:

Bool: True if equal, False otherwise.

`ne`

def __ne__(self, other: Self) -> Bool

Check the equality of self and other.

Args:

self (Self)
other (Self): The BitVec to compare against.

Returns:

Bool: True if not equal, False otherwise.

`sub`

def __sub__(self, other: Self) -> Self

Returns a new BitVec that is the difference of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-: 0 0 0 1 1 1 1 0

Args:

self (Self)
other (Self): The BitVec to subtract from self.

Returns:

Self: A new BitVec containing elements from self that are not in other.

`and`

def __and__(self, other: Self) -> Self

Returns a new BitVec that is the intersection of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&: 0 0 1 0 0 0 0 0

Args:

self (Self)
other (Self): The BitVec to intersect with.

Returns:

Self: A new BitVec containing only the elements present in both sets.

`or`

def __or__(self, other: Self) -> Self

Returns a new BitVec that is the union of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|: 1 1 1 1 1 1 1 0

Args:

self (Self)
other (Self): The BitVec to union with.

Returns:

Self: A new BitVec containing all elements from both sets.

`isub`

def __isub__(mut self, other: Self)

Modifies self to be the difference of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-= 0 0 0 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

self (Self)
other (Self): The BitVec to subtract from self.

`iand`

def __iand__(mut self, other: Self)

Modifies self to be the intersection of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&= 0 0 1 0 0 0 0 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

self (Self)
other (Self): The BitVec to intersect with.

`ior`

def __ior__(mut self, other: Self)

Modifies self to be the union of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|= 1 1 1 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s

Notes: This retains selfs length.

Args:

self (Self)
other (Self): The BitVec to union with.

`copy`

def copy(self) -> Self

Details

Args:

self (Self)

Returns:

Self

`len`

def __len__(self) -> Int

The number of bits in the bitvec.

Args:

self (Self)

Returns:

Int

`capacity`

def capacity(self) -> UInt

Returns the capacity in bits.

Args:

self (Self)

Returns:

UInt

`word_len`

def word_len(self) -> UInt

Get the number of words that have been set.

Args:

self (Self)

Returns:

UInt

`is_empty`

def is_empty(self) -> Bool

Checks if the BitVec has any values stored in it.

Equivalent to len(self) == 0. Note that this checks the logical size, not the allocated capacity.

Args:

self (Self)

Returns:

Bool: True if no values are stored in the BitVec.

`resize`

def resize(mut self, new_size: UInt, fill: Bool)

Resize the bitvec, filling any new size with fill.

Args:

self (Self)
new_size (UInt): The new size in bits.
fill (Bool): The value to use to populate new elements.

`shrink`

def shrink(mut self, new_size: UInt)

Resizes to the given new size (in bits) which must be <= the current size.

Notes: With no new value provided, the new size must be smaller than or equal to the current one. Elements at the end are discarded.

Args:

self (Self)
new_size (UInt): The new size in bits.

`reserve`

def reserve(mut self, new_capacity: UInt)

Reserves the requested capacity (in bits).

Notes: If the current capacity is greater or equal, this is a no-op. Otherwise, the storage is reallocated and the data is moved.

Args:

self (Self)
new_capacity (UInt): The new capacity, in bits.

`test`

def 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:

self (Self)
idx (UInt): The non-negative index of the bit to test (must be < size).

Returns:

Bool: True if the bit at idx is set, False otherwise.

`clear`

def clear(mut self)

Clear the BitVec.

This sets the length to 0.

Args:

self (Self)

def clear(mut self, idx: UInt)

Clear the bit at the given index (set to 0).

Args:

self (Self)
idx (UInt): The index of the bit to clear.

`zero_all`

def zero_all(mut self)

Set all bits to zero.

Args:

self (Self)

`set_and_check`

def set_and_check(mut self, idx: UInt) -> Bool

Set the bit at the given index. If the value was already set, return False, otherwise True.

Args:

self (Self)
idx (UInt): The index of the bit to set.

Returns:

Bool: False if the bit was already set, True if it was not.

`set`

def set(mut self, idx: UInt)

Set the bit at the given index to 1.

Args:

self (Self)
idx (UInt): The index of the bit to set.

`clear_and_check`

def clear_and_check(mut self, idx: UInt) -> Bool

Clear the bit at the given index. If the value was already clear (0, False), return False, otherwise True.

Args:

self (Self)
idx (UInt): The index of the bit to clear.

Returns:

Bool: False if the bit was already clear, True if it was not.

`toggle`

def toggle(mut self, idx: UInt)

Toggles (inverts) the bit at the specified index idx.

Args:

self (Self)
idx (UInt): The non-negative index of the bit to toggle (must be < len(BitVec)).

`append`

def append(mut self, value: Bool)

Append an item to the end of the BitVec.

Notes: If there is no capacity left, resizes to twice the current capacity. Except for 0 capacity where it sets to 1.

Args:

self (Self)
value (Bool): The value to append.

`append_true`

def append_true(mut self)

Append a set bit to the end of the BitVec.

Notes: If there is no capacity left, resizes to twice the current capacity. Except for 0 capacity where it sets to 1.

Args:

self (Self)

`append_false`

def append_false(mut self)

Append a cleared bit to the end of the BitVec.

Notes: If there is no capacity left, resizes to twice the current capacity. Except for 0 capacity where it sets to 1.

Args:

self (Self)

`pop_back`

def pop_back(mut self) -> Bool

Remove and return the last item in the BitVec.

Args:

self (Self)

Returns:

Bool

`count_set_bits`

def count_set_bits(self) -> UInt

Count the total number of set bits.

Args:

self (Self)

Returns:

UInt

`rank`

def rank(self, bit_idx: UInt) -> UInt

Count the total number of set bits up to (but not including) bit_idx.

TODO: implement another struct that builds a rank/select index.

References:

https://rob-p.github.io/CMSC858D/static_files/presentations/CMSC858D-Lec08.pdf

Args:

self (Self)
bit_idx (UInt): Index to get the rank for.

Returns:

UInt

`count_clear_bits`

def count_clear_bits(self) -> UInt

Count the total number of clear bits.

Args:

self (Self)

Returns:

UInt

`union`

def union(self, other: Self) -> Self

Returns a new BitVec that is the union of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|: 1 1 1 1 1 1 1 0

Args:

self (Self)
other (Self): The BitVec to union with.

Returns:

Self: A new BitVec containing all elements from both sets.

`intersection`

def intersection(self, other: Self) -> Self

Returns a new BitVec that is the intersection of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&: 0 0 1 0 0 0 0 0

Args:

self (Self)
other (Self): The BitVec to intersect with.

Returns:

Self: A new BitVec containing only the elements present in both sets.

`difference`

def difference(self, other: Self) -> Self

Returns a new BitVec that is the difference of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-: 0 0 0 1 1 1 1 0

Args:

self (Self)
other (Self): The BitVec to subtract from self.

Returns:

Self: A new BitVec containing elements from self that are not in other.

`union_update`

def union_update(mut self, other: Self)

Modifies self to be the union of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
|= 1 1 1 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s

Notes: This retains selfs length.

Args:

self (Self)
other (Self): The BitVec to union with.

`intersection_update`

def intersection_update(mut self, other: Self)

Modifies self to be the intersection of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
&= 0 0 1 0 0 0 0 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

self (Self)
other (Self): The BitVec to intersect with.

`difference_update`

def difference_update(mut self, other: Self)

Modifies self to be the difference of self and other.

A: 0 0 1 1 1 1 1 0
B: 1 1 1 0 0
-= 0 0 0 1 1 1 1 0

If len(self) < len(other), self will be resized to match the size of other by filling with 0s.

Notes: This retains selfs length.

Args:

self (Self)
other (Self): The BitVec to subtract from self.

`write_to`

def write_to[W: Writer](self, mut writer: W)

Write the bitvec in a nice format.

Parameters:

W (Writer)

Args:

self (Self)
writer (W)