Find MSB — Asked in Ola Interview

Problem Statement :

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.

Can you solve this in constant time and space complexity?

Sample Input:

22

Sample Output:

16

Explanation of Sample Test Case:

The nearest integer that is less than or equal to 22 and also is a power of two is 16.

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:

1. ’N’ = ’N’ | ’N’ >> 1.
2. ’N’ = ’N’ | ’N’ >> 2.
3. ’N’ = ’N’ | ’N’ >> 4.
4. ’N’ = ’N’ | ’N’ >> 8.
5. ’N’ = ’N’ | ’N’ >> 16.
6. ’N’ = ’N’ + 1.
7. Return, (’N’ >> 1).

Time Complexity : O(1)
Space Complexity : O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.