Recuento de números en el rango [L, R] con LSB como 0 en su representación binaria

Dados dos enteros L y R . La tarea es encontrar el conteo de todos los números en el rango [L, R] cuyo bit menos significativo en representación binaria es 0.  

Ejemplos :  

Entrada : L = 10, R = 20  
Salida : 6  

Entrada : L = 7, R = 11  
Salida : 2   

Enfoque ingenuo : el enfoque más simple para resolver este problema es verificar cada número en el rango [L, R],  si el bit menos significativo en la representación binaria es 0.

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

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of required numbers
int countNumbers(int l, int r)
{
    int count = 0;
 
    for (int i = l; i <= r; i++) {
        // If rightmost bit is 0
        if ((i & 1) == 0) {
            count++;
        }
    }
    // Return the required count
    return count;
}
 
// Driver code
int main()
{
    int l = 10, r = 20;
 
    // Call function countNumbers
    cout << countNumbers(l, r);
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG{
     
// Function to return the count
// of required numbers
static int countNumbers(int l, int r)
{
    int count = 0;
    for(int i = l; i <= r; i++)
    {
         
        // If rightmost bit is 0
        if ((i & 1) == 0)
            count += 1;
    }
     
    // Return the required count
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int l = 10, r = 20;
     
    // Call function countNumbers
    System.out.println(countNumbers(l, r));
}
}
 
// This code is contributed by MuskanKalra1

# Python3 implementation of the approach
 
# Function to return the count
# of required numbers
def countNumbers(l, r):
     
    count = 0
     
    for i in range(l, r + 1):
         
        # If rightmost bit is 0
        if ((i & 1) == 0):
            count += 1
             
    # Return the required count
    return count
 
# Driver code
l = 10
r = 20
 
# Call function countNumbers
print(countNumbers(l, r))
 
# This code is contributed by amreshkumar3

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to return the count
    // of required numbers
    static int countNumbers(int l, int r)
    {
        int count = 0;
        for (int i = l; i <= r; i++) {
 
            // If rightmost bit is 0
            if ((i & 1) == 0)
                count += 1;
        }
 
        // Return the required count
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int l = 10, r = 20;
 
        // Call function countNumbers
        Console.WriteLine(countNumbers(l, r));
    }
}
 
// This code is contributed by subham348.

<script>
 
// JavaScript implementation of the approach
 
// Function to return the count
// of required numbers
function countNumbers(l, r)
{
    let count = 0;
 
    for (let i = l; i <= r; i++) {
        // If rightmost bit is 0
        if ((i & 1) == 0) {
            count++;
        }
    }
    // Return the required count
    return count;
}
 
// Driver code
    let l = 10, r = 20;
 
    // Call function countNumbers
    document.write(countNumbers(l, r));
 
</script>

6

Complejidad temporal: O(r – l)  
Espacio auxiliar: O(1)

Enfoque eficiente : este problema se puede resolver utilizando las propiedades de los bits . Solo los números pares tienen el bit más a la derecha como 0 . El conteo se puede encontrar usando esta fórmula ((R / 2) – (L – 1) / 2) en tiempo O(1) .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of required numbers
int countNumbers(int l, int r)
{
    // Count of numbers in range
    // which are divisible by 2
    return ((r / 2) - (l - 1) / 2);
}
 
// Driver code
int main()
{
    int l = 10, r = 20;
    cout << countNumbers(l, r);
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG{
     
// Function to return the count
// of required numbers
static int countNumbers(int l, int r)
{
     
    // Count of numbers in range
    //  which are divisible by 2
    return ((r / 2) - (l - 1) / 2);
}
 
// Driver Code
public static void main(String[] args)
{
    int l = 10;
    int r = 20;
     
    System.out.println(countNumbers(l, r));
}
}
 
// This code is contributed by MuskanKalra1

# Python3 implementation of the approach
 
# Function to return the count
# of required numbers
def countNumbers(l, r):
 
    # Count of numbers in range
    #  which are divisible by 2
    return ((r // 2) - (l - 1) // 2)
 
# Driver code
l = 10
r = 20
 
print(countNumbers(l, r))
 
# This code is contributed by amreshkumar3

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to return the count
// of required numbers
static int countNumbers(int l, int r)
{
   
    // Count of numbers in range
    // which are divisible by 2
    return ((r / 2) - (l - 1) / 2);
}
 
// Driver code
public static void Main()
{
    int l = 10, r = 20;
    Console.Write(countNumbers(l, r));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// Javascript implementation of the approach
 
// Function to return the count
// of required numbers
function countNumbers(l, r)
{
     
    // Count of numbers in range
    // which are divisible by 2
    return(parseInt(r / 2) -
          parseInt((l - 1) / 2));
}
 
// Driver code
let l = 10, r = 20;
 
document.write(countNumbers(l, r));
 
// This code is contributed by subhammahato348
 
</script>

6

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