bit_fiddling.cc

/* bit_fiddling.cc */

#include <iostream>

/* Rotate the bits of x to the right by I bits. */
template <typename T>
inline T rotate_right(const T & x, const int & I)
{
    const int N = sizeof(T) * 8;
    const int reduced_I = I % N;
    if (reduced_I > 0) {
        const int J = (N - reduced_I) % N;
        const T low = x >> reduced_I;
        const T high = x << J;
        const T y = low | high;
        return y;
    } else {
        return x;
    }
}

/* Rotate the bits of x to the left by I bits. */
template <typename T>
inline T rotate_left(const T & x, const int & I) {
    const int N = sizeof(T) * 8;
    const int reduced_I = I % N;
    const int J = (N - reduced_I) % N;
    return rotate_right<T>(x,J);
}
/* Have the static value of X rotated to the right by I bits. */
template <typename T,int I,T X>
struct RotateRight {
    static const int N = sizeof(T) * 8;
    static const int reduced_I = I % N;
    static const int J = (N-reduced_I) % N;
    static const T value = (X >> reduced_I) | (X << J);
};
template <typename T,T X>
struct RotateRight<T,0,X> {
    static const T value = X;
};
/* Have the static value of X rotated to the left by I bits. */
template <typename T,int I,T X>
struct RotateLeft {
    static const int N = sizeof(T) * 8;
    static const int reduced_I = I % N;
    static const int J = (N-reduced_I) % N;
    static const T value = (X << reduced_I) | (X >> J);
};
template <typename T,T X>
struct RotateLeft<T,0,X> {
    static const T value = X;
};

/* Reverse the I bit sized blocks of the N bit sized word. */
template <typename T, int I,int N, int S, bool CONTINUE>
struct BitReverse {
    static const T unity = 1;
    static const T unrotated_low_bitmask = static_cast<T>(-1) / ((unity << I) + unity);
/* This mask corresponds to the lower bit-blocks. */
    static const T low_bitmask = RotateLeft<T,S,unrotated_low_bitmask>::value;
/* This mask corresponds to the upper bit-blocks. */
    static const T high_bitmask = ~low_bitmask;

    static const T inner(const T & x) {
/* Extract the lower bit-blocks and swap them with the upper bit-blocks by rotating
   them to the left by twice the size of a bit-block. */
        const T low = rotate_left<T>(x & low_bitmask,I*2);
        const T rotated_high = x & high_bitmask;
        const T next = low | rotated_high;
/* The size of the next bit-blocks are twice the size of the current bit-blocks. */
        const int next_I = I*2;
/* The accumulated shift increases by the size of a bit-block. */
        const int next_S = (S+I)%N;
        const bool next_CONTINUE = next_I < N;
        return BitReverse<T,next_I,N,next_S,next_CONTINUE>::inner(next);
    }
};

template <typename T,int I,int N,int S>
struct BitReverse<T,I,N,S,false> {
    static const T inner(const T & x) {
/* Undo the rotations. */
        return rotate_right<T>(x,S);
    }
};

template <typename T>
static const T bit_reverse(const T & x) {
    const int N = sizeof(T) * 8;
    return BitReverse<T,1,N,0,true>::inner(x);
}

/* Count the number of set bits in an N bit sized word. */
template <typename T, int I,int N, bool CONTINUE>
struct PopulationCount {
    static const T unity = 1;
    static const T low_bitmask = static_cast<T>(-1) / ((unity << I) + unity);
    static const int inner(const T & x) {
/* Extract the lower bit-blocks. */
        const T low = x & low_bitmask;
/* Extract the upper bit-blocks and shift them to coincide with the lower bit-blocks. */
        const T high = (x >> I) & low_bitmask;
/* Add the bit-blocks. */
        const T next = low+high;
/* The size of the next bit-blocks are twice the size of the current bit-blocks. */
        const int next_I = I*2;
        const bool next_CONTINUE = next_I < N;
        return PopulationCount<T,next_I,N,next_CONTINUE>::inner(next);
    }
};

template <typename T,int I,int N>
struct PopulationCount<T,I,N,false> {
    static const int inner(const T & x) {
/* The input contains the population count. */
        return static_cast<int>(x);
    }
};

template <typename T>
static const int population_count(const T & x) {
    const int N = sizeof(T) * 8;
    return PopulationCount<T,1,N,true>::inner(x);
}

using namespace std;
template <typename T>
void do_test()
{
    const int N = sizeof(T)*8;
    T m = 0;
    for (int i = 0; i<N; i++) {
        const T n = 1UL << i;
        m += n;
        cout << hex << n << " : ";
        cout << hex << bit_reverse(n) << " : ";
        cout << dec << population_count(m) << endl;
    }
}

int count_byte(const unsigned char x)
{
    return population_count(x);
}

int count_uint32(const unsigned int x)
{
    return population_count(x);
}

unsigned long long reverse_uint64(const unsigned long long x)
{
    return bit_reverse(x);
}
int main(int argc, char * argv[])
{
    do_test<unsigned char>();
    do_test<unsigned short>();
    do_test<unsigned int>();
    do_test<unsigned long long>();

    return 0;
}