BitSet

Introduction

The C++ STL provides std::bitset which emulates an array of bool elements.

The BitSet class template provides similar support for sets of strongly-typed elements. For example:

enum class Fruit {
   apple,
   banana,
   kiwi,
   orange,
   passion,
   pear,
   tomato,
};

using FruitBasket = BitSet<uint8_t, Fruit, unsigned(Fruit::tomato) + 1>;

static constexpr FruitBasket fixedBasket = Fruit::orange | Fruit::banana | Fruit::tomato;

A FruitBasket uses one byte of storage, with each bit representing an item of Fruit. If the basket contains a piece of fruit, the corresponding bit is set. If it does not, the bit is clear.

Without BitSet you implement this as follows:

using FruitBasket = uint8_t;

static constexpr FruitBasket fixedBasket = _BV(Fruit::orange) | _BV(Fruit::banana) | _BV(Fruit::tomato);

To test whether the set contains a value you’d do this:

if(fixedBasket & _BV(Fruit::orange)) {
   Serial.println("I have an orange");
}

With a BitSet, you do this:

if(fixedBasket[Fruit::orange]) {
   Serial.println("I have an orange");
}

And you can add an element like this:

basket[Fruit::kiwi] = true;

Bit manipulation operators are provided so you can do logical stuff like this:

FruitBasket basket1; // Create an empty basket

// Add a kiwi fruit
basket1 = fixedBasket + Fruit::kiwi;

// Create a second basket containing all fruit not in our first basket
FruitBasket basket2 = ~basket1;

// Remove some fruit
basket2 -= Fruit::orange | Fruit::tomato;

And so on.

To display the contents of a BitSet, do this:

Serial.print(_F("My basket contains: "));
Serial.println(basket1);

You will also need to provide an implementation of toString(Fruit) or whatever type you are using for the set elements.

API

template<typename S, typename E, size_t size_ = sizeof(S) * 8>
class BitSet

Manage a set of bit values using enumeration.

API is similar to a simplified std::bitset, but with added +/- operators.

Note

It is important to specify size correctly when using enumerated values. In the FruitBasket example, we use a uint8_t storage type so can have up to 8 possible values. However, the Fruit enum contains only 7 values. The set operations will therefore be restricted to ensure that the unused bit is never set.

Template Parameters
  • S: Storage type (e.g. uint32_t). This determines how much space to use, and must be an unsigned integer. It is safe to use this class in structures, where it will occupy exactly the required space.

  • E: Element type e.g. enum class. You can use any enum or unsigned integer for the elements. These must have ordinal sequence starting at 0.

  • size_: Number of possible values in the set. Defaults to maximum for given storage type. Number of possible values in the set. This must be at least 1, and cannot be more than the given Storage type may contain. For example, a :cpp:type:uint8_t may contain up to 8 values.

Public Functions

constexpr BitSet()

Construct empty set.

template<typename S2>
constexpr BitSet(const BitSet<S2, E> &bitset)

Copy constructor.

Parameters
  • bitset: The set to copy

constexpr BitSet(S value)

Construct from a raw set of bits.

Parameters
  • value: Integral type whose bits will be interpreted as set{E}

constexpr BitSet(E e)

Construct set containing a single value.

Parameters
  • e: Value to place in our new BitSet object

bool operator==(const BitSet &other) const

Compare this set with another for equality.

bool operator!=(const BitSet &other) const

Compare this set with another for inequality.

constexpr BitSet operator~() const

Obtain a set containing all elements not in this one.

BitSet &flip()

Flip all bits in the set.

BitSet &flip(E e)

Flip state of the given bit.

size_t count() const

Get the number of elements in the set, i.e. bits set to 1.

BitSet &operator+=(const BitSet &rhs)

Union: Add elements to set.

BitSet &operator-=(const BitSet &rhs)

Remove elements from set.

template<>
BitSet &operator&=(const BitSet &rhs)

Intersection: Leave only elements common to both sets.

BitSet &operator|=(const BitSet &rhs)

Union: Add elements to set.

BitSet &operator^=(const BitSet &rhs)

XOR - toggle state of bits using another set.

bool test(E e) const

Test to see if given element is in the set.

bool operator[](E e) const

Read-only [] operator.

Parameters
  • e: Element to test for

Return Value
  • bool: true if given element is in the set

BitRef operator[](E e)

Read/write [] operator.

This returns a temporary

BitRef object to support assignment operations such as set[x] = value
Parameters
  • e: Element to read or write

Return Value
  • BitRef: Temporary object used to do the read or write

bool any() const

Determine if set contains any values.

bool any(const BitSet &other) const

Determine if set contains any values from another set i.e. intersection != [].

bool all() const

Test if set contains all possible values.

bool none() const

Test if set is empty.

BitSet &set()

Add all possible values to the bit set.

BitSet &set(E e, bool state = true)

Set the state of the given bit (i.e. add to or remove from the set)

Parameters
  • e: Element to change

  • state: true to add the element, false to remove it

BitSet &reset()

Remove all values from the set.

BitSet &reset(E e)

Clear the state of the given bit (i.e. remove it from the set)

bool operator==(E e) const

Determine if set consists of only the one given element.

constexpr operator S() const

Allow casts from the native storage type to get a numeric result for this set.

constexpr S value() const

Get stored bits for this bitset.

Public Static Functions

static constexpr size_t size()

Get the number of possible elements in the set.

static constexpr BitSet domain()

Get the set of all possible values.

static constexpr S bitVal(E e)

Get the bitmask corresponding to a given value.