Data Structures & Algorithms in Java – Binary – Reverse Bits

Problem:

Given a number , reverse the bits in that number

Input:

00000010100101000001111010011100

Output:

00111001011110000010100101000000

Since in Java the above binary number will be represented as an integer , the output should be

964176192

which is the decimal equivalent of the above binary number

Assumptions:

• The input is stored in 32 bits (which is the case in Java anyways)

Try out the solution here:

https://leetcode.com/problems/reverse-bits/

Solution:

Hint:

• Use shift operators to get the last digit and to construct the new reversed number step by step
• Make use of the assumption that the reversed digit is 32 bits length

Algorithm:

STEP1: Initialize result variable to zero

STEP2: Run a loop from 0 to 31 (representing the 32 bits )

STEP 2a: Left shift the result variable by one position , this will append a zero bit to the end of the variable

STEP 2b: Find the last bit of the given number by performing AND operation between the number and 1.

STEP 2c: Add the last bit to the result

STEP 2d: Right shift the given input number by 1 so that the last bit is stripped and you can continue the above steps again

Let’s look into the code and then run a sample to see how it works

Code:

public class Solution {
    
    public int reverseBits(int n) {
        
        
  
        int result =0;
        
    
        for(int i=0;i<32;i++){
            
            
                result = result <<1;
                       
                
                result = result + (n&1);
            
            
                n = n >>1;
      
          
        
    }
        
        return result;
        
    }
}

The basic logic is to make place in the result variable to store the next bit , find the last bit from the input and append it to the result. Keep doing this until you have processed all the bits.

Example:

Let us consider a input of less than 32 bits for simplicity.

Let’s consider a input of size 4 bits:

1101

The result is also going to be stored in 4 bits again as said earlier for simplicity.

First initialize a result variable to 0.

result = 0;

Next iterate through the input 4 times

Iteration 1:

result = 0, input = 1101

Left shift result variable by 1 place

Since it is already 0 , it remains 0.

Find the last bit by using AND Operation :

1101 & 0001 = 1

The last bit is 1

Add this to the result variable:

result = 0 + 1 = 1

Right shift the input by 1 so that the last bit which is already processed is stripped off:

1101 >> 1 = 0110

This is the new input now.

Iteration 2:

result = 1 , input = 0110

Left shift result by 1:

result = 0001 << 1 = 0010

Find the last bit

input & 1 = 0110 & 0001 = 0

Add this to result

result = 0010 + 0 = 0010

Right shift input by 1

0110 >> 1 = 0011

This is the new input now

Iteration 3:

result = 0010 , input = 0011

Left shift result by 1

result = 0010 << 1 = 0100

Find the last bit:

0011 & 0001 = 0001

Add the last bit to result

result = 0100 + 0001 = 0101

Right shift the input by 1

0011 >> 1 = 0001

Iteration 4:

result – 0101 , input – 0001

Left shift result by 1

result = 0101 << 1 = 1010

Find last bit from input :

0001 & 0001 = 0001

Add that to result :

result = 1010 + 0001 = 1011

Right shift input by 1:

0001 >> 1 = 0000

The input is now 0 , so we stop the iteration.

The result is now 1011 which is the reverse of the input 1101!

Time complexity of the above algorithm is O(logn) since you iterate through the for loop for 32 times but the value of n can be 2^32 in the worst case.

That’s it!