Reverse integer bitwise without using loop

Question

I want to write a program which reverses the bits of an integer.
Ex 11000101 to 10100011
I know how to solve this using a loop, but I came across solutions that do it using byte shift:

num>>4|num<<4

I don't understand how does this work. Can somebody hep me with this?

Answer 1

That's not reversing the bits, it's swapping the nybbles (4-bit units). In other words, it will turn:

1100 0101 (abcd efgh)

into:

0101 1100 (efgh abcd)

and it will do so only if the data type is actually 8 bits (otherwise num << 4 places some bits left of the eight rightmost ones. A safer way to do it is to ensure all other bits are cleared before shifting:

((num & 0xf0) >> 4) | ((num & 0x0f) << 4)

For a precis on how bitwise operators work, see this excellent answer.

The equivalent expression for a full bit reversal, hgfe dcba, is the rather monstrous:

  ((num & 0x01) << 7)
| ((num & 0x02) << 5)
| ((num & 0x04) << 3)
| ((num & 0x08) << 1)
| ((num & 0x10) >> 1)
| ((num & 0x20) >> 3)
| ((num & 0x40) >> 5)
| ((num & 0x80) >> 7)

which extracts and shifts each of the eight bits.

There are also optimisations that can handle groups of non-contiguous bits in one operation, such as:

num = ((num & 0xf0) >> 4) | ((num & 0x0f) << 4) // abcdefgh -> efghabcd
num = ((num & 0xcc) >> 2) | ((num & 0x33) << 2) // efghabcd -> ghefcdab
num = ((num & 0xaa) >> 1) | ((num & 0x55) << 1) // ghefcdab -> hgfedcba

These work by grabbing the non-contiguous bits and moving them left or right, with the mask values showing which bits get affected:

0xf0, 0x0f -> 1111-0000, 0000-1111, shift by 4
0xcc, 0x33 -> 1100-1100, 0011-0011, shift by 2
0xaa, 0x55 -> 1010-1010, 0101-0101, shift by 1

The first bit mask in each line extracts the bits to shift right, the second grabs the bits to shift left. The two results are then recombined. To take the second one as an example, say you have the bits abcdefgh beforehand and you evaluate the expression ((num & 0xcc) >> 2) | ((num & 0x33) << 2):

(num&0xcc)>>2     (num&0x33)<<2
-------------     -------------
  abcdefgh          abcdefgh
  11001100          00110011        'and' with mask
  --------          --------
  ab00ef00          00cd00gh
  00ab00ef          cd00gh00        shift right/left
          \        /
           00ab00ef
           cd00gh00                 'or' them together
           --------
           cdabghef

Hence you can see how the actions of bit extraction, shifting and recombination allow you to reverse the order of sections within the value:

ab   cd   ef   gh
  \ /       \ /
   X         X
  / \       / \
cd   ab   gh   ef

I suggest you try a similar experiment with the third operation num = ((num & 0xaa) >> 1) | ((num & 0x55) << 1), you'll see it also acts as expected, reversing individual bits in each group of two.

Answer 2

As mentioned, it's not reversing the bits, just the nibbles. But you can decompose a real bit-reversal to something like that as well, like this (not tested):

// swap nibbles
x = x >> 4 | x << 4;
// swap groups of 2
x = (x >> 2) & 0x33 | (x & 0x33) << 2;
// swap groups of 1
x = (x >> 1) & 0x55 | (x & 0x55) << 1;

You can of course extend that pattern to reverse a wider number. Every additional step doubles the width of the number it reverses, which makes this method far more scalable than moving every bit to its position one by one. To reverse a 64bit number, this algorithm takes only 6 "steps" (at 5 operations for all but 1 step, so roughly 30 operations) whereas the bit-by-bit algorithm takes 64 steps (at 3 operations per step except one, so 191 operations).

You can reorder the steps, if you want.