Smallest number exceeding N whose Kth bit is set

Given two integers N and K, the task is to find the smallest number greater than N whose Kth bit in its binary representation is set.

Examples:

Input: N = 15, K = 2

Output: 20

Explanation:

The binary representation of (20)10 is (10100)2. The 2nd bit(0-based indexing) from left is set in (20)10. Therefore, 20 is the smallest number greater than 15 having 2nd bit set.

Input: N = 16, K = 3

Output: 24

Naive Approach: The simplest approach is to traverse all numbers starting from N + 1 and for each number, check if its Kth bit is set or not. If the such a number is found, then print that number.

Below is the implementation of the above approach:

// C++ program for the above approach 

  

#include "bits/stdc++.h" 

using namespace std; 

  

// Function to find the number greater 

// than n whose Kth bit is set 

int find_next(int n, int k) 

{ 

    // Iterate from N + 1 

    int M = n + 1; 

  

    while (1) { 

  

        // Check if Kth bit is 

        // set or not 

        if (M & (1ll << k)) 

            break; 

  

        // Increment M for next number 

        M++; 

    } 

  

    // Return the minimum value 

    return M; 

} 

  

// Driver Code 

int main() 

{ 

    // Given N and K 

    int N = 15, K = 2; 

  

    // Function Call 

    cout << find_next(N, K); 

  

    return 0; 

} 

Output:

20

Time Complexity: O(2K)

Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, there exists two possibilities:

Kth bit is not set: Observe that bits having positions greater than K will not be affected. Therefore, make the Kth bit set and make all bits on its left 0.

Kth bit is set: Find the first least significant unset bit and set it. After that, unset all the bits that are on its right.

Follow the steps below to solve the problem:

Check if the Kth bit of N is set. If found to be true, then find the lowest unset bit and set it and change all the bits to its right to 0.

Otherwise, set the Kth bit and update all the bits positioned lower than K to 0.

Print the answer after completing the above steps.

Below is the implementation of the above approach:

// C++ program for the above approach 

  

#include "bits/stdc++.h" 

using namespace std; 

  

// Function to find the number greater 

// than n whose Kth bit is set 

int find_next(int n, int k) 

{ 

    // Stores the resultant number 

    int ans = 0; 

  

    // If Kth bit is not set 

    if ((n & (1ll << k)) == 0) { 

        int cur = 0; 

  

        // cur will be the sum of all 

        // powers of 2 < k 

        for (int i = 0; i < k; i++) { 

  

            // If the current bit is set 

            if (n & (1ll << i)) 

                cur += 1ll << i; 

        } 

  

        // Add Kth power of 2 to n and 

        // subtract the all powers of 2 

        // less than K that are set 

        ans = n - cur + (1ll << k); 

    } 

  

    // If the kth bit is set 

    else { 

        int first_unset_bit = -1, cur = 0; 

  

        for (int i = 0; i < 64; i++) { 

  

            // First unset bit position 

            if ((n & (1ll << i)) == 0) { 

                first_unset_bit = i; 

                break; 

            } 

  

            // sum of bits that are set 

            else

                cur += (1ll << i); 

        } 

  

        // Add Kth power of 2 to n and 

        // subtract the all powers of 2 

        // less than K that are set 

        ans = n - cur 

              + (1ll << first_unset_bit); 

  

        // If Kth bit became unset 

        // then set it again 

        if ((ans & (1ll << k)) == 0) 

            ans += (1ll << k); 

    } 

  

    // Return the resultant number 

    return ans; 

} 

  

// Driver Code 

int main() 

{ 

    int N = 15, K = 2; 

  

    // Print ans 

    cout << find_next(N, K); 

  

    return 0; 

} 

Output:

20

Time Complexity: O(K)

Auxiliary Space: O(1)