Table of Contents

BitSet Class

Definition

Namespace
Bodu.Collections.Specialized
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
BitSet.Enumerator.cs

Represents a growable set of non-negative integers stored as a packed bit array, following the semantics of the Java BitSet class: writes beyond the current capacity grow the storage automatically, and reads beyond the current capacity report the bit as clear rather than throwing.

public sealed class BitSet : IEnumerable<int>, IEnumerable, IEquatable<BitSet>
Inheritance
BitSet
Implements
Inherited Members
Extension Methods

Examples

var primes = new BitSet();
primes.Set(2);
primes.Set(3);
primes.Set(5);
primes.Set(100);          // grows automatically

Console.WriteLine(primes.Cardinality);    // 4
Console.WriteLine(primes.Length);         // 101 - highest set bit + 1
Console.WriteLine(primes.Get(1_000_000)); // False - beyond capacity, no throw

foreach (int index in primes)
    Console.WriteLine(index);             // 2, 3, 5, 100 - ascending

Remarks

A BitSet is backed by a ulong array packing 64 bits per word. Single-bit Get(int), Set(int), Clear(int), and Flip(int) operations are O(1) (amortized when growth occurs); range operations and the word-wise logical operators (And(BitSet), Or(BitSet), Xor(BitSet), AndNot(BitSet)) process 64 bits per step.

The type distinguishes the logical length from the allocated capacity: Length is one greater than the index of the highest set bit (the Java length() contract), while Capacity is the number of bits the current backing storage can address without reallocating. Reading a bit at or beyond Capacity returns false; clearing such a bit is a no-op; setting or flipping it grows the storage.

The addressable universe is bounded: bit indices range from 0 to MaxBitCount − 1, which keeps Capacity and Length representable as int values. Get(int) and Clear(int) accept any non-negative index (indices beyond the universe are trivially clear), whereas Set(int) and Flip(int) reject indices outside the universe.

Enumerating a BitSet yields the indices of the set bits in ascending order through a non-boxing BitSet.Enumerator struct. Any mutation invalidates active enumerators.

Equality is a value comparison over the logical content: two instances are equal when they have the same set bits, regardless of allocated capacity. Because the content is mutable, the hash code changes as bits change - do not use a BitSet as a dictionary key while it is being mutated.

Unlike BitArray - which has a fixed, explicit length, no set-bit query surface, and a boxing enumerator over bool values - BitSet grows on demand, exposes NextSetBit(int) / NextClearBit(int) / Cardinality, and enumerates set-bit indices without boxing.

BitSet is not thread-safe. Concurrent reads and writes require external synchronization.

Constructors

BitSet()

Initializes a new instance of the BitSet class with all bits clear and a small default capacity.

public BitSet()

BitSet(BitSet)

Initializes a new instance of the BitSet class containing the same set bits as the specified source set.

public BitSet(BitSet source)

Parameters

source BitSet

The set whose bits are copied. Must not be null.

Remarks

The copy shares no storage with source - subsequent mutations of either instance do not affect the other. The copy's Capacity matches the source's capacity at the time of the copy.

Exceptions

ArgumentNullException

source is null.

BitSet(int)

Initializes a new instance of the BitSet class with all bits clear and storage pre-allocated for at least the specified number of bits.

public BitSet(int initialCapacityBits)

Parameters

initialCapacityBits int

The number of bits the set can address before its first growth. A value of 0 allocates no storage.

Remarks

The requested capacity is rounded up to a whole number of 64-bit words, so Capacity may exceed initialCapacityBits. The capacity is a pre-allocation hint only - the set still grows automatically when a bit beyond it is set or flipped.

Exceptions

ArgumentOutOfRangeException

initialCapacityBits < 0, or initialCapacityBits > MaxBitCount.

Fields

MaxBitCount

The number of addressable bits in the largest supported BitSet. Bit indices range from 0 to MaxBitCount − 1.

