Reverse bits of a given 32 bits unsigned integer

Example (Taken from leetcode):

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Approach: There are many ways to solve this problem. O(n) when n is number of bits is very trivial solution. Let's talk about a better solution:

Lets take an example of 4 bit integer first for simplicity say 13 whose 4 bit representation will be 1101. What we will try to do it is first we will reverse number by 4/2 = 2 bits and then 2/2 = 1 bit:

1. At step 1, reverse the number by 2 bits that so the number will become 01|11 => 0111. Can be done by n = ((n & 0xc) >> 2) | ((n & 0x3) << 2); 
2. At step 2, we will reverse the number 1 by 1 bit so now the number 0111 will become 1|0|1|1 => 1011. Can be done by n = ((n & 0xa) >> 1) | ((n & 0x5) << 1);

And that's it. n will be our answer so now let's take an example of 8 bit number say 10011110. Now we are going to do it in 3 steps:

1. At step1, reverse the number by 8/2 = 4 bits so the number will become 1110|1001 => 11101001. Can be done by n = ((n & 0xf0) >> 4) | ((n & 0x0f) << 4);
2. At step 2, reverse the number by 4/2 = 2 bits that so the number 11101001 will become 10|11|01|10 => 10110110. Can be done by n = ((n & 0xcc) >> 2) | ((n & 0x33) << 2); 
3. At step 3, we will reverse the number 1 by 1 bit so now the number 10110110 will become 0|1|1|1|1|0|0|1 => 01111001. Can be done by n = ((n & 0xaa) >> 1) | ((n & 0x55) << 1);

If you see the step 2 and step 3 for 8 bit integer reversal is same as step 1 and step 2 of 4 bit integer reversal. Now hopefully we understood what we are trying to do so lets see the steps for 32 bit integer:

1. Reverse the number by 32/2 = 16 bits by 16 bits.
2. Reverse the number by 16/2 = 8 bits by 8 bits.

Rest of the steps will be same as 8 bit numbers given above. 

Implementation in C#:

        public uint ReverseBits(uint n)

        {

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

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

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

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

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

            return n;

        }  

Complexity: O(logn) where n is the number of bits.