Smallest Number With All Set Bits - Solution & Explanation

Problem Overview: You are given an integer n. The task is to return the smallest number greater than or equal to n whose binary representation consists entirely of set bits (all 1s). Numbers like 1 (1), 3 (11), 7 (111), and 15 (1111) satisfy this property.

Approach 1: Iterative Incremental Approach (Time: O(ans - n), Space: O(1))

Start from n and keep incrementing the value until you find a number whose binary representation contains only set bits. A useful bit trick identifies such numbers: a value with all bits set satisfies x & (x + 1) == 0. This works because numbers like 111...111 become a power of two when incremented, which clears all lower bits. Iterate until the condition holds, then return that number. This approach is straightforward and easy to reason about, though in the worst case you may check several numbers before reaching the next valid one.

Approach 2: Bit Manipulation - Direct Calculation (Time: O(1), Space: O(1))

All numbers with every bit set follow the pattern 2^k - 1. The goal is to find the smallest such value that is greater than or equal to n. Observe that 2^k - 1 ≥ n when k ≥ ceil(log2(n + 1)). Compute k from the bit length of n, then return (1 << k) - 1. This avoids iteration entirely and directly constructs the correct number using bit shifts. The approach relies on patterns in binary representation and is a classic use of bit manipulation combined with simple math reasoning.

Recommended for interviews: The direct bit manipulation approach is what most interviewers expect. It demonstrates recognition of the 2^k - 1 pattern and comfort with binary operations. The iterative approach still helps show understanding of the property x & (x + 1) == 0, which is a common trick in bit manipulation problems.