Bitset¶

1

import "std/data/bitset";

BitSet struct¶

A BitSet stores a fixed number of bits in a compact form, packing 64 bits into every machine word. Compared to a set of integers it is far denser and offers fast bitwise operations (and/or/xor/not) over the whole sequence.

The number of bits is fixed at construction time.

Time complexity:
Access (test/set/clear/flip): O(1)
Bitwise ops (and/or/xor/not): O(n / 64)
count/any/none/all: O(n / 64)

Invariant: bits beyond numBits in the last word are always kept zero, so that count(), any() and all() never observe stale padding bits.

Constructors¶

ctor¶

1

public p BitSet.ctor(unsigned long numBits = 0l)

Construct a bit set holding the given number of bits, all initialized to 0

Parameters

ctor¶

1

public p BitSet.ctor(unsigned int numBits)

Construct a bit set holding the given number of bits, all initialized to 0

Parameters

ctor¶

1

public p BitSet.ctor(unsigned long numBits, bool initialValue)

Construct a bit set holding the given number of bits, all initialized to the given value

Parameters

ctor¶

1

public p BitSet.ctor(const BitSet& original)

Construct a bit set as a deep copy of another bit set

Parameters

Methods¶

set¶

1

public p BitSet.set(unsigned long index)

Sets the bit at the given index to 1

Parameters

set¶

1

public p BitSet.set(unsigned long index, bool value)

Sets the bit at the given index to the given value

Parameters

clear¶

1

public p BitSet.clear(unsigned long index)

Clears (sets to 0) the bit at the given index

Parameters

flip¶

1

public p BitSet.flip(unsigned long index)

Flips (toggles) the bit at the given index

Parameters

test¶

1

public f<bool> BitSet.test(unsigned long index)

Returns the value of the bit at the given index

Parameters

Returns: bool — true if the bit is set, false otherwise

setAll¶

1

public p BitSet.setAll()

Sets all bits in the set to 1

clearAll¶

1

public p BitSet.clearAll()

Clears all bits in the set to 0

flipAll¶

1

public p BitSet.flipAll()

Flips (toggles) all bits in the set

count¶

1

public f<unsigned long> BitSet.count()

Returns the number of bits that are set to 1

Returns: unsigned long — Number of set bits

getSize¶

1

public f<unsigned long> BitSet.getSize()

Returns the number of bits in the set

Returns: unsigned long — Number of bits

any¶

1

public f<bool> BitSet.any()

Checks whether at least one bit is set

Returns: bool — true if any bit is set

none¶

1

public f<bool> BitSet.none()

Checks whether no bit is set

Returns: bool — true if no bit is set

all¶

1

public f<bool> BitSet.all()

Checks whether all bits are set

Returns: bool — true if every bit is set

toString¶

1

public f<String> BitSet.toString()

Builds a string representation of the set, with the highest index bit first (MSB-first)

Returns: String — String of '0' and '1' characters

Operators¶

operator=¶

1

public p operator=(BitSet& this, const BitSet& newValue)

Copy-assign the contents of another bit set into this one

Parameters

operator[]¶

1

public f<bool> operator[](const BitSet& bs, unsigned long index)

Returns the value of the bit at the given index

Parameters

Returns: bool — true if the bit is set, false otherwise

operator==¶

1

public f<bool> operator==(const BitSet& lhs, const BitSet& rhs)

Check if two bit sets are equal, i.e. they have the same size and the same bits set

Parameters

Returns: bool — Equal or not equal

operator!=¶

1

public f<bool> operator!=(const BitSet& lhs, const BitSet& rhs)

Check if two bit sets are not equal

Parameters

Returns: bool — Not equal or equal

operator&¶

1

public f<BitSet> operator&(const BitSet& lhs, const BitSet& rhs)

Compute the bitwise AND of two equally sized bit sets

Parameters

Returns: BitSet — New bit set holding the bitwise AND

operator|¶

1

public f<BitSet> operator|(const BitSet& lhs, const BitSet& rhs)

Compute the bitwise OR of two equally sized bit sets

Parameters

Returns: BitSet — New bit set holding the bitwise OR

operator^¶

1

public f<BitSet> operator^(const BitSet& lhs, const BitSet& rhs)

Compute the bitwise XOR of two equally sized bit sets

Parameters

Returns: BitSet — New bit set holding the bitwise XOR

operator~¶

1

public f<BitSet> operator~(const BitSet& bs)

Compute the bitwise NOT (complement) of a bit set

Parameters

Returns: BitSet — New bit set holding the bitwise complement