Last Updated: 26 Jan, 2021
Find MSB In O(1)
Easy
Asked in company
You are given a positive integer 'N'. Your task is to find the greatest integer less than or equal to 'N' which is a power of 2.
For Example:
If N = 14, then the nearest integer that is less than or equal to 14 and is a power of two is 8(2^3). So, the answer is 8.
Follow Up:
Can you solve this in constant time and space complexity?
Input format:
The first line contains an integer 'T' which denotes the number of test cases. Then, the 'T' test cases area as follow.
The first and only line of each test case contains a single integer 'N'.
Output format:
For each test case, print the nearest integer that is less than or equal to 'N' and also is a power of 2.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 2 * 10^3
1 <= N <= 10^9
Time Limit: 1 second
Approaches
The Algorithm is as follows:
- Create an ‘ANS’ variable and initialize it to 1.
- While ‘N’ != 1, do:
- ‘N’ = ‘N’ / 2.
- ‘ANS’ = ‘ANS’ * 2.
- Finally, return ‘ANS’.
The Algorithm is as follows:
- Create an integer ‘X’ and make ‘X’ = (int) log2(‘N’).
- Then, return (int) pow(2, ‘X’). Note that, we need to do the typecasting in both the steps, as both the log and pow function returns a double value in C++.
Approach: When the size of the integer is fixed (32 bits in this case), we can try to set all the bits of N by making bitwise OR operations after performing logical right shift operations (>>).
Logical right shift (>>) operation takes two numbers such as a >> b. Then it shifts the bits of a to b places towards the right. For example, if a = 11 and b = 1, then the binary representation of a is 1011. So after performing a >> b, all the bits of a are shifted one bit towards the right and the MSB(Most Significant Bit) is filled with 0. So, now a becomes 0101, and the decimal value is 5.
Now let’s understand the algorithm by taking N = 256. So, the binary representation of N is 100000000. We can make N = N | N >> 1. Now N = 384 and the binary representation is 110000000. So, by doing the above step, we are making sure that 2 bits from MSB including the MSB are set.
Then we will make N = N | N >> 2. Now, N = 480 and the binary representation is 111100000. So, 4 bits from MSB will be set.
Similarly, we will do N = N | N >> 4 and 8 bits from MSB will be set. After N = N | N >> 8, 16 bits from MSB will be set. And finally, after N = N | N >> 16, all the bits from the MSB will be set. Note that, if the number of bits of a number is less than 16, then the step N = N | N >> 16, doesn’t change anything.
So, now all the bits of N are set. Now increase N by 1, so that only the bit just before the original bit is set. For example, if N = 7, the binary representation of N is 111. If we increase N by 1, then N becomes 8 and the binary representation is 1000. So, the bit just before the original bit is set. Finally, right shift N by 1 and return the answer.
The Algorithm is as follows:
- ‘N’ = ‘N’ | ‘N’ >> 1.
- ‘N’ = ‘N’ | ‘N’ >> 2.
- ‘N’ = ‘N’ | ‘N’ >> 4.
- ‘N’ = ‘N’ | ‘N’ >> 8.
- ‘N’ = ‘N’ | ‘N’ >> 16.
- ‘N’ = ‘N’ + 1.
- Return, (‘N’ >> 1).