El número más pequeño que excede N cuyo bit Kth está establecido

Dados dos números enteros N y K , la tarea es encontrar el número más pequeño mayor que N cuyo K ^-ésimo bit en su representación binaria esté establecido.

Ejemplos:

Entrada: N = 15, K = 2
Salida: 20
Explicación:
La representación binaria de (20) ₁₀ es (10100) ₂ . El segundo ^bit ( indexación basada en 0 ) desde la izquierda se establece en (20) ₁₀ . Por lo tanto, 20 es el número más pequeño mayor que 15 que tiene el segundo ^bit establecido.

Entrada: N = 16, K = 3
Salida: 24 
 

Enfoque ingenuo: el enfoque más simple es recorrer todos los números a partir de N + 1 y, para cada número, verificar si su K ^-ésimo bit está configurado o no. Si se encuentra dicho número, entonces imprima ese número.

A continuación se muestra la implementación del enfoque anterior:

// 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;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to find the number greater
// than n whose Kth bit is set
static int find_next(int n, int k)
{
  // Iterate from N + 1
  int M = n + 1;
 
  while (true)
  {
    // Check if Kth bit is
    // set or not
    if ((M & (1L << k)) > 0)
      break;
 
    // Increment M for
    // next number
    M++;
  }
 
  // Return the minimum value
  return M;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given N and K
  int N = 15, K = 2;
 
  // Function Call
  System.out.print(find_next(N, K));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for
# the above approach
 
# Function to find the number
# greater than n whose Kth
# bit is set
def find_next(n, k):
   
    # Iterate from N + 1
    M = n + 1;
 
    while (True):
       
        # Check if Kth bit is
        # set or not
        if ((M & (1 << k)) > 0):
            break;
 
        # Increment M for
        # next number
        M += 1;
 
    # Return the
    # minimum value
    return M;
 
# Driver Code
if __name__ == '__main__':
   
    # Given N and K
    N = 15; K = 2;
 
    # Function Call
    print(find_next(N, K));
 
# This code is contributed by Rajput-Ji

// C# program for
// the above approach
using System;
class GFG{
 
// Function to find the
// number greater than n
// whose Kth bit is set
static int find_next(int n, int k)
{
  // Iterate from N + 1
  int M = n + 1;
 
  while (true)
  {
    // Check if Kth bit is
    // set or not
    if ((M & (1L << k)) > 0)
      break;
 
    // Increment M for
    // next number
    M++;
  }
 
  // Return the minimum value
  return M;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given N and K
  int N = 15, K = 2;
 
  // Function Call
  Console.Write(find_next(N, K));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to implement
// the above approach
     
 // Function to find the number greater
// than n whose Kth bit is set
function find_next(n, k)
{
  // Iterate from N + 1
  let M = n + 1;
  
  while (true)
  {
    // Check if Kth bit is
    // set or not
    if ((M & (1 << k)) > 0)
      break;
  
    // Increment M for
    // next number
    M++;
  }
  
  // Return the minimum value
  return M;
}
 
// Driver Code
  
     // Given N and K
  let N =  15, K = 2;
  
  // Function Call
  document.write(find_next(N, K));
  
 // This code is contributed by avijitmondal1998.
</script>

20

Tiempo Complejidad: O(2 ^K )
Espacio Auxiliar: O(1)

Enfoque Eficiente: Para optimizar el enfoque anterior, existen dos posibilidades:

1. K ^-ésimo bit no está establecido: observe que los bits que tienen posiciones mayores que K no se verán afectados. Por lo tanto, establezca el K ^-ésimo bit y haga que todos los bits a su izquierda sean 0 .
2. Se establece el k ^-ésimo bit: encuentre el primer bit no establecido menos significativo y configúrelo. Después de eso, desarma todos los bits que están a su derecha.

Siga los pasos a continuación para resolver el problema:

1. Compruebe si el K ^-ésimo bit de N está establecido. Si se determina que es cierto, busque el bit más bajo no configurado y configúrelo y cambie todos los bits a su derecha a 0 .
2. De lo contrario, establezca el K ^-ésimo bit y actualice todos los bits ubicados por debajo de K a 0 .
3. Imprima la respuesta después de completar los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

// 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;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to find the number
// greater than n whose Kth
// bit is set
static int find_next(int n,
                     int k)
{
  // Stores the resultant
  // number
  int ans = 0;
 
  // If Kth bit is not set
  if ((n & (1L << 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 & (1L << i)) > 0)
        cur += 1L << i;
    }
 
    // Add Kth power of 2 to n and
    // subtract the all powers of 2
    // less than K that are set
    ans = (int)(n - cur + (1L << 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 & (1L << i)) == 0)
      {
        first_unset_bit = i;
        break;
      }
 
      // sum of bits that are set
      else
        cur += (1L << i);
    }
 
    // Add Kth power of 2 to n and
    // subtract the all powers of 2
    // less than K that are set
    ans = (int)(n - cur +
          (1L << first_unset_bit));
 
    // If Kth bit became unset
    // then set it again
    if ((ans & (1L << k)) == 0)
      ans += (1L << k);
  }
 
  // Return the resultant number
  return ans;
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 15, K = 2;
 
  // Print ans
  System.out.print(find_next(N, K));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to find the number greater
# than n whose Kth bit is set
def find_next(n, k):
 
    # Stores the resultant number
    ans = 0
     
    # If Kth bit is not set
    if ((n & (1 << k)) == 0):
        cur = 0
 
        # cur will be the sum of all
        # powers of 2 < k
        for i in range(k):
 
            # If the current bit is set
            if (n & (1 << i)):
                cur += 1 << i
 
        # Add Kth power of 2 to n and
        # subtract the all powers of 2
        # less than K that are set
        ans = n - cur + (1 << k)
 
    # If the kth bit is set
    else:
        first_unset_bit, cur = -1, 0
 
        for i in range(64):
 
            # First unset bit position
            if ((n & (1 << i)) == 0):
                first_unset_bit = i
                break
 
            # Sum of bits that are set
            else:
                cur += (1 << i)
 
        # Add Kth power of 2 to n and
        # subtract the all powers of 2
        # less than K that are set
        ans = n - cur + (1 << first_unset_bit)
 
        # If Kth bit became unset
        # then set it again
        if ((ans & (1 << k)) == 0):
            ans += (1 << k)
 
    # Return the resultant number
    return ans
     
# Driver code
N, K = 15, 2
 
# Print ans
print(find_next(N, K))
 
# This code is contributed by divyeshrabadiya07

// C# program for
// the above approach
using System;
class GFG{
 
// Function to find the number
// greater than n whose Kth
// bit is set
static int find_next(int n,
                     int k)
{
  // Stores the resultant
  // number
  int ans = 0;
 
  // If Kth bit is not set
  if ((n & (1L << 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 & (1L << i)) > 0)
        cur += (int)1L << i;
    }
 
    // Add Kth power of 2 to n and
    // subtract the all powers of 2
    // less than K that are set
    ans = (int)(n - cur + (1L << 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 & (1L << i)) == 0)
      {
        first_unset_bit = i;
        break;
      }
 
      // Sum of bits that are set
      else
        cur +=(int)(1L << i);
    }
 
    // Add Kth power of 2 to n and
    // subtract the all powers of 2
    // less than K that are set
    ans = (int)(n - cur +
          (1L << first_unset_bit));
 
    // If Kth bit became unset
    // then set it again
    if ((ans & (1L << k)) == 0)
      ans += (int)(1L << k);
  }
 
  // Return the resultant number
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 15, K = 2;
 
  // Print ans
  Console.Write(find_next(N, K));
}
}
 
