Cuente números hasta N cuyo bit establecido más a la derecha es K

Dados dos enteros positivos N y K , la tarea es contar los números del rango [1, N] cuyo K ^-ésimo bit desde la derecha, es decir , LSB , es el bit establecido más a la derecha .

Ejemplos:

Entrada: N = 15, K = 2
Salida: 4
Explicación:
(2) ₁₀ = (010) ₂ , (6) ₁₀ = (110) ₂ , (10) ₁₀ = (1010) ₂ , (14) ₁₀ = ( 1110) ₂ tienen el segundo ^{bit de la derecha está establecido.}

Entrada: N = 10 K = 3
Salida: 3

Enfoque ingenuo: la idea es iterar sobre el rango [1, N] y para cada número en el rango, verificar si la posición del bit establecido más a la derecha es K e imprimir el recuento de dichos números. 
Complejidad temporal: O(N LogN)
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es encontrar los números con la posición del bit establecido más a la derecha en la posición i en cada paso. Siga los pasos a continuación para resolver el problema:

• Iterar sobre el rango [1, K] usando una variable, digamos i .
• Encuentre un número cuyo bit establecido más a la derecha sea i ^th .
• Resta ese número de N .
• Repita el paso anterior para todos los valores de i .

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 count the numbers in the
// range [1, N] whose rightmost set bit is K
int countNumberHavingKthBitSet(int N, int K)
{
    // Stores the number whose
    // rightmost set bit is K
    int numbers_rightmost_setbit_K;
 
    for (int i = 1; i <= K; i++) {
 
        // Numbers whose rightmost set bit is i
        int numbers_rightmost_bit_i = (N + 1) / 2;
 
        // Subtracting the number whose
        // rightmost set bit is i, from N
        N -= numbers_rightmost_bit_i;
 
        // Since i = k, then the number whose
        // rightmost set bit is K is stored
        if (i == K) {
            numbers_rightmost_setbit_K
                = numbers_rightmost_bit_i;
        }
    }
 
    cout << numbers_rightmost_setbit_K;
}
 
// Driver Code
int main()
{
    int N = 15;
    int K = 2;
    countNumberHavingKthBitSet(N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.Arrays;
class GFG
{
      
// Function to count the numbers in the
// range [1, N] whose rightmost set bit is K
static void countNumberHavingKthBitSet(int N, int K)
{
    // Stores the number whose
    // rightmost set bit is K
    int numbers_rightmost_setbit_K = 0;
    for (int i = 1; i <= K; i++)
    {
  
        // Numbers whose rightmost set bit is i
        int numbers_rightmost_bit_i = (N + 1) / 2;
  
        // Subtracting the number whose
        // rightmost set bit is i, from N
        N -= numbers_rightmost_bit_i;
  
        // Since i = k, then the number whose
        // rightmost set bit is K is stored
        if (i == K)
        {
            numbers_rightmost_setbit_K
                = numbers_rightmost_bit_i;
        }
    }
    System.out.println(numbers_rightmost_setbit_K);
}
  
// Driver Code
static public void main(String args[])
{
    int N = 15;
    int K = 2;
    countNumberHavingKthBitSet(N, K);
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
 
# Function to count the numbers in the
# range [1, N] whose rightmost set bit is K
def countNumberHavingKthBitSet(N, K):
     
    # Stores the number whose
    # rightmost set bit is K
    numbers_rightmost_setbit_K = 0
 
    for i in range(1, K + 1):
 
        # Numbers whose rightmost set bit is i
        numbers_rightmost_bit_i = (N + 1) // 2
 
        # Subtracting the number whose
        # rightmost set bit is i, from N
        N -= numbers_rightmost_bit_i
 
        # Since i = k, then the number whose
        # rightmost set bit is K is stored
        if (i == K):
            numbers_rightmost_setbit_K = numbers_rightmost_bit_i
 
    print (numbers_rightmost_setbit_K)
 
# Driver Code
if __name__ == '__main__':
    N = 15
    K = 2
    countNumberHavingKthBitSet(N, K)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG
{
 
  // Function to count the numbers in the
  // range [1, N] whose rightmost set bit is K
  static void countNumberHavingKthBitSet(int N, int K)
  {
    // Stores the number whose
    // rightmost set bit is K
    int numbers_rightmost_setbit_K = 0;
    for (int i = 1; i <= K; i++)
    {
 
      // Numbers whose rightmost set bit is i
      int numbers_rightmost_bit_i = (N + 1) / 2;
 
      // Subtracting the number whose
      // rightmost set bit is i, from N
      N -= numbers_rightmost_bit_i;
 
      // Since i = k, then the number whose
      // rightmost set bit is K is stored
      if (i == K)
      {
        numbers_rightmost_setbit_K
          = numbers_rightmost_bit_i;
      }
    }
    Console.WriteLine(numbers_rightmost_setbit_K);
  }
 
  // Driver Code
  static public void Main(String []args)
  {
    int N = 15;
    int K = 2;
    countNumberHavingKthBitSet(N, K);
  }
}
 
 
// This code is contributed by 29AjayKumar

<script>
 
// javascript program for the above approach
 
// Function to count the numbers in the
// range [1, N] whose rightmost set bit is K
function countNumberHavingKthBitSet(N, K)
{
    // Stores the number whose
    // rightmost set bit is K
    let numbers_rightmost_setbit_K = 0;
    for (let i = 1; i <= K; i++)
    {
   
        // Numbers whose rightmost set bit is i
        let numbers_rightmost_bit_i = (N + 1) / 2;
   
        // Subtracting the number whose
        // rightmost set bit is i, from N
        N -= numbers_rightmost_bit_i;
   
        // Since i = k, then the number whose
        // rightmost set bit is K is stored
        if (i == K)
        {
            numbers_rightmost_setbit_K
                = numbers_rightmost_bit_i;
        }
    }
    document.write(numbers_rightmost_setbit_K);
}
 
   
// Driver Code
     
    let N = 15;
    let K = 2;
    countNumberHavingKthBitSet(N, K);
   
</script>

4

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