Reverse the bits of a 32-bit integer

For example, given an integer i = 0x00000001,

i	0000	0000	0000	0000	0000	0000	0000	0001
reversal(i)	1000	0000	0000	0000	0000	0000	0000	0000

the reversed result is: 80000000.

One approach is to construct a byte wise look up table. The table is a <byte, reversal byte> container which has reversal outcome of all possible byte values indexed by the byte value. Given a particular byte value, the table provides its corresponding reversal order. For a 32-bit integer, four look ups are needed. Start the look up from the zeroth byte of the input and place the outcome as the third byte in the output. This approach can be extended to a 64-bit integer as well with a 16-bit look up table implementation. This is an efficient approach but requires additional memory to store the look up table.

Another approach is to perform an in place reversal by following the following steps. For example, let the input is 12345670.

1. Consider adjacent bits. Swap them.

i	0001	0010	0011	0100	0101	0110	0111	0000
reversal(i)	0010	0001	0011	1000	1010	1001	1011	0000

2. Consider two bits at a time in the output from step 1. Swap them.

i	0010	0001	0011	1000	1010	1001	1011	0000
reversal(i)	1000	0100	1100	0010	1010	0110	1110	0000

3. Consider four bits at a time in the output from step 2. Swap them.

i	1000	0100	1100	0010	1010	0110	1110	0000
reversal(i)	0100	1000	0010	1100	0110	1010	0000	1110

4. Consider eight bits at a time in the output from step 3. Swap them.

i	0100	1000	0010	1100	0110	1010	0000	1110
reversal(i)	0010	1100	0100	1000	0000	1110	0110	1010

5. Consider 16 bits at a time in the output from step 4. Swap them.

i	0010	1100	0100	1000	0000	1110	0110	1010
reversal(i)	0000	1110	0110	1010	0010	1100	0100	1000

The output of step 5 is the reversal outcome of the 32-bit input. The answer (in hex) in our example is 0e6a2c48.

Here is the C++ code:

void BitReversal(int inp_int) {

  inp_int = ((inp_int & 0xaaaaaaaa) >> 1) | ((inp_int & 0x55555555) << 1);

  inp_int = ((inp_int & 0xcccccccc) >> 2) | ((inp_int & 0x33333333) << 2);

  inp_int = ((inp_int & 0xf0f0f0f0) >> 4) | ((inp_int & 0x0f0f0f0f) << 4);

  inp_int = ((inp_int & 0xff00ff00) >> 8) | ((inp_int & 0x00ff00ff) << 8);

  inp_int = ((inp_int & 0xffff0000) >> 16) | ((inp_int & 0x0000ffff) << 16);

  printf("%x\n",inp_int);

}

An additional 32-bit shift step is required for a 64-bit integer reversal.