Efficient bit operations

Question

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.

is the number of bits fixed? because you could easily unroll the loop manually — Domso
– Domso, Commented Dec 11, 2018 at 20:10
Check sizeof(unsigned long) before you get too carried away - it's very likely less than 12. Why are you wanting to do this? — TypeIA
– TypeIA, Commented Dec 11, 2018 at 20:10
sizeof(..) is checked, yes. It is used for a tree data structure. The number of bits is not fixed. Typically 8-10 but can be more. — Raffi
– Raffi, Commented Dec 11, 2018 at 20:15
OK, you also say "Let's assume that the output variable is large enough for all used bits," but the example you show is too large to fit in an unsigned long on any modern mainstream platform. — TypeIA
– TypeIA, Commented Dec 11, 2018 at 20:16
An unsigned long is 64 bits on LP64. But we can use unsigned long long also. — Raffi
– Raffi, Commented Dec 11, 2018 at 20:21

1201ProgramAlarm · Accepted Answer · 2018-12-12 05:57:42Z

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.

Collectives™ on Stack Overflow

Efficient bit operations

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related