public const int MaxBitCount = 2147483584

Field Value

int

Remarks

The bound (MaxValue − 63) is the largest whole-word bit count whose capacity and logical length remain representable as int values.

Properties

Capacity

Gets the number of bits the current backing storage can address without reallocating.

public int Capacity { get; }

Property Value

int

The allocated size in bits - always a multiple of 64.

Remarks

Capacity is an allocation detail, distinct from the logical Length: reading a bit at or beyond the capacity returns false, clearing it is a no-op, and setting or flipping it grows the storage (increasing the capacity). The capacity never shrinks.

Cardinality

Gets the number of set bits in the set.

public int Cardinality { get; }

Property Value

int

The population count - the total number of bits whose value is true.

IsEmpty

Gets a value indicating whether the set contains no set bits.

public bool IsEmpty { get; }

Property Value

bool

true if no bit is set; otherwise, false.

this[int]

Gets or sets the value of the bit at the specified index.

public bool this[int index] { get; set; }

Parameters

index int

The zero-based bit index.

Property Value

bool

true if the bit at index is set; otherwise, false.

Remarks

The getter follows the Get(int) contract (indices beyond Capacity read as false); the setter follows the Set(int, bool) contract (auto-growing when a bit beyond the capacity is set to true).

Exceptions

ArgumentOutOfRangeException

index < 0, or - for the setter only - index ≥ MaxBitCount.

Length

Gets the logical length of the set - one greater than the index of the highest set bit.

public int Length { get; }

Property Value

int

The highest set-bit index plus one, or 0 when the set is empty.

Remarks

Length is the Java BitSet.length() contract and reflects only the logical content - it is unrelated to the allocated Capacity. Clearing the highest set bit reduces the length; clearing every bit reduces it to 0 regardless of how much storage remains allocated.

Methods

And(BitSet)

Performs an in-place logical AND with the specified set: a bit remains set only when it is set in both operands.

public void And(BitSet other)

Parameters

other BitSet

The set to intersect with. Must not be null.

Remarks

The result can never contain bits beyond either operand's content, so this operation never grows the storage. Bits of this set beyond other's capacity are cleared (they are ANDed with conceptually clear bits). Passing this instance as other is a no-op.

Exceptions

ArgumentNullException

other is null.

AndNot(BitSet)

Performs an in-place logical AND NOT (set difference) with the specified set: every bit that is set in other is cleared in this set.

public void AndNot(BitSet other)

Parameters

other BitSet

The set whose bits are removed from this set. Must not be null.

Remarks

The result is a subset of this set's content, so this operation never grows the storage. Passing this instance as other clears every bit.

Exceptions

ArgumentNullException

other is null.

Clear()

Clears every bit in the set.

public void Clear()

Remarks

The allocated Capacity is retained; only the logical content is reset. After this call IsEmpty is true and Length is 0.

Clear(int)

Clears the bit at the specified index.

public void Clear(int index)

Parameters

index int

The zero-based index of the bit to clear.

Remarks

An index at or beyond Capacity is already conceptually clear, so the call is a no-op - it never grows the storage and never throws for large indices (Java BitSet.clear semantics). Such a no-op call does not invalidate in-flight enumerators.

Exceptions

ArgumentOutOfRangeException

index < 0.

Clear(int, int)

Clears every bit in the half-open range [fromInclusive, toExclusive).

public void Clear(int fromInclusive, int toExclusive)

Parameters

fromInclusive int

The first bit index of the range.

toExclusive int

The exclusive upper bound of the range.

Remarks

An empty range (fromInclusive equal to toExclusive) is a no-op that does not invalidate in-flight enumerators. The portion of the range at or beyond Capacity is already conceptually clear, so the operation never grows the storage; a range entirely beyond Capacity is likewise an enumerator-preserving no-op.

Exceptions

ArgumentOutOfRangeException

fromInclusive < 0, or toExclusive < 0.

ArgumentException

