Smallest Number With All Set Bits

easy bit manipulation math powers of two

Problem

You are given a positive integer n. Return the smallest number x that is greater than or equal to n whose binary representation contains only set bits (all 1s), i.e. a number of the form 2^k − 1 such as 1, 3, 7, 15, 31, …

Inputn = 5

Output7

The binary representation of 7 is "111" — the smallest all-ones number that is ≥ 5.

n (1 ≤ n ≤ 1000)

def smallestNumber(n):
    # Smallest all-ones number is 1 (binary "1").
    x = 1
    # Append a 1 bit each step (x*2 + 1) until x reaches n.
    while x < n:
        x = x * 2 + 1
    # x is now the smallest 2^k - 1 that is >= n.
    return x

function smallestNumber(n) {
  // Smallest all-ones number is 1 (binary "1").
  let x = 1;
  // Append a 1 bit each step (x*2 + 1) until x reaches n.
  while (x < n) {
    x = x * 2 + 1;
  }
  // x is now the smallest 2^k - 1 that is >= n.
  return x;
}

int smallestNumber(int n) {
    // Smallest all-ones number is 1 (binary "1").
    int x = 1;
    // Append a 1 bit each step (x*2 + 1) until x reaches n.
    while (x < n) {
        x = x * 2 + 1;
    }
    // x is now the smallest 2^k - 1 that is >= n.
    return x;
}

int smallestNumber(int n) {
    // Smallest all-ones number is 1 (binary "1").
    int x = 1;
    // Append a 1 bit each step (x*2 + 1) until x reaches n.
    while (x < n) {
        x = x * 2 + 1;
    }
    // x is now the smallest 2^k - 1 that is >= n.
    return x;
}

Explanation

A number whose binary form is all set bits looks like 111…1. Such numbers are exactly one less than a power of two: 1 = 2¹-1, 3 = 2²-1, 7 = 2³-1, 15 = 2⁴-1, and so on. So the answer is always the smallest 2^k - 1 that is at least n.

Instead of computing logarithms we simply grow the candidate. Start at x = 1 (binary "1"). Appending a 1 to the right of a binary all-ones number is the same arithmetic as x = x * 2 + 1: it shifts left by one bit and turns on the new lowest bit, taking 1 → 11 → 111 → ….

We keep appending while x < n. The moment x ≥ n, we stop — x is the first all-ones number to reach or pass n, which is precisely the smallest valid answer.

Example: n = 5. We have x = 1 (< 5), then x = 3 (< 5), then x = 7 (≥ 5) → stop and return 7 whose binary is "111". For n = 3 the loop never even runs once we hit x = 3, so the answer is 3.

Because the constraint is 1 ≤ n ≤ 1000 and each step at least doubles x, the loop runs only about log₂(n) times — at most 10 iterations.

Time: O(log n) Space: O(1)