[LeetCode] Smallest Number With All Set Bits

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:

Input: n = 5
Output: 7
Explanation: 
The binary representation of 7 is "111".

Input: n = 10
Output: 15
Explanation: 
The binary representation of 15 is "1111".

Input: n = 3
Output: 3
Explanation: 
The binary representation of 3 is "11".

Approach: One simple way to think about it is we just need to get the number of bits requird to (like 5 is 000...0101 so number of bits are 3 in number 5) represent the current number and get to the number which is having same number of bits with all the bits set.

To get the number of bits, we can simply take the log base 2 of the given number. Say the result is b so the result will be 2^b - 1.

Now say we are not given the log method and also we want to make it more performant using biwise operations. 

Key is if the a number has all the bits set then n & (n + 1) will be 0 so what we just need to do is keep setting the unset bit set using n | (n + 1) till we get n & (n + 1) is 0.

Question is how n | (n + 1) will set the bit.? It's because adding 1 to a number will always set the first unset bit so if we OR with the original number, we are setting the next unset bit in the original number.

Implementation in C#:

Approach 1: Using Log2:

    public int SmallestNumber(int n)

    {

        int numBits = (int)Math.Floor(Math.Log2(n)) + 1;

        return ((int)Math.Pow(2, numBits)) - 1;

    }

Approach 2: Using Bitwise operators:

    public int SmallestNumber(int n)

    {

        while ((n & (n + 1)) != 0)

        {

            n |= (n + 1);

        }

        return n;

    }

Complexity: O(logn)