Flip bitmask horizontally

Question

is there any easy way to flip a bitmask horizontally, a oneliner? It should do the following:

0b1010101111001101 -> 0b1011001111010101

A straight forward solution would be doing it bit for bit:

uint16 flipUint16Horizontally(uint16 bitmask)
{
    uint16 flippedMask = 0;
    for(unsigned int bit = 0; bit < 16; ++bit)
    {
        uint16 currentBit = (bitmask & (1 << bit)) >> bit;
        flippedMask |= currentBit << (15 - bit);
    }
    return flippedMask;
}

Is there a more elegant way?

You can find several approaches [here](https://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious); however, none of the ideas can be called a 'one-liner'. — Codor, Nov 17 '16 at 10:44
"one-liner" and "not the stupid way" are usually not compatible. — Lundin, Nov 17 '16 at 10:45
@Lundin Could you dup-close it, I have already used my vote incorrectly and had to revert? Thanks. https://stackoverflow.com/questions/2253166/reverse-bit-pattern-in-c — 2501, Nov 17 '16 at 10:50
[In C/C++ what's the simplest way to reverse the order of bits in a byte?](http://stackoverflow.com/q/2602823/995714) — phuclv, Nov 17 '16 at 10:56
@LưuVĩnhPhúc That's not a good dup as it's asking for a byte. The one I posted is better since it applies to unsigned types and is only for C. — 2501, Nov 17 '16 at 10:58

score 0 · Answer 1 · answered Nov 17 '16 at 12:08

Given that you have a uint16 there, a lookup table. That's a one liner for the reverse, of course the initialization takes some more work. It's not necessarily the fastest way either since that's a pretty big table and you'll probably index into it relatively randomly which is liable to cause cache misses. Also still simple, and a lot less space-hungry: a lookup table that reverses bytes. Use it the obvious way:

return (bitreverse[x & 0xFF] << 8) | bitreverse[x >> 8];

Of course you still need to deal with the initialization, but speed matters less there.

There is an (in my opinion) more elegant but a bit more complicated way using only some bitwise operations (and no totally incomprehensible remainder operations or anything like that), reversing first adjacent bits, then adjacent 2-bit pieces, then adjacent nibbles, and so on doubling the width of the reversed thing every step until in the end all the bits are reversed "globally". You can reorder these steps by the way, and there is a way to write them with one operation less but also less ILP.

x = ((x & 0x5555) << 1) | ((x >> 1) & 0x5555); // swap bits
x = ((x & 0x3333) << 2) | ((x >> 2) & 0x3333); // swap 2-bit pieces
x = ((x & 0x0f0f) << 4) | ((x >> 4) & 0x0f0f); // swap nibbles
return (x >> 8) | (x << 8); // optimized last step

Flip bitmask horizontally

1 Answers1