Cuente números hasta N con el bit K-ésimo establecido

Dados dos números enteros N y K, la tarea es encontrar el conteo de números hasta N con el bit K-ésimo establecido.

Ejemplos:

Entrada: N = 14, K = 2
Salida: 7
Explicación: 
Los números menores que iguales a 14, que tienen el segundo ^bit establecido, son 4, 5, 6, 7, 12, 13 y 14.

Entrada: N = 6, K = 1
Salida: 3
Explicación : 
Los números menores que 6 que tienen el ^1er bit establecido son 1, 3, 5.

Enfoque ingenuo: el enfoque más simple es atravesar de 1 a N y verificar para cada número si su k-ésimo bit está configurado o no.

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

Enfoque eficiente: el enfoque anterior se puede optimizar dividiendo la tarea en dos partes:

1. Primero, desplazar a la derecha N , K+1 veces, seguido de desplazar a la izquierda el resultado K veces, lo que da el recuento de números que satisfacen la condición dada hasta la potencia de 2 menor que N más cercana .
2. Ahora, verifique si el K ^-ésimo bit está configurado en N o no.
3. Si el K ^-ésimo bit está establecido en N, entonces agregue la cuenta de números desde la potencia de 2 más cercana menor que N a la respuesta.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of number of 1's at ith bit
// in a range [1, n - 1]
long long getcount(long long n, int k)
{
    // Store count till nearest
    // power of 2 less than N
    long long res = (n >> (k + 1)) << k;
 
    // If K-th bit is set in N
    if ((n >> k) & 1)
 
        // Add to result the nearest
        // power of 2 less than N
        res += n & ((1ll << k) - 1);
 
    // Return result
    return res;
}
 
// Driver Code
int main()
{
 
    long long int N = 14;
    int K = 2;
 
    // Function Call
    cout << getcount(N + 1, K) << endl;
 
    return 0;
}

// Java program for above approach
class GFG
{
 
  // Function to return the count
  // of number of 1's at ith bit
  // in a range [1, n - 1]
  static long getcount(long n, int k)
  {
 
    // Store count till nearest
    // power of 2 less than N
    long res = (n >> (k + 1)) << k;
 
    // If K-th bit is set in N
    if (((n >> k) & 1) != 0)
 
      // Add to result the nearest
      // power of 2 less than N
      res += n & ((1 << k) - 1);
 
    // Return result
    return res;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    long N = 14;
    int K = 2;
 
    // Function Call
    System.out.println(getcount(N + 1, K));
  }
}
 
// This code is contributed by divyesh072019

# Python3 program for above approach
 
# Function to return the count
# of number of 1's at ith bit
# in a range [1, n - 1]
def getcount(n, k):
     
    # Store count till nearest
    # power of 2 less than N
    res = (n >> (k + 1)) << k
 
    # If K-th bit is set in N
    if ((n >> k) & 1):
         
        # Add to result the nearest
        # power of 2 less than N
        res += n & ((1 << k) - 1)
 
    # Return result
    return res
 
# Driver Code
if __name__ == '__main__':
 
    N = 14
    K = 2
 
    # Function Call
    print (getcount(N + 1, K))
 
# This code is contributed by mohit kumar 29

// C# program for above approach
using System;
 
class GFG{
 
// Function to return the count
// of number of 1's at ith bit
// in a range [1, n - 1]
static long getcount(long n, int k)
{
     
    // Store count till nearest
    // power of 2 less than N
    long res = (n >> (k + 1)) << k;
     
    // If K-th bit is set in N
    if (((n >> k) & 1) != 0)
     
        // Add to result the nearest
        // power of 2 less than N
        res += n & ((1 << k) - 1);
     
    // Return result
    return res;
}
 
// Driver Code 
static void Main()
{
    long N = 14;
    int K = 2;
     
    // Function Call
    Console.WriteLine(getcount(N + 1, K));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
    // Javascript program for above approach
     
    // Function to return the count
    // of number of 1's at ith bit
    // in a range [1, n - 1]
    function getcount(n, k)
    {
 
        // Store count till nearest
        // power of 2 less than N
        let res = (n >> (k + 1)) << k;
 
        // If K-th bit is set in N
        if (((n >> k) & 1) != 0)
 
            // Add to result the nearest
            // power of 2 less than N
            res += n & ((1 << k) - 1);
 
        // Return result
        return res;
    }
     
    let N = 14;
    let K = 2;
      
    // Function Call
    document.write(getcount(N + 1, K));
   
</script>

7

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)