# Smallest Number With All Set Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/smallest-number-with-all-set-bits)
Canonical: https://scaleengineer.com/dsa/problems/smallest-number-with-all-set-bits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
You are given a _positive_ number `n`.

Return the **smallest** number `x` **greater than** or **equal to** `n`, such that the binary representation of `x` contains only set bits

**Example 1:**

**Input:** n = 5

**Output:** 7

**Explanation:**

The binary representation of 7 is `"111"`.

**Example 2:**

**Input:** n = 10

**Output:** 15

**Explanation:**

The binary representation of 15 is `"1111"`.

**Example 3:**

**Input:** n = 3

**Output:** 3

**Explanation:**

The binary representation of 3 is `"11"`.

**Constraints:**

* `1 <= n <= 1000`

# Approaches
## Brute Force Iteration
This approach involves checking every number starting from `n` until we find one whose binary representation consists solely of set bits (1s).
**Time:** O(M - n), where `M` is the smallest number with all set bits that is greater than or equal to `n`. In the worst case, `n` could be `2^k`, and `M` would be `2^(k+1) - 1`. The number of iterations would be `2^k - 1`, which is roughly `n`. So, the complexity is approximately O(n). · **Space:** O(1), as we only use a constant amount of extra space.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large `n`, especially when `n` is just slightly larger than a number with all set bits (e.g., `n = 2^k`). The number of iterations can be proportional to `n`.
### Explanation
We start a loop with a variable `x` initialized to `n`. In each iteration, we check if `x` is a number with all bits set. A number `y` has all its bits set if it is of the form `2^k - 1`. A clever bitwise trick to check this condition is `(y & (y + 1)) == 0`. This works because adding 1 to a number composed of all 1s (like `...0111`) results in a number that is a power of two (`...1000`), and the bitwise AND of these two numbers will be zero. If the condition is met, we have found our smallest number `x >= n` and we return it. If the condition is not met, we increment `x` by 1 and continue the loop. The loop is guaranteed to terminate because the sequence of numbers with all set bits is infinite (1, 3, 7, 15, ...), so we will eventually find one.

```java
class Solution {
    public int smallestNumberWithAllSetBits(int n) {
        int x = n;
        while (true) {
            // A number has all set bits if (x & (x + 1)) == 0
            // Example: x = 7 (0111), x + 1 = 8 (1000). 7 & 8 = 0.
            // This check is valid for x > 0.
            if ((x & (x + 1)) == 0) {
                return x;
            }
            x++;
        }
    }
}
```
### Algorithm
- Start a loop with a variable `x` initialized to `n`.
- In each iteration, check if `x` is a number with all bits set. A number `y` has all its bits set if it is of the form `2^k - 1`. A clever bitwise trick to check this condition is `(y & (y + 1)) == 0`.
- If the condition is met, we have found our smallest number `x >= n` and we return it.
- If the condition is not met, we increment `x` by 1 and continue the loop.

## Constructive Generation of Candidates
Instead of checking every number from `n` upwards, we can generate only the numbers that have all set bits and find the first one that is greater than or equal to `n`.
**Time:** O(log n). The number of iterations is equal to the number of bits in the final result. Since the result is the smallest number of the form `2^k-1` greater than or equal to `n`, its number of bits `k` is proportional to `log n`. · **Space:** O(1). We only use a single variable to store the candidate.
**Pros:** Very efficient, with logarithmic time complexity.
**Cons:** Requires recognizing the pattern of the target numbers.
### Explanation
The numbers with all set bits follow a clear pattern: 1 (binary `1`), 3 (binary `11`), 7 (binary `111`), 15 (binary `1111`), and so on. Each subsequent number in this sequence can be generated from the previous one. If `c` is a number with all set bits, the next one is `(c * 2) + 1`, or using bitwise operations, `(c << 1) | 1`. The algorithm starts with the first number in the sequence, `candidate = 1`. It then enters a loop, and in each iteration, it checks if the `candidate` is less than `n`. If `candidate < n`, it generates the next number in the sequence: `candidate = (candidate << 1) | 1`. The loop continues until `candidate` is no longer less than `n`. At this point, `candidate` is the smallest number with all set bits that is greater than or equal to `n`. Finally, we return the `candidate`.

