Bits Reversal - Advanced

Suppose we have 16-bit number where we want to reverse some bits between bits i'th and j'th.  To illustrate that, say we have a 16-bit value stored in v:

|<-------- L = sizeof(short)*CHAR_BIT --------->|
 15                       7                1   0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  | x| x| x| x| x| x| x|  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
          ^                  ^
          |                  |
         i=12               j=6
|<------>|
 L - i - 1
  

So, we want to reverse bits between bits 6th to 12th.

Assume i is always greater than j (i > j):
Number of bits to reverse: n = (i - j) + 1

Mask to use: (2^n - 1) << j

Or, in the case above:

n = (12 - 6) + 1 = 7
mask = (2^7 - 1) << 6 = 127 << 6  = 0x1FC0 (0001111111000000 in binary)

Then we mask the bits stored in v and shift it back to 0 (to do reverse operation):

r = (v & mask)  >> j;

r =
 15                       7                1   0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 0| 0| 0| 0| 0| 0| x| x| x| x| x| x| x|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+


We use bit reversal operation as posted previously on r:

r = bit_reversal(r);

After this call, the bits are reversed, but filled in from MSB.  We need to put them to the position originally started.

 15                       7                1   0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| x| x| x| x| x| x| x|  |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                    |-------> shr 3

<========= sizeof(unsigned int)* CHAR_BIT ======>

m = sizeof(short) * CHAR_BIT - n - j
m = 2*8 - 7 -6 = 16 - 13 = 3

Final result is:

(v & !mask) | ((r >> m) & mask);

Bit Reversal - Explained

The page Bit Twiddling Hacks shows how to reverse bits in an integer (e.g, reverse LSB with MSB bits or reading bits from the opposite direction), but seems it doesn't explain anything why that works.

Here I try to explain it step by step.  Let start with a 8-bit char first.  Assume each letter in ABCDEFGH represents each bits in the char (e.g, A is for MSB etc.).

x = ABCDEFGH

ABCDEFGH
10101010 (or 0xAA)
-------- &
A0C0E0G0  ---- >> 1 : 0A0C0E0G

ABCDEFGH
01010101 (or 0x55)
-------- &
0B0D0F0H  ---- << 1 : B0D0F0H0

0A0C0E0G
B0D0F0H0
-------- |
BADCFEHG  ---> stored as a new x, then we do next operation

BADCFEHG
11001100  (or 0xCC)
--------- &
BA00FE00  ---- >> 2: 00BA00FE

BADCFEHG
00110011  (or 0x33)
--------- &
00DC00HG  ---- << 2: DC00HG00

00BA00FE
DC00HG00
-------- |
DCBAHGFE


Last, we operate the similar thing on the high and low nibbes:

DCBAHGFE
11110000 (or 0xF0)
-------- &
DCBA0000   ==> >> 4 = 0000DCBA

DCBAHGFE
00001111 (or 0x0F)
-------- &
0000HGFE   ==> << 4 = HGFE0000

0000DCBA
HGFE0000
--------|
HGFEDCBA

Finally, we now get HGFEDCBA which is the reversed bits of ABCDEFGH!  To summarize, to reverse bits in an octet, we do operations:

x = (x & 0xAA >> 1) | (x & 0x55 << 1);
x = (x & 0xCC >> 2) | (x & 0x33 << 2);
x = (x & 0xF0 >> 4) | (x & 0x0F >> 4);

For operation on 32-bit data, we do the similar one, except we do with 32-bit mask (instead of 10101010 binary or 0xAA, we mask with 0xAAAAAAAA) plus extra two pair of masks (0xF0F0F0F0 and 0x0F0F0F0F, 0xFF00FF00 and 0x00FF00FF) with shift left/right 4, 8 and 16 bit.

So, bit-reversal computation or algorithm for 32-bit integer:

unsigned int reverse_bits(unsigned int x)
{
    x = ((x & 0xA0A0A0A0) >> 1) | ((x & 0x05050505) << 1);
    x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);

    x = ((x & 0x0F0F0F0F) >> 4) | ((x & 0xF0F0F0F0) << 4);
    x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
    return (x >> 16) | (x << 16);

}