Compile Time Sets in C++

I found myself needing a set data structure for an enum, and it had to have a very fast membership check operation. Since the elements of each instance of the set were known at compile-time, I used a neat meta-programming trick to get a "compile-time set" based on bitmasks.

Since it uses bit masks to track which values are in the set, it's pretty much limited to working with enum values only (actually small integers, technically), but I still found it useful. It's more interesting as an example of meta-programming than as an actual data structure, since it's so special-purpose. But I like it :-)

Here's the C++ (note that this one only supports 64 possible values, but it's possible to extend it to fit your needs). It compiles with MSVC 2010 (haven't tested it other compilers).

template<uint32_t a, uint32_t b> struct CompileTimeEnumSet {
    // Bit-counting hack from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
    enum { Size =
        (((a & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f) +
        ((((a & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f) +
        (((a >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f) +
        (((b & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f) +
        ((((b & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f) +
        (((b >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f)
    };

    // Can be optimized to returning a constant value at compile time
    template<SomeEnum t> inline static bool
    contains() {
        auto u = static_cast<uint32_t>(t);
        return (((b * (u / 32)) & (1 << (u & 31))) | ((a * (1 - u / 32)) & (1 << (u & 31)))) != 0;
    }

    // Run-time set membership test
    inline static bool
    contains(SomeEnum t) {
        auto u = static_cast<uint32_t>(t);
        return (((b * (u / 32)) & (1 << (u & 31))) | ((a * (1 - u / 32)) & (1 << (u & 31)))) != 0;
    }

    template<uint32_t Ba, uint32_t Bb> inline CompileTimeEnumSet<a | Ba, b | Bb>
    operator|(CompileTimeEnumSet<Ba, Bb> const&) const {
        return CompileTimeEnumSet<a | Ba, b | Bb>();
    }

    template<uint32_t Ba, uint32_t Bb> inline CompileTimeEnumSet<a & ~Ba, b & ~Bb>
    operator-(CompileTimeEnumSet<Ba, Bb> const&) const {
        return CompileTimeEnumSet<a & ~Ba, b & ~Bb>();
    }

    template<uint32_t Ba, uint32_t Bb> inline CompileTimeEnumSet<a & Ba, b & Bb>
    operator&(CompileTimeEnumSet<Ba, Bb> const&) const {
        return CompileTimeEnumSet<a & Ba, b & Bb>();
    }
};

template<uint32_t t> inline CompileTimeEnumSet<((1 - t / 32) << ((1 - t / 32) * t)),
    ((t / 32) << ((t / 32) * (t - 32)))>
SingleItemSet() {
    return CompileTimeEnumSet<((1 - t / 32) << ((1 - t / 32) * t)),
        ((t / 32) << ((t / 32) * (t - 32)))>();
}

typedef CompileTimeEnumSet<0, 0> EmptySet;

Usage:

enum SomeEnum { Foo, Bar, Baz, Quux };

auto set = (EmptySet() | SingleItemSet<Foo>() | SingleItemSet<Quux>()) & SingleItemSet<Foo>();

assert(set.contains<Foo>());
assert(set.contains(Foo));
assert(!set.contains<Bar>());
assert(!set.contains<Quux>());
assert(decltype(set)::Size == 1);