Print Binary And Reverse Bits
1. You are given a number.Input Format
2. You have to print its binary representation.
3. You also have to reverse the bits of n and print the number obtained after reversing the bits.
A number nOutput Format
Check the sample ouput and question video.Question Video
1 <= n <= 10^9Sample Input
11Sample Output
1011
13
-
Editorial
The problem here is divided into two parts:
1. Given an integer, print its binary representation.
2. Given an integer, reverse its bits and print the number thus formed.
Let us take an example:
N = 11
Binary Representation = 1 0 1 1 [Print]
Reverse Bits = 1 1 0 1
New Number formed = 13 [Print]
To print the binary representation, we can traverse every bit starting from 31st position upto 0th position (as Integer is of 4 bytes) and we can print the binary values. Here we need to remove the redundant zeroes which occur before the first set bit like for 11 we only need to print 1011 instead of 00000000000000000000000000001011. So for that we will be checking for the first set bit and only after the first set bit we will start printing data as it is present in the integer.
Now to get the reverse bits, it implies that the LSB of the current number shall be the MSB of the new number and so on. We will iterate over a loop till N becomes 0 and for every iteration we will push the LSB of the remaining number to the new number and left shift the new number. This left shift ensures that every time we add a new bit to the new number it always adds at the LSB position hence at the end we get a number which has reversed bits. Also in each iteration we right shift the remaining number, this is done to always be able to access the next LSB of the number.
Time Complexity: O(k)
The time complexity for the function is proportional to the length of its binary representation. In case of integer value k<=32.
Space Complexity: O(n)
The space complexity for the function is constant.
-
Asked in Companies
-
Related Topics