fromInclusive > toExclusive.

Equals(BitSet?)

Determines whether the specified BitSet contains the same set bits as this instance.

public bool Equals(BitSet? other)

Parameters

other BitSet

The set to compare, or null.

Returns

bool

true if other has the same set bits; otherwise, false.

Remarks

Equality is a value comparison over the logical content only: allocated capacity and trailing zero words are ignored, so a set that grew and was subsequently cleared equals a freshly constructed empty set.

Equals(object?)

Determines whether the specified object is a BitSet containing the same set bits as this instance.

public override bool Equals(object? obj)

Parameters

obj object

The object to compare, or null.

Returns

bool

true if obj is a BitSet with the same set bits; otherwise, false.

Flip(int)

Toggles the bit at the specified index - a set bit becomes clear and a clear bit becomes set.

public void Flip(int index)

Parameters

index int

The zero-based index of the bit to toggle.

Remarks

Flipping a bit at or beyond Capacity sets it (the bit was conceptually clear), growing the storage as required.

Exceptions

ArgumentOutOfRangeException

index < 0, or index ≥ MaxBitCount.

Flip(int, int)

Toggles every bit in the half-open range [fromInclusive, toExclusive).

public void Flip(int fromInclusive, int toExclusive)

Parameters

fromInclusive int

The first bit index of the range.

toExclusive int

The exclusive upper bound of the range.

Remarks

An empty range (fromInclusive equal to toExclusive) is a no-op that does not invalidate in-flight enumerators. The storage grows as required so that clear bits beyond the current Capacity become set.

Exceptions

ArgumentOutOfRangeException

fromInclusive < 0, toExclusive < 0, or toExclusive > MaxBitCount.

ArgumentException

fromInclusive > toExclusive.

Get(int)

Returns the value of the bit at the specified index.

public bool Get(int index)

Parameters

index int

The zero-based bit index.

Returns

bool

true if the bit at index is set; otherwise, false.

Remarks

An index at or beyond Capacity returns false rather than throwing - every bit outside the allocated storage is conceptually clear (Java BitSet.get semantics). Any non-negative index, including MaxValue, is accepted.

Exceptions

ArgumentOutOfRangeException

index < 0.

GetEnumerator()

Returns a non-boxing enumerator that yields the indices of the set bits in ascending order.

public BitSet.Enumerator GetEnumerator()

Returns

BitSet.Enumerator

An BitSet.Enumerator positioned before the first set bit.

GetHashCode()

Returns a hash code derived from the logical content of the set.

public override int GetHashCode()

Returns

int

An int hash code consistent with Equals(BitSet?).

Remarks

The hash covers only the words up to the highest set bit, so trailing zero words (excess capacity) do not affect it. Because the content is mutable, the hash code changes as bits change.

Intersects(BitSet)

Determines whether this set and the specified set have at least one set bit in common.

public bool Intersects(BitSet other)

Parameters

other BitSet

The set to test against. Must not be null.

Returns

bool

true if any bit is set in both this set and other; otherwise, false.

Remarks

Neither operand is modified. Passing this instance as other returns true exactly when the set is non-empty.

Exceptions

ArgumentNullException

other is null.

NextClearBit(int)

Returns the index of the first clear bit at or after the specified index.

public int NextClearBit(int fromIndex)

Parameters

fromIndex int

The index at which the search starts.

Returns

int

The index of the first clear bit ≥ fromIndex.

Remarks

A clear bit conceptually always exists - every bit at or beyond Capacity is clear - so this method never returns −1. The result may therefore be ≥ Length (and ≥ Capacity when every allocated bit from fromIndex onward is set).

Exceptions

ArgumentOutOfRangeException

fromIndex < 0.

NextSetBit(int)

Returns the index of the first set bit at or after the specified index, or −1 when no further bit is set.

public int NextSetBit(int fromIndex)

Parameters

fromIndex int

The index at which the search starts.

Returns

int

