C++ bitwise operations on structs and classes

Question

I'm developing a generic Genetic Algorithm library, where the chromosome of each organism is its bit representation in memory. So, for instance, if I want to mutate a organism, I flip the bits themselves of the object randomly.

At first, I tried using the bitset class from the C++ standard library, but, when converting back to an object T, my only option was using the to_ullong member function, which was a problem for representations with a number of bits larger than the size of an unsigned long long.

Then I decided to create a generic library for bitwise operations on any object T, so I could apply these operations directly onto the objects themselves, instead of converting them first to a bitset.

So you can see what I'm trying to achieve, here's a function from the library:

template<typename T>
void flip(T& x, size_t const i)
{
    x ^= 1 << i;
}

And it's used in the GA library like this:

template<typename T>
void GeneticAlgorithm<T>::mutate(T& organism, double const rate)
{
    std::random_device rd;
    std::mt19937 mt(rd());

    std::uniform_real_distribution<double> dist(0, 1);

    for(size_t i = 0; i < m_nBits; ++i)
        if(dist(mt) <= rate)
            bit::flip(organism, i);
}

It would be really nice if this worked, however now I'm getting this error message from the VC++ 2015 RC compiler:

Severity Code Description Project File Line Error C2677 binary '^': no global operator found which takes type 'T' (or there is no acceptable conversion) GeneticAlgorithm path\geneticalgorithm\geneticalgorithm\BitManip.hpp 57

If I correct this error for the ^, I get more for the other operators.

I haven't used bitwise operators before in my code, so I guess these operators are not supposed to be used with any object? If so, how could I work around the problem?

Answer 1

What you want to achieve can be done like that (see Peter Schneider's comment):

template<typename T> void flip(T& x, size_t const i) {
    unsigned char* data = reinterpret_cast<unsigned char*>(&x);
    data[i/8] ^= (1 << (i%8));
}

what it does is reinterpreting your data x as an array of bytes (unsigned char), then determining which byte should be flipped (i/8), then which bit within the byte (i%8).

Note: in addition, it may be safe to add at the beginning of the function:

assert(i < sizeof(T)*8)

Answer 2

I am under the impression that you are not yet fully appreciating the object oriented features C++ offers. (That's not untypical when coming from a more data-centric programming in C. C++ is specifically designed to make that transition at the desired speed and to make it painless.)

My suggestion is to encapsulate the flip operation in an organism and let the organism handle it. As an illustration (untested, but compiles):

#include<climits>  // CHAR_BIT
#include<cstdlib>  // exit()

class string;
void log(const char *);

// inaccessible from the outside
constexpr int NUM_TRAITS = 1000;
constexpr size_t TRAIT_ARR_SZ = (NUM_TRAITS+CHAR_BIT-1)/CHAR_BIT;

class Organism
{ 

    char traits[TRAIT_ARR_SZ];
    int flips[NUM_TRAITS];

    /////////////////////////////////////////////////////////////
    public:

    Organism()  {  /* set traits and flips zero */  }

    // Consider a virtual function if you may derive 
    /** Invert the trait at index traitIndex */
    void flipTrait(int traitIndex)
    {
        if( traitIndex >= NUM_TRAITS ) { log("trait overflow"); exit(1); }

        int charInd = traitIndex / CHAR_BIT;
        int bitInd = traitIndex % CHAR_BIT;

        traits[traitIndex] ^= 1 << bitInd;
        flips[traitIndex]++;
    }

    // Organisms can do so much more!
    void display();
    void store(string &path);
    void load(string &path);
    void mutate(float traitRatio);
    Organism clone();
};