C reverse binary

Question

Possible Duplicate:
C reverse bits in unsigned integer

How can I reverse a binary number only using binary operators?

E.g:

11100000 -> 00000111
00110100 -> 00101100
00111111 -> 11111100

Solution 1

For this sort of thing I recommend that you take a look at the awesome page Bit Twiddling Hacks.

Here is just one example solution taken from that page:

Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division)

unsigned char b; // reverse this (8-bit) byte 
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

And as pointed out in the comments, here's another option:

Reverse an N-bit quantity in parallel in 5 * lg(N) operations

unsigned int v; // 32-bit word to reverse bit order

// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles ... 
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

Solution 2

Take a look at Bit Twiddling Hacks. There's an entire section on reversing bit sequences.

Solution 3

You can see this website http://graphics.stanford.edu/~seander/bithacks.html

Reversing bit sequences
Reverse bits the obvious way
Reverse bits in word by lookup table
Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division)
Reverse the bits in a byte with 4 operations (64-bit multiply, no division)
Reverse the bits in a byte with 7 operations (no 64-bit, only 32)
Reverse an N-bit quantity in parallel with 5 * lg(N) operations

Comments

[auselen]

call it reverse instead?

[Piotr Praszmo]

stackoverflow.com/a/9144870/745924

[Matteo Italia]

Done s/invert/reverse/, with "invert" is way too easy to think you just want a not.

[Frederico Schardong]

I can not just call it reverse, they are pulled from a buffer and I need to reverse them. I believe that @Banthar's comment has what I need

[Wug]

I was going to post this but you beat me to it.

[Frederico Schardong]

And what about a 32 bits variable?

[lashgar]

@FredericoSchardong Please refer to the Section Reverse an N-bit quantity in parallel in 5 * lg(N) operations in Bit Twiddling Hacks.