Reverse Bits

Problem Statement:

You are given a number as input. You need to reverse the bits in it’s binary form and print the output. The maximum length is a 32-bit unsigned integer.

Example:

Let’s see how to solve this problem

Let us take a simple problem and solve;

Input: 1010001
Output: 1000101

To arrive at the solution, it is a 2 step process.

Step 1: Insert the binary numbers in an array
Step 2: Take the reverse of the numbers that you have inserted into the array,

To inset the binary numbers in an array, we do below operations:

Here we use bitwise and [&] and right shift operator[>>] to arrive at the solution.

In bitwise and, we know that

1 & 1 = 1
0 & 1 = 0

With the help of this, it is possible to know the set and unset bits.

Now let us solve the above problem step by step.

Pass 1:

Now we have to go to the next bit. To go to next bit, we need to push the right most bit. To do that, we do a right shift operation for 1 time. i.e >>1

So we get

Pass 2:

Again do a right shift operation. All the remaining passes will be as below:

Pass 3:

Pass 4:

Pass 5:

Pass 6:

Pass 7:

Now that we have got the binary representation, we need to store it in reverse.

How do we take the reverse of 1010001?

We can do that with help of bitwise or operator and left shift operator.

When you do a left shift operation, a “0” will be added at the end.

Example:

101 << 1 will give 1010

So to insert “0” or “1” value to 1010, you can just use or operator to it.

Solution in C++

#include<iostream>

using namespace std;

void reverse_bits( uint32_t num) 
{
    uint32_t result = 0;
    for( int i = 0; i < 32; i++, num >>= 1 )
    {
        if( num & 1 )
        {
            result =  result | 1 << ( 31 - i );
        }
    }
       
    cout<< "The reverse number in int value is = " << result<<endl;
    cout<< "The reverse number in binary format is = " << bitset<32>(result)<<endl;
}

int main()
{
	uint32_t num = 43261432;
	cout<< "The num in int value is = " <<num<<endl;
	cout<< "The num in binary format is = " << bitset<32>(num)<<endl;

	reverse_bits(num);

	return 0;
}