How to flip and reverse an int in C?

Question

For example:

Input: 01011111

Output: 00000101

I know I can use ~ to flip a number, but I don't know good ways to reverse it. And I'm not sure whether they can be done together.

Does anyone have any ideas?

Answer 1

For this sort of thing I'd advise you to go to the fantastic bit twiddling hacks webpage. Here's one of the solutions 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;

The multiply operation creates five separate copies of the 8-bit byte pattern to fan-out into a 64-bit value. The AND operation selects the bits that are in the correct (reversed) positions, relative to each 10-bit groups of bits. The multiply and the AND operations copy the bits from the original byte so they each appear in only one of the 10-bit sets. The reversed positions of the bits from the original byte coincide with their relative positions within any 10-bit set. The last step, which involves modulus division by 2^10 - 1, has the effect of merging together each set of 10 bits (from positions 0-9, 10-19, 20-29, ...) in the 64-bit value. They do not overlap, so the addition steps underlying the modulus division behave like or operations.

This method was attributed to Rich Schroeppel in the Programming Hacks section of Beeler, M., Gosper, R. W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972.

And here's a different solution that doesn't use 64-bit integers:

Reverse the bits in a byte with 7 operations (no 64-bit):

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

Make sure you assign or cast the result to an unsigned char to remove garbage in the higher bits. Devised by Sean Anderson, July 13, 2001. Typo spotted and correction supplied by Mike Keith, January 3, 2002.