Last Updated: 23 Aug, 2021
Reverse Bits
Moderate
Asked in companies
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’.
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.
Approaches
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.
Approach:
- It is a brute force approach where we iterate over all the bits from rightmost bit to leftmost bit.
- In this approach, we will create a new variable ANS to store the integer formed after reversing the bits of actual integer N. Then, for each extracted bit from N, we will add it to ‘ANS’.
Algorithm:
- Create an unsigned integer ANS initialized it to 0 to store the answer.
- Iterate over all the bits of the given N from right to left, and in each iteration, perform the following operations:
- Extract the rightmost bit say K.
- Add the extracted bit K to the ANS.
- And then shift one bit to the left to extract the next bit.
- Then finally return ANS as our required answer.
Similar problems