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() = default

Construct empty set.

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

Copy constructor.

Parameters:

bitset – The set to copy

inline constexpr BitSet(S value)

Construct from a raw set of bits.

Parameters:

value – Integral type whose bits will be interpreted as set{E}

inline constexpr BitSet(E e)

Construct set containing a single value.

Parameters:

e – Value to place in our new BitSet object

inline bool operator==(const BitSet &other) const

Compare this set with another for equality.

inline bool operator!=(const BitSet &other) const

Compare this set with another for inequality.

inline constexpr BitSet operator~() const

Obtain a set containing all elements not in this one.

inline BitSet &flip()

Flip all bits in the set.

inline BitSet &flip(E e)

Flip state of the given bit.

inline size_t count() const

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

inline BitSet &operator+=(const BitSet &rhs)

Union: Add elements to set.

inline BitSet &operator-=(const BitSet &rhs)

Remove elements from set.

inline BitSet &operator&=(const BitSet &rhs)

Intersection: Leave only elements common to both sets.

inline BitSet &operator|=(const BitSet &rhs)

Union: Add elements to set.

inline BitSet &operator^=(const BitSet &rhs)

XOR - toggle state of bits using another set.

inline bool test(E e) const

Test to see if given element is in the set.

inline bool operator[](E e) const

Read-only [] operator.

Parameters:

e – Element to test for

Return values:

bool – true if given element is in the set

inline 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 values:

BitRef – Temporary object used to do the read or write

inline bool any() const

Determine if set contains any values.

inline bool any(const BitSet &other) const

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

inline bool all() const

Test if set contains all possible values.

inline bool none() const

Test if set is empty.

inline BitSet &set()

Add all possible values to the bit set.

inline 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

inline BitSet &reset()

Remove all values from the set.

inline BitSet &reset(E e)

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

inline bool operator==(E e) const

Determine if set consists of only the one given element.

inline explicit constexpr operator S() const

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

inline constexpr S value() const

Get stored bits for this bitset.

inline size_t printTo(Print &p, const String &separator = ", ") const

Class template to print the contents of a BitSet to a String.

Note

Requires an implementation of toString(E)

Public Static Functions

static inline constexpr size_t size()

Get the number of possible elements in the set.

static inline constexpr BitSet domain()

Get the set of all possible values.

static inline constexpr S bitVal(E e)

Get the bitmask corresponding to a given value.

class BitRef