```java
class Solution {
    public int smallestNumberWithAllSetBits(int n) {
        // Start with the first number with all set bits, which is 1.
        long candidate = 1;
        
        // Keep generating the next number with all set bits
        // until it is greater than or equal to n.
        while (candidate < n) {
            // The next number is generated by shifting left by 1 and setting the new LSB.
            // e.g., from 7 (111) to 15 (1111)
            candidate = (candidate << 1) | 1;
        }
        
        return (int)candidate;
    }
}
```
### Algorithm
- The numbers with all set bits follow a pattern: 1, 3, 7, 15, etc.
- Each subsequent number `c_next` can be generated from the previous one `c_prev` by `c_next = (c_prev << 1) | 1`.
- Start with a `candidate = 1`.
- In a loop, while `candidate < n`, update the candidate to the next number in the sequence.
- When the loop terminates, `candidate` will be the smallest number with all set bits that is greater than or equal to `n`.

## Bit Manipulation and Direct Calculation
This is the most efficient approach. It directly calculates the result by determining the required number of bits and constructing the number in a single step.
**Time:** O(log n) for the loop-based bit counting. If using a hardware instruction like `clz` (count leading zeros), which `Integer.numberOfLeadingZeros` often maps to, the complexity is effectively O(1). · **Space:** O(1).
**Pros:** Most efficient and elegant solution.; Directly computes the answer without iteration or searching.
**Cons:** Might be slightly less intuitive than the constructive generation approach for beginners.
### Explanation
The problem asks for the smallest number `x` of the form `2^k - 1` such that `x >= n`. Let's analyze the relationship between `n` and the result `x`. If `n` has `b` bits in its binary representation, the smallest number with all `b` bits set is `2^b - 1`. Any number with fewer than `b` bits will be smaller than `n` (since `n`'s most significant bit is at position `b-1`). The number `2^b - 1` is the largest possible number with `b` bits. Therefore, `n <= 2^b - 1`. This means the smallest number with all set bits that is greater than or equal to `n` must have at least `b` bits. The smallest such number is exactly `2^b - 1`. So, the algorithm simplifies to these steps:
1. Find the number of bits, `b`, in the binary representation of `n`.
2. The result is `(1 << b) - 1`.
The number of bits can be found efficiently. For a 32-bit integer, `32 - Integer.numberOfLeadingZeros(n)` gives the bit length. Alternatively, a simple loop that repeatedly right-shifts `n` until it becomes zero can count the bits.

```java
class Solution {
    public int smallestNumberWithAllSetBits(int n) {
        // Find the number of bits in n.
        // For n=5 (101), bits=3. For n=10 (1010), bits=4.
        int bits = 0;
        int temp = n;
        while (temp > 0) {
            temp >>= 1;
            bits++;
        }
        
        // The result is a number with 'bits' number of 1s.
        // This can be calculated as (1 << bits) - 1.
        // For bits=3, (1 << 3) - 1 = 8 - 1 = 7 (111).
        // For bits=4, (1 << 4) - 1 = 16 - 1 = 15 (1111).
        return (1 << bits) - 1;
    }
}
```
### Algorithm
- The goal is to find the smallest number `x` of the form `2^k - 1` such that `x >= n`.
- Let `b` be the number of bits in the binary representation of `n`.
- The smallest number with all set bits that is `>= n` must have at least `b` bits.
- The smallest number with `b` bits that are all set is `2^b - 1`.
- This number `2^b - 1` is also the largest number with `b` bits, so `n <= 2^b - 1` is always true.
- Therefore, the answer is always `2^b - 1`.
- The algorithm is: 
  1. Find the number of bits, `b`, in `n`.
  2. Calculate and return `(1 << b) - 1`.

# Solutions
### Java

```java
class Solution {
public
  int smallestNumber(int n) {
    int x = 1;
    while (x - 1 < n) {
      x <<= 1;
    }
    return x - 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int smallestNumber(int n) {
    int x = 1;
    while (x - 1 < n) {
      x <<= 1;
    }
    return x - 1;
  }
};

```

### Python

```python
class Solution:
    def smallestNumber(self, n: int) -> int: x = 1 while x - 1 < n: x <<= 1 return x - 1

```