// This code is contributed by Rajput-Ji

<script>
// javascript program for
// the above approach
 
    // Function to find the number
    // greater than n whose Kth
    // bit is set
    function find_next(n , k) {
        // Stores the resultant
        // number
        var ans = 0;
 
        // If Kth bit is not set
        if ((n & (1 << k)) == 0) {
            var cur = 0;
 
            // cur will be the sum of all
            // powers of 2 < k
            for (i = 0; i < k; i++) {
                // If the current bit is set
                if ((n & (1 << i)) > 0)
                    cur += 1 << i;
            }
 
            // Add Kth power of 2 to n and
            // subtract the all powers of 2
            // less than K that are set
            ans = parseInt( (n - cur + (1 << k)));
        }
 
        // If the kth bit is set
        else {
            var first_unset_bit = -1, cur = 0;
 
            for (i = 0; i < 64; i++) {
                // First unset bit position
                if ((n & (1 << i)) == 0) {
                    first_unset_bit = i;
                    break;
                }
 
                // sum of bits that are set
                else
                    cur += (1 << i);
            }
 
            // Add Kth power of 2 to n and
            // subtract the all powers of 2
            // less than K that are set
            ans = parseInt( (n - cur + (1 << first_unset_bit)));
 
            // If Kth bit became unset
            // then set it again
            if ((ans & (1 << k)) == 0)
                ans += (1 << k);
        }
 
        // Return the resultant number
        return ans;
    }
 
    // Driver Code
     
        var N = 15, K = 2;
 
        // Print ans
        document.write(find_next(N, K));
         
// This code is contributed by umadevi9616
</script>

20

Complejidad temporal: O(K)
Espacio auxiliar: O(1)