Finding an alternative to std::bitset

In one of my games I ran into a seemingly simple problem: saving a puzzle state (ie. completed/not completed) for each of 105 available levels. Naturally first thing that came to mind was a static bool array with required amount of entries – both easy to maintain and write to disk without hassle:

bool m_levelComplete[105];  // array of 105 bools (in most cases: 8 * 105 bits)

That would serve my purpose well but I felt like expanding on the problem a bit. In my particular case, the array would take 105 bytes (or 840 bits). Not too much, but the excessive redundancy felt “dirty”, so I decided to tackle this issue and find a different way. Second solution that came to my mind was using a std::bitset object:

#include <bitset>
std::bitset<105> m_levelComplete;  // better in terms of size but still "not quite right"

A lot better in terms of storage, std::bitset felt like the thing I needed... with one (well, two, as it turned out later) exceptions: it was not trivial to serialize and store to disk (which I didn’t like) and it produced erratic behavior on one of the target platforms (Nintendo 3DS). For various reasons I also needed to know the underlying type of variables that the bits were “stored in”, so this particular implemenation didn’t fit my purpose. Eventually I started implementing a simple bitset/bit vector of my own:

#define BS_NUM_ELEM (size_t)(numBits / (sizeof(storageType) * 8) + numBits / (sizeof(storageType) * 8) % 2)

template<typename storageType, size_t numBits> class BitSet
{
    storageType m_bits[BS_NUM_ELEM];
};

For starters, I encapsulate m_bits array of desired data type. In order to satisfy the amount of bits, I calculate the required amount of array elements using the BS_NUM_ELEM macro. As you can see, the number of elements will be always rounded up, so we get nicely aligned data. For example: using unsigned long long for underlying type (and assuming it’s 64 bit in size), we get m_bits[2], so essentialy 128 available bits. Since this is a regular C-style array it will be easily saved to file but also size redundancy will be low (depending on which data type you use, the redundancy can get even lower). Having this very basic structure, I needed a way to set, clear and access individual bits:

#define BS_NUM_ELEM (size_t)(numBits / (sizeof(storageType) * 8) + numBits / (sizeof(storageType) * 8) % 2)

template<typename storageType, size_t numBits> class BitSet
{
public:
    // set bit value
    void Set(size_t bitNo)
    {
        for (size_t i = 0; i < BS_NUM_ELEM; ++i)
        {
            if (bitNo < (i + 1) * sizeof(storageType) * 8)
            {
                m_bits[i] |= ((storageType)0x01 << (bitNo - i * sizeof(storageType) * 8));
                break;
            }
        }
    }

    // clear bit value
    void Clear(size_t bitNo)
    {
        for (size_t i = 0; i < BS_NUM_ELEM; ++i)
        {
            if (bitNo < (i + 1) * sizeof(storageType) * 8)
            {
                m_bits[i] &= ~((storageType)0x01 << (bitNo - i * sizeof(storageType) * 8));
                break;
            }
        }
    }

    // access bit value
    bool operator[](size_t bitNo)
    {
        for (size_t i = 0; i < BS_NUM_ELEM; ++i)
        {
            if (bitNo < (i + 1) * sizeof(storageType) * 8)
            {
                return ((m_bits[i] >> (bitNo - i * sizeof(storageType) * 8)) & 0x01) && 0x01;
            }
        }

        return false;
    }

private:
    storageType m_bits[BS_NUM_ELEM];
};

The code should be fairly self explanatory (I omitted constructors for clarity). First we determine in which stored variable our desired bit resides. Once it’s located, we set/clear proper bit in said variable. Accessing the bit is done easily with operator[] – note how I return a boolean which simply determines whether desired bit is non-zero.

// Usage
BitSet<unsigned long long, 104> bv; // create an "aligned" 128 bit set stored in two ULL variables.
printf("%d", sizeof(bv)); // 16 bytes/128 bits
bv.Set(24); // set bit 24
bv.Set(103); // set bit 103

...

Full template code can be downloaded from: https://github.com/kondrak/cpp_tools/tree/master/bitset