The index of the first set bit ≥ fromIndex, or −1 if none exists.

Remarks

The canonical iteration idiom is for (int i = bits.NextSetBit(0); i >= 0; i = bits.NextSetBit(i + 1)); the struct BitSet.Enumerator obtained from GetEnumerator() provides the same walk as a foreach loop.

Exceptions

ArgumentOutOfRangeException

fromIndex < 0.

Or(BitSet)

Performs an in-place logical OR with the specified set: a bit becomes set when it is set in either operand.

public void Or(BitSet other)

Parameters

other BitSet

The set to union with. Must not be null.

Remarks

The storage grows as required to accommodate other's logical Length, so bits set beyond this set's current capacity are preserved in the result. Passing this instance as other is a no-op.

Exceptions

ArgumentNullException

other is null.

Set(int)

Sets the bit at the specified index to true, growing the storage as required.

public void Set(int index)

Parameters

index int

The zero-based index of the bit to set.

Exceptions

ArgumentOutOfRangeException

index < 0, or index ≥ MaxBitCount.

Set(int, bool)

Sets the bit at the specified index to the specified value, growing the storage as required.

public void Set(int index, bool value)

Parameters

index int

The zero-based index of the bit to write.

value bool

true to set the bit; false to clear it.

Remarks

Storage grows only when a bit beyond the current Capacity is set to true; writing false to such a bit is a no-op (it is already conceptually clear) that does not invalidate in-flight enumerators.

Exceptions

ArgumentOutOfRangeException

index < 0, or index ≥ MaxBitCount.

Set(int, int)

Sets every bit in the half-open range [fromInclusive, toExclusive) to true, growing the storage as required.

public void Set(int fromInclusive, int toExclusive)

Parameters

fromInclusive int

The first bit index of the range.

toExclusive int

The exclusive upper bound of the range.

Remarks

An empty range (fromInclusive equal to toExclusive) is a no-op that does not invalidate in-flight enumerators.

Exceptions

ArgumentOutOfRangeException

fromInclusive < 0, toExclusive < 0, or toExclusive > MaxBitCount.

ArgumentException

fromInclusive > toExclusive.

ToString()

Returns a summary string describing the logical content of the set.

public override string ToString()

Returns

string

A string of the form BitSet(Cardinality = 5, Length = 65) reporting Cardinality and Length.

Remarks

The summary form is deliberate - a set-builder listing could be arbitrarily large. Enumerate the instance to obtain the individual set-bit indices.

Xor(BitSet)

Performs an in-place logical XOR with the specified set: a bit becomes set when it is set in exactly one of the two operands (symmetric difference).

public void Xor(BitSet other)

Parameters

other BitSet

The set to combine with. Must not be null.

Remarks

The storage grows as required to accommodate other's logical Length. Passing this instance as other clears every bit.

Exceptions

ArgumentNullException

other is null.

Operators

operator ==(BitSet?, BitSet?)

Determines whether two BitSet instances contain the same set bits.

public static bool operator ==(BitSet? left, BitSet? right)

Parameters

left BitSet

The first operand, or null.

right BitSet

The second operand, or null.

Returns

bool

true if both operands are null or contain the same set bits; otherwise, false.

operator !=(BitSet?, BitSet?)

Determines whether two BitSet instances contain different set bits.

public static bool operator !=(BitSet? left, BitSet? right)

Parameters

left BitSet

The first operand, or null.

right BitSet

The second operand, or null.

Returns

bool

true if the operands differ in at least one set bit (or exactly one is null); otherwise, false.

Explicit Interface Implementations

IEnumerable<int>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<int> IEnumerable<int>.GetEnumerator()

Returns

IEnumerator<int>

An enumerator that can be used to iterate through the collection.

IEnumerable.GetEnumerator()

Returns an enumerator that iterates through a collection.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An IEnumerator object that can be used to iterate through the collection.

Applies to

ProductVersions
.NET8, 10