CODEWITHSUNDEEP
c++bit-manipulation
Raffi
Raffi

Reputation: 107

Efficient bit operations

In C++ I want to encode the bits of 3 unsigned variables into one. More precisely, when the three variables are:

A: a3 a2 a1 a0
B: b3 b2 b1 b0
C: c3 c2 c1 c0

then the output variable shall contain such triples:

D: a3 b3 c3   a2 b2 c2   a1 b1 c1   a0 b0 c0

Let's assume that the output variable is large enough for all used bits. I have come up with

unsigned long long result(0);
unsigned a,b,c; // Some numbers to be encoded
for(int level=0;level<numLevels;++level)
{
    int q(1<<level); // SearchBit q: 1<<level
    int baseShift((3*level)-level); // 0,2,4,6
    result|=(   ((a&q)<<(baseShift+2)) | ((b&q)<<(baseShift+1)) | ((c&q)<<(baseShift)) );
}

...and it works sufficiently. But I wonder if there is a solution that does not require a loop that iterates over all bits separately.

Upvotes: 0

Views: 146

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

Define a table mapping all or part of your bits to where they end up. Shift values appropriately.

unsigned long long encoder(unsigned a, unsigned b, unsigned c) {
    static unsigned const encoding[16] = {
        0b0000000000,
        0b0000000001,
        0b0000001000,
        0b0000001001,
        0b0001000000,
        0b0001000001,
        0b0001001000,
        0b0001001001,
        0b1000000000,
        0b1000000001,
        0b1000001000,
        0b1000001001,
        0b1001000000,
        0b1001000001,
        0b1001001000,
        0b1001001001,
    };

    unsigned long long result(0);

    int shift = 0;
    do {
        result += ((encoding[a & 0xF] << 2) | (encoding[b & 0xF] << 1) | encoding[c & 0xF]) << shift;
        shift += 12;
        a >>= 4;
        b >>= 4;
        c >>= 4;
    } while (a || b || c);
    return result;
}

encoding defines a table to map 4 bits into their encoded locations. This used directly for c, and shifted 1 or 2 bits for b and a. If you have more than 4 bits to process, the next 4 bits in the source values are offset 12 bits further to the left. Keep doing this until all nonzero bits have been processed.

This could use a while loop instead of a do/while but checking for zero before starting is useless unless most of the encodings are of all zero values.

If you frequently use more than 4 bits, the encoding table can be expanded and appropriate changes made to the loop to process more than 4 bits at a time.

Upvotes: 2

Related Questions