Reverse Bits

Question: Reverse bits of a given 32 bits unsigned integer.

You may view the full question here.

Approach 1: Let’s start with a simple approach.

Step 1: Extract the right most bit in the main number

Step 2: Shift the bits in the main number by one position to the right

Step 3: Shift the bits in the reversed number by one position to the left

Step 4: Append the bit extracted in Step 1 to the partial result generated in Step 3 by doing a bitwise add operation

Repeat these steps until the main number reduces to zero.

The code would look like —

public int reverseBits(int n) {
        int rev = 0;
        while(n!=0){
            //Get the right most bit
            int right = n & 1;
            //Shift bits to the right by 1
            n = n >> 1;
            //Add the rightmost bit to the reversed number
            rev = rev << 1;
            rev = rev | right;
        }
        return rev;
    }

But this code returns the wrong result! For instance,

Input: 00000010100101000001111010011100

Output from Code: 15065253 (00000000111001011110000010100101)

Expected Output: 964176192 (00111001011110000010100101000000)

The problem with the code is that we stop evaluating when the number reduces to zero. In the above example, the input has 6 zeroes in the beginning, which do not get evaluated because the loop condition (n!=0) would cause the while loop to break.

Approach 1.1: There are 32 bits in the unsigned integer we are evaluating. To fix the previous version of the solution, we need to modify the loop condition. We will have to continue to evaluate until all the 32 bits are evaluated.

//Approach 1.1:
//Runtime: 1ms
//Memory usage: 32MB
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int rev = 0;
        int bitCount = 32;
        while(bitCount-->0){
            //Get the right most bit
            int right = n & 1;
            //Shift bits to the right by 1
            n = n >> 1;
            //Add the rightmost bit to the reversed number
            rev = rev << 1;
            rev = rev | right;
        }
        return rev;
    }
}

Find more posts here.

Cheers & Chao!