Reverse Bits

Moderate
0/80
393 upvotes
Asked in companies
GrofersMicrosoftChegg Inc.

Problem statement

There is a song concert going to happen in the city. The price of each ticket is equal to the number obtained after reversing the bits of a given 32 bits unsigned integer ‘n’.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains a single unsigned integer ‘N’ whose bits are to be reversed.
Output Format : 
For each test case, print the number obtained after reversing the bits.

Print the output for each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
2
0
12
Sample Output 1:
 0
 805306368
Explanation For Sample Input 1 :
For the first test case :
Since the given number N = 0 is represented as 00000000000000000000000000000000 in its binary representation. So after reversing the bits, it will become 00000000000000000000000000000000 which is equal to 0 only. So the output is 0.     



For the second test case :
Since the given number N = 12 is represented as 00000000000000000000000000001100 in its binary representation. So after reversing the bits, it will become 0110000000000000000000000000000, which is equal to 805306368 only. So the output is 805306368.
Sample Input 2 :
2
6
4
Sample Output 2 :
 1610612736
 536870912
Explanation For Sample Input 1 :
For the first test case :
Since the given number N = 6 is represented as 00000000000000000000000000000110 in its binary representation. So after reversing the bits, it will become 01100000000000000000000000000000, which is equal to 1610612736.


For the second test case :
Since the given number N = 4 is represented as 00000000000000000000000000000100 in its binary representation. So after reversing the bits, it will become 0010000000000000000000000000000, which is equal to 536870912 only.
Expected time complexity:
The expected time complexity is O(log(n)).
Constraints :
1 <= T <= 10
0 <= N <= 2^32

Time Limit: 1 sec
Hint

Swap the leftmost and the rightmost bits of the given number.

Approaches (2)
Reversing the bits representation

Approach:

  • Since we are given a 32-bit  integer, reversing the bits can take place by iterating over 16 bits from least significant to most significant bits.
  • We will find the ith rightmost bit and the (31- i)th leftmost bit in each iteration and swap these two bits.

 

Algorithm:

  • Store the bits representation of ‘N’ into an array.
  • Create a variable ‘i’ = 0 to iterate through 16 bits of given integer ‘N’.
  • Now iterate through 16 bits and, in each iteration, perform the following operations:
    • Find the ith bit of the given integer.
    • Find the (31 - i)th bit of the given integer
    • Swap both these two bits.
    • Increment the ‘i’ by one.
  • Change this bits representation into an unsigned integer.
  • Finally, return the answer,which now will be modified.
Time Complexity

O(1).


Since we iterate over 16 bits only, which will take constant time. So the overall time complexity will be O(1).

Space Complexity

O(1).


Since constant space is being used. So overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Reverse Bits
Full screen
Console