Contar números menores que N cuyo Bitwise AND con N es cero

Posted on by Rudeus Greyrat

Dado un entero positivo N , la tarea es contar todos los números que son menores que N, cuyo AND bit a bit de todos esos números con N es cero.

Ejemplos:

Entrada: N = 5
Salida: 2
Explicación: Los enteros menores que N(= 5) cuyo AND bit a bit con 5 es 0 son 0 y 2. Por lo tanto, la cuenta total es 2.

Entrada: N = 9
Salida: 4

Enfoque ingenuo: la idea es ir por cada número menor que n y verificar si es Bitwise Y con n es cero (0) o no. Si AND bit a bit se convierte en cero, entonces incremente el contador y finalmente devuelva el contador.
Siga los pasos a continuación para implementar la idea anterior:

  1. Inicializar cuenta con 0
  2. Iterar de i = 0 a n y calcular el AND bit a bit de i con n
    Si AND bit a bit con n se convierte en cero, entonces incremente el valor de count en 1.
  3. Devuelve la cuenta.

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 whose
// Bitwise AND with N equal to 0
int countBitwiseZero(int n)
{
    int count = 0;
    for (int i = 0; i < n; i++) {
 
        // If n&i == 0 then we will increase count by 1
        int temp = n & i;
        if (temp == 0) {
            count++;
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    int n = 9;
    cout << countBitwiseZero(n);
    return 0;
}
Producción

4

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

Enfoque: El problema dado se puede resolver en base a la observación de que todos los bits que están establecidos en N se desactivarán en cualquier número que tenga Bitwise AND con N igual a 0 . Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos unsetBits , igual al número total de bits no establecidos en el entero N dado .
  • Ahora, cada bit no establecido en N puede tener 0 o 1 en la posición correspondiente, ya que Bitwise AND para cualquier posición en la que N tenga un bit no establecido siempre será igual a 0 . Por lo tanto, el número total de posibilidades diferentes será 2 elevado a la potencia de unsetBits .
  • Por lo tanto, imprima el valor de 2 a la potencia de unsetBits como resultado.

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 number of
// unset bits in the integer N
int countUnsetBits(int N)
{
    // Stores the number of unset
    // bits in N
    int c = 0;
 
    while (N) {
 
        // Check if N is even
        if (N % 2 == 0) {
 
            // Increment the value of c
            c += 1;
        }
 
        // Right shift N by 1
        N = N >> 1;
    }
 
    // Return the value of
    // count of unset bits
    return c;
}
 
// Function to count numbers whose
// Bitwise AND with N equal to 0
void countBitwiseZero(int N)
{
    // Stores the number
    // of unset bits in N
    int unsetBits = countUnsetBits(N);
 
    // Print the value of 2 to the
    // power of unsetBits
    cout << (1 << unsetBits);
}
 
// Driver Code
int main()
{
    int N = 9;
    countBitwiseZero(N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count number of
// unset bits in the integer N
static int countUnsetBits(int N)
{
    // Stores the number of unset
    // bits in N
    int c = 0;
 
    while (N != 0) {
 
        // Check if N is even
        if (N % 2 == 0) {
 
            // Increment the value of c
            c += 1;
        }
 
        // Right shift N by 1
        N = N >> 1;
    }
 
    // Return the value of
    // count of unset bits
    return c;
}
 
// Function to count numbers whose
// Bitwise AND with N equal to 0
static void countBitwiseZero(int N)
{
    // Stores the number
    // of unset bits in N
    int unsetBits = countUnsetBits(N);
 
    // Print the value of 2 to the
    // power of unsetBits
    System.out.print(1 << unsetBits);
}
 
// Driver Code
public static void main(String[] args)
{
     int N = 9;
    countBitwiseZero(N);
}
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program for the above approach
 
# Function to count number of
# unset bits in the integer N
def countUnsetBits(N):
   
    # Stores the number of unset
    # bits in N
    c = 0
 
    while (N):
 
        # Check if N is even
        if (N % 2 == 0):
           
            # Increment the value of c
            c += 1
             
        # Right shift N by 1
        N = N >> 1
 
    # Return the value of
    # count of unset bits
    return c
 
# Function to count numbers whose
# Bitwise AND with N equal to 0
def countBitwiseZero(N):
   
    # Stores the number
    # of unset bits in N
    unsetBits = countUnsetBits(N)
 
    # Print value of 2 to the
    # power of unsetBits
    print ((1 << unsetBits))
 
# Driver Code
if __name__ == '__main__':
    N = 9
    countBitwiseZero(N)
 
    # This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count number of
// unset bits in the integer N
static int countUnsetBits(int N)
{
     
    // Stores the number of unset
    // bits in N
    int c = 0;
 
    while (N != 0)
    {
         
        // Check if N is even
        if (N % 2 == 0)
        {
             
            // Increment the value of c
            c += 1;
        }
 
        // Right shift N by 1
        N = N >> 1;
    }
 
    // Return the value of
    // count of unset bits
    return c;
}
 
// Function to count numbers whose
// Bitwise AND with N equal to 0
static void countBitwiseZero(int N)
{
     
    // Stores the number
    // of unset bits in N
    int unsetBits = countUnsetBits(N);
 
    // Print the value of 2 to the
    // power of unsetBits
    Console.Write(1 << unsetBits);
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 9;
     
    countBitwiseZero(N);
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// Javascript program for the above approach
// Function to count number of
// unset bits in the integer N
function countUnsetBits( N)
{
    // Stores the number of unset
    // bits in N
    let c = 0;
 
    while (N != 0) {
 
        // Check if N is even
        if (N % 2 == 0) {
 
            // Increment the value of c
            c += 1;
        }
 
        // Right shift N by 1
        N = N >> 1;
    }
 
    // Return the value of
    // count of unset bits
    return c;
}
 
// Function to count numbers whose
// Bitwise AND with N equal to 0
function countBitwiseZero( N)
{
    // Stores the number
    // of unset bits in N
    let unsetBits = countUnsetBits(N);
 
    // Print the value of 2 to the
    // power of unsetBits
    document.write(1 << unsetBits);
}
 
// Driver Code
    let N = 9;
    countBitwiseZero(N);
 
// This code is contributed by shivansinghss2110
</script>
Producción

4

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

Publicación traducida automáticamente

Artículo escrito por adityamutharia 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 *