How to Reverse Bits – Bit Manipulation

Reversing bits is one of the popular problem. How to reverse bits? In this article, we going to see about how to reverse bits in an efficient way.

Reversing bits tests out understanding about bits. One of the top leetcode problem in bits section.

Let’s see our given problem,

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

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

Time to play with zeros and ones😃

Consider the below simple example to understand better,

Input: 00110
Output: 01100

Basic knowledge to have

And vs OR operator

0 & 1 = 0

1 & 1 = 1

0 & 0 = 0

0 | 1 = 1

0 | 0 = 0

1 | 1 = 1

How can I get original value back from above operations?

That is, I want given input as output. If 0 is input, I need 0 as output. If 1 is input, I need 1 as output. See the first two operations, I will get output same as the input. When I use & operator with 1, I will get my desired result here.

Let’s look at how I’m going to store these values in result.

Input: 00110

From the above diagram, I clearly explained about how I reversed the bits.

>> operator to move digits one steps to right side.

& 1 to get input digit as output.

Here, I have stored all the digits in result array or list.

Now, I have list or array, I want to make this fresh list as unsigned integer. That is the output, they asked to send.

How can I form fresh List into Unsigned integer without changing any order?

Look at below,

Consider we have a bit of 111. I want to insert 1 number to it. For that, I want to move 111 to left side, so I can insert one number into it.

Use left shift operator to allocate space for one number right to that, so remaining number moves one side to the left. And do | (OR) operator to insert number in that position. See the above illustration.

I hope, you will understand the solution approach better, now see my below code to understand the solution.

    public class Solution {
        // We need to treat n as an unsigned value
        public int reverseBits(int n) {
            int result = 0;
            for (int i = 0;i<32;i++){
                int end = n & 1;
                n >>= 1;
                result <<=1;
                result |= end;
            }
            return result;
        }
    }

If you do not understand, please take a note and trace the program with the help of my above diagrammatic illustrations. Sure, you will get an idea about reversing the bits.

One thought on “How to Reverse Bits – Bit Manipulation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s