Recuento de números que tienen solo un bit no establecido en un rango [L,R]

Posted on by Rudeus Greyrat

Dados dos enteros L y R , la tarea es contar los números que tienen solo un bit no establecido en el rango [L, R] .

Ejemplos:

Entrada: L = 4, R = 9
Salida: 2
Explicación:
La representación binaria de todos los números en el rango [4, 9] son 
​​4 = (100) 2 
5 = (101) 2 
6 = (110) 2 
7 = ( 111) 2 
8 = (1000) 2 
9 = (1001) 2 
De todos los números anteriores, solo 5 y 6 tienen exactamente un bit sin configurar.
Por lo tanto, el conteo requerido es 2.

Entrada: L = 10, R = 13
Salida: 2
Explicación:
Las representaciones binarias de todos los números en el rango [10, 13] 
10 = (1010) 2 
11 = (1011) 2 
12 = (1100) 2 
13 = (1101 ) 2 
De todos los números anteriores, solo 11 y 13 tienen exactamente un bit sin configurar. 
Por lo tanto, el conteo requerido es 2.

Enfoque ingenuo: el enfoque más simple es verificar cada número en el rango [L, R] si tiene exactamente un bit sin configurar o no. Para cada uno de esos números, incremente el conteo. Después de recorrer todo el rango, imprima el valor de count .

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count numbers in the range
// [l, r] having exactly one unset bit
int count_numbers(int L, int R)
{
    // Stores the required count
    int ans = 0;
 
    // Iterate over the range
    for (int n = L; n <= R; n++) {
 
        // Calculate number of bits
        int no_of_bits = log2(n) + 1;
 
        // Calculate number of set bits
        int no_of_set_bits
            = __builtin_popcount(n);
 
        // If count of unset bits is 1
        if (no_of_bits
                - no_of_set_bits
            == 1) {
 
            // Increment answer
            ans++;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int L = 4, R = 9;
 
    // Function Call
    cout << count_numbers(L, R);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to count numbers in the range
// [l, r] having exactly one unset bit
static int count_numbers(int L,
                         int R)
{
    // Stores the required count
    int ans = 0;
 
    // Iterate over the range
    for (int n = L; n <= R; n++)
    {
        // Calculate number of bits
        int no_of_bits = (int) (Math.log(n) + 1);
 
        // Calculate number of set bits
        int no_of_set_bits = Integer.bitCount(n);
 
        // If count of unset bits is 1
        if (no_of_bits - no_of_set_bits == 1)
        {
            // Increment answer
            ans++;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int L = 4, R = 9;
 
    // Function Call
    System.out.print(count_numbers(L, R));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
from math import log2
 
# Function to count numbers in the range
# [l, r] having exactly one unset bit
def count_numbers(L, R):
     
    # Stores the required count
    ans = 0
 
    # Iterate over the range
    for n in range(L, R + 1):
 
        # Calculate number of bits
        no_of_bits = int(log2(n) + 1)
 
        # Calculate number of set bits
        no_of_set_bits = bin(n).count('1')
 
        # If count of unset bits is 1
        if (no_of_bits - no_of_set_bits == 1):
 
            # Increment answer
            ans += 1
 
    # Return the answer
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    L = 4
    R = 9
 
    # Function call
    print(count_numbers(L, R))
 
# This code is contributed by mohit kumar 29   

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count numbers in the range
// [l, r] having exactly one unset bit
static int count_numbers(int L,
                         int R)
{
     
    // Stores the required count
    int ans = 0;
 
    // Iterate over the range
    for(int n = L; n <= R; n++)
    {
         
        // Calculate number of bits
        int no_of_bits = (int)(Math.Log(n) + 1);
 
        // Calculate number of set bits
        int no_of_set_bits = bitCount(n);
 
        // If count of unset bits is 1
        if (no_of_bits - no_of_set_bits == 1)
        {
             
            // Increment answer
            ans++;
        }
    }
 
    // Return the answer
    return ans;
}
 
static int bitCount(long x)
{
    int setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
 
// Driver Code
public static void Main(String[] args)
{
    int L = 4, R = 9;
 
    // Function call
    Console.Write(count_numbers(L, R));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// javascript program for the
// above approach
 
// Function to count numbers in the range
// [l, r] having exactly one unset bit
function count_numbers(L, R)
{
    // Stores the required count
    let ans = 0;
  
    // Iterate over the range
    for (let n = L; n <= R; n++)
    {
        // Calculate number of bits
        let no_of_bits = Math.floor(Math.log(n) + 1);
  
        // Calculate number of set bits
        let no_of_set_bits = bitCount(n);
  
        // If count of unset bits is 1
        if (no_of_bits - no_of_set_bits == 1)
        {
            // Increment answer
            ans++;
        }
    }
  
    // Return the answer
    return ans;
}
 
function bitCount(x)
{
    let setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
  
// Driver Code
 
    let L = 4, R = 9;
  
    // Function Call
    document.write(count_numbers(L, R));
 
// This code is contributed by avijitmondal1998.
</script>
Producción: 

2

Complejidad de tiempo: O(N*Log R)
Espacio auxiliar: O(1)

Enfoque eficiente: dado que el número máximo de bits es como máximo log R y el número debe contener exactamente un cero en su representación binaria, fije una posición en [0, log R] como el bit no configurado y configure todos los demás bits e incremente el conteo si el número generado está dentro del rango dado. 
Siga los pasos a continuación para resolver el problema:

  1. Recorra todas las posiciones posibles de bit no establecido, digamos zero_bit , en el rango [0, log R]
  2. Establezca todos los bits antes de zero_bit .
  3. Iterar sobre el rango j = zero_bit + 1 para registrar R y establecer el bit en la posición j e incrementar el conteo si el número formado está dentro del rango [L, R] .
  4. Imprima el recuento después de los pasos anteriores.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count numbers in the range
// [L, R] having exactly one unset bit
int count_numbers(int L, int R)
{
    // Stores the count elements
    // having one zero in binary
    int ans = 0;
 
    // Stores the maximum number of
    // bits needed to represent number
    int LogR = log2(R) + 1;
 
    // Loop over for zero bit position
    for (int zero_bit = 0;
         zero_bit < LogR; zero_bit++) {
 
        // Number having zero_bit as unset
        // and remaining bits set
        int cur = 0;
 
        // Sets all bits before zero_bit
        for (int j = 0; j < zero_bit; j++) {
 
            // Set the bit at position j
            cur |= (1LL << j);
        }
 
        for (int j = zero_bit + 1;
             j < LogR; j++) {
 
            // Set the bit position at j
            cur |= (1LL << j);
 
            // If cur is in the range [L, R],
            // then increment ans
            if (cur >= L && cur <= R) {
                ans++;
            }
        }
    }
 
    // Return ans
    return ans;
}
 
// Driver Code
int main()
{
    long long L = 4, R = 9;
 
    // Function Call
    cout << count_numbers(L, R);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to count numbers in the range
// [L, R] having exactly one unset bit
static int count_numbers(int L, int R)
{
  // Stores the count elements
  // having one zero in binary
  int ans = 0;
 
  // Stores the maximum number of
  // bits needed to represent number
  int LogR = (int) (Math.log(R) + 1);
 
  // Loop over for zero bit position
  for (int zero_bit = 0; zero_bit < LogR;
           zero_bit++)
  {
    // Number having zero_bit as unset
    // and remaining bits set
    int cur = 0;
 
    // Sets all bits before zero_bit
    for (int j = 0; j < zero_bit; j++)
    {
      // Set the bit at position j
      cur |= (1L << j);
    }
 
    for (int j = zero_bit + 1;
             j < LogR; j++)
    {
      // Set the bit position at j
      cur |= (1L << j);
 
      // If cur is in the range [L, R],
      // then increment ans
      if (cur >= L && cur <= R)
      {
        ans++;
      }
    }
  }
 
  // Return ans
  return ans;
}
 
// Driver Code
public static void main(String[] args)
{
  int L = 4, R = 9;
 
  // Function Call
  System.out.print(count_numbers(L, R));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for
# the above approach
import  math
 
# Function to count numbers in the range
# [L, R] having exactly one unset bit
def count_numbers(L, R):
   
    # Stores the count elements
    # having one zero in binary
    ans = 0;
 
    # Stores the maximum number of
    # bits needed to represent number
    LogR = (int)(math.log(R) + 1);
 
    # Loop over for zero bit position
    for zero_bit in range(LogR):
       
        # Number having zero_bit as unset
        # and remaining bits set
        cur = 0;
 
        # Sets all bits before zero_bit
        for j in range(zero_bit):
           
            # Set the bit at position j
            cur |= (1 << j);
 
        for j in range(zero_bit + 1, LogR):
           
            # Set the bit position at j
            cur |= (1 << j);
 
            # If cur is in the range [L, R],
            # then increment ans
            if (cur >= L and cur <= R):
                ans += 1;
 
    # Return ans
    return ans;
 
# Driver Code
if __name__ == '__main__':
    L = 4;
    R = 9;
 
    # Function Call
    print(count_numbers(L, R));
 
# This code is contributed by Rajput-Ji

C#

// C# program for
// the above approach
using System;
 
public class GFG{
 
// Function to count numbers in the range
// [L, R] having exactly one unset bit
static int count_numbers(int L, int R)
{
  // Stores the count elements
  // having one zero in binary
  int ans = 0;
 
  // Stores the maximum number of
  // bits needed to represent number
  int LogR = (int) (Math.Log(R) + 1);
 
  // Loop over for zero bit position
  for (int zero_bit = 0; zero_bit < LogR;
           zero_bit++)
  {
    // Number having zero_bit as unset
    // and remaining bits set
    int cur = 0;
 
    // Sets all bits before zero_bit
    for (int j = 0; j < zero_bit; j++)
    {
      // Set the bit at position j
      cur |= (1 << j);
    }
 
    for (int j = zero_bit + 1;
             j < LogR; j++)
    {
      // Set the bit position at j
      cur |= (1 << j);
 
      // If cur is in the range [L, R],
      // then increment ans
      if (cur >= L && cur <= R)
      {
        ans++;
      }
    }
  }
 
  // Return ans
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
  int L = 4, R = 9;
 
  // Function Call
  Console.Write(count_numbers(L, R));
}
}
 
 
 
// This code contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript  program for
//the above approach
 
// Function to count numbers in the range
// [L, R] having exactly one unset bit
function count_numbers(L, R)
{
  // Stores the count elements
  // having one zero in binary
  let ans = 0;
  
  // Stores the maximum number of
  // bits needed to represent number
  let LogR =  (Math.log(R) + 1);
  
  // Loop over for zero bit position
  for (let zero_bit = 0; zero_bit < LogR;
           zero_bit++)
  {
    // Number having zero_bit as unset
    // and remaining bits set
    let cur = 0;
  
    // Sets all bits before zero_bit
    for (let j = 0; j < zero_bit; j++)
    {
      // Set the bit at position j
      cur |= (1 << j);
    }
  
    for (let j = zero_bit + 1;
             j < LogR; j++)
    {
      // Set the bit position at j
      cur |= (1 << j);
  
      // If cur is in the range [L, R],
      // then increment ans
      if (cur >= L && cur <= R)
      {
        ans++;
      }
    }
  }
  
  // Return ans
  return ans;
}
  
// Driver Code
 
    let L = 4, R = 9;
  
  // Function Call
  document.write(count_numbers(L, R));
  
 // This code is contributed by souravghosh0416.
</script>
Producción: 

2

Complejidad de Tiempo: O((log R) 2 )
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por dp82 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *