Smallest Number With All Set Bits

Smallest Number With All Set Bits

What is this problem about?

The "Smallest Number With All Set Bits" interview question is a bitwise challenge. You are given an integer n. You need to find the smallest integer x such that x >= n and the binary representation of x consists only of set bits (1s). For example, numbers with all set bits are 1 (1), 3 (11), 7 (111), 15 (1111), and so on. This "Smallest Number With All Set Bits coding problem" is about finding the smallest "Mersenne-like" number that covers n.

Why is this asked in interviews?

Companies like Microsoft ask this to check if a candidate understands how binary numbers are structured. It tests your ability to manipulate bits or use logarithmic properties to find the "next power of 2 minus 1". It's an "EASY" problem but requires a solid grasp of bitwise logic.

Algorithmic pattern used

This problem follows the "Math and Bit Manipulation interview pattern". There are two main ways to solve it:

1. Iterative: Start with x = 1. While x < n, shift x left and add 1 (e.g., x = (x << 1) | 1).
2. Bit Masking: Find the position of the most significant bit (MSB) of n. Create a mask that has 1s from that position down to the 0th bit. Both approaches effectively find the smallest value 2^k - 1 that is greater than or equal to n.

Example explanation

Let n = 10.

1. Binary of 10 is 1010.
2. The most significant bit is at position 3 (value 8).
3. We need a number with 4 bits, all set to 1: 1111.
4. 1111 in decimal is 15. Result: 15. Check: 15 >= 10 and all bits are set. The next smaller such number is 7, but 7 < 10.

Common mistakes candidates make

A frequent mistake is overcomplicating the logic with loops that check every number between n and 2n. While that works, bitwise operations are much faster and more idiomatic. Another mistake is not correctly handling the case where n already has all set bits (the answer should be n itself).

Interview preparation tip

To quickly find a number with all bits set that is greater than or equal to n, you can use the bit-smearing trick: n |= n >> 1; n |= n >> 2; n |= n >> 4; .... This fills all bits to the right of the MSB with 1s. This is a classic bitwise optimization used in many "Smallest Number With All Set Bits interview question" contexts.