A language that doesn't affect the way you think about programming is not worth knowing.
Print Binary and Reverse Bits
Welcome back, dear reader. So, in this article, we will discuss this problem called PRINT BINARY AND REVERSE BITS. So, what does this question say? We will be given an input number. We have to print the binary representation of this number and then, reverse the bits of this number and print the number in decimal form as the result. For instance, if N=11 is the input then the binary form of 11 is 1011. So, we will print 1011. After this, we will reverse the bits i.e. the bits will become 1101 and this number in the decimal number system is 13. So, we will print 13.
So, dear reader, we hope that you have understood the question completely. You may refer to the PRINT BINARY AND REVERSE BITS VIDEO to understand the question if you have any doubts regarding it. We recommend you try to solve this problem on your own first and then refer to the solution to make your concept strong.
Approach :
Time Complexity: O(n) where n is the number of bits in an integer i.e. 32. So, in a way, we can also say O(32) i.e. O(1).
Space Complexity: O(1)
Algorithm:
Create a mask that has 1 at the same bit position which we are at in our number and take its AND with the input number. If the AND is 0, the bit is 0 else it is 1.
Start printing the number when you get the 1st non-zero value after performing the AND operation.
For reversing the bits, create a mask with 1 at the 0th bit initially and keep moving the 'j' variable forward and setting the ' jth ' bit for the set bit in N.
Explanation:
So, dear reader, we hope that you have understood the question now and you have also tried to solve it yourself. So we have two parts to the question, the first part is about printing the number in the binary form and the second part is about reversing the bits of the number. Let us discuss the first part of the question where we have to print the binary representation of the input number.
Printing the Binary Representation:
Let us say that the input number is 11. The binary form of 11 is 1101. We have to print this binary form of 11. So, for doing this we will require a mask. Dear reader, we recommend you watch the INTRODUCTION TO BIT MANIPULATION VIDEO as we have covered some basics of this question in that video.
So, you already know how to check a bit. Have a look at the diagram given below.
n the above diagram, we saw that we have represented the binary number using 32 bits. This is because We are dealing with the integer (int) data type which has 32 bits. After all, it is of four bytes. The most significant bit is represented by index 31 and the least significant bit is indexed zero. We will create a mask in such a way that if we are checking the indexth bit then the mask will have 1 at that position and all the other bits of the mask will be zero.
We will take the AND of the input number with the mask that we have created. When we are at the indexth bit, and we take the AND of the input number with our mask and the answer comes out to be zero, this means that the indexth bit of the number was 0. Have a look at the image shown below :
As you can see in the image above, since the result of the AND operation of the mask we created and the input number is 0, this means that the indexth bit of the input number was zero.
Since integer data type is 32 bytes and 11 is just a 4-bit binary number, therefore the first 28 bits of the input number will be 0.
The mask will be modified accordingly. As already discussed, the mask will be designed in such a way that it has 1 at the bit position that we are checking and all the other bits are 0. Have a look at a random index idx that we are at, during this procedure.
If the result of the AND operation of the mask and the input number is non-zero, this means that the indexth bit of the number is non-zero.
Have a look at the image given below.
As you can see from the image above, we are now at index 3. The bit at index 3 is 1 and the mask will also have this bit set. Therefore, 1 AND 1 results in leaving 1 at this indexth bit and the overall answer of the N AND mask is non-zero. This is the first time that we have encountered a non-zero answer for N AND mask. Therefore, we will print 1 in the console.
After this, if the answer for the further bits comes out to be zero, we will print 0 in the console and if the answer comes out to be non-zero, we will print 1.
In this way, we will be able to print the entire number. Have a look at the image given below:
So, dear reader, we hope that you have understood the process till here. If you have any doubts regarding this process, refer to the solution video to understand the above procedure completely and also the code below which shows the above procedure for printing the binary representation of any number.
Java code (For printing Binary Representation)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
boolean flag = false;
for(int i = 31;i>=0;i--){
int mask=(1<< i);
if(flag)
{
if((n & mask)!=0)
{
System.out.print(1);
}
else
{
System.out.print(0);
}
}
else
{
if((n & mask)!=0)
{
flag=true;
System.out.print(1);
}
else
{
}
}
}
}
}
java;
true";
So, we have finished one part of the question. Now, let us discuss the other part where we have to reverse the bits and then print the number obtained by reversing the bits.
Reversing the bits
To understand this procedure, we must understand the above procedure completely. So, you are requested to go through the above procedure once more so that you can understand this procedure simultaneously.
See, when we get at the set bit for the first time in the number, we will set the 0thbit of a number which was initialized to 0.
So, we will keep on doing this and we will get the number with reverse bits. Now, here is a question for you. How will we set the jth bit of this number that we have taken?
Yes, we will have to take a mask. We have already studied how to set, unset and check a bit in BASICS OF BIT MANIPULATION VIDEO. We highly recommend you watch it to get your basics clear. So, what mask will we make? Our mask will have 1 at the jth position in it and we will take the OR of our number with the mask. This is shown in the figure below:
Also, remember one thing that we have set the 0th bit of this reverse number that we are calculating when we got the first set bit of the number N. After this, if we get the next bit as 0, we will not do anything with the reverse number, just move j one position forward.
So, dear reader, we hope that you have understood the above process completely too. If you have any doubts regarding this, refer to the solution video to clear all your doubts and understand the code below completely.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
boolean flag = false;
int rev=0;
int j=0;
for(int i = 31;i>=0;i--){
int mask=(1<< i);
if(flag)
{
if((n & mask)!=0)
{
System.out.print(1);
int smask=(1<< j);
rev|=smask;
}
else
{
System.out.print(0);
}
j++;
}
else
{
if((n & mask)!=0)
{
flag=true;
System.out.print(1);
int smask=(1<< j);
rev |=smask;
j++;
}
else
{
}
}
}
System.out.println();
System.out.println(rev);
}
}
java;
true";
Now that we have understood the entire procedure and the code, let us analyze the time and space complexity.
Analysis
Time Complexity:
The time complexity of the above solution is O(n) where n is the number of bits in an integer i.e. 32 since the loop is executing that many times.
Space Complexity:
The space complexity of the above solution is O(1) as we have not used any extra memory.
So, dear reader, we hope that you have got the complete procedure. If you still have any doubts, refer to the complete solution video to clear all your doubts. With this, we have completed this problem.
Suggestions:
Here are a few suggestions from our side that you do not want to miss:
Most of the things discussed in this problem could have been done by anyone if he/she had already watched the INTRODUCTION TO BIT MANIPULATION video. Not only this, all the questions in the portal of not just bit manipulation, but of any topic are arranged in such a way that they are inter-related to one another and you will be able to get the maximum output only if you solve all the problems in a sequence in continuation. We suggest that you maintain the sequence of these problems and stay consistent in problem-solving. You will be able to complete all the problems surely and with a deep understanding of every topic. So, keep practicing and moving forward. Till then, Happy Coding!!
