Números formados al voltear bits conjuntos comunes en dos enteros dados

Posted on by Rudeus Greyrat

Dados dos números enteros positivos A y B , la tarea es invertir los bits comunes establecidos en A y B .

Ejemplos:

Entrada: A = 7, B = 4 
Salida: 3 0 
Explicación: 
La representación binaria de 7 es 111 
La representación binaria de 4 es 100 
Dado que el tercer bit de A y B es un bit establecido. Por lo tanto, cambiar el tercer bit de A y B modifica A = 3 y B = 0. 
Por lo tanto, la salida requerida es 3 0

Entrada: A = 10, B = 20 
Salida: 10 20

Enfoque ingenuo: el enfoque más simple para resolver este problema es verificar si el i -ésimo bit de A y B es un conjunto o no . Si se determina que es cierto, cambie el i -ésimo bit de A y B. Finalmente, imprima los valores actualizados de A y B .

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to flip bits of A and B
// which are set bits in A and B
void flipBitsOfAandB(int A, int B)
{
    // Iterator all possible bits
    // of A and B
    for (int i = 0; i < 32; i++) {
 
        // If ith bit is set in
        // both A and B
        if ((A & (1 << i)) && (B & (1 << i))) {
 
            // Clear i-th bit of A
            A = A ^ (1 << i);
 
            // Clear i-th bit of B
            B = B ^ (1 << i);
        }
    }
 
    // Print A and B
    cout << A << " " << B;
}
 
// Driver Code
int main()
{
    int A = 7, B = 4;
 
    flipBitsOfAandB(A, B);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
   
class GFG{
   
// Function to flip bits of A and B
// which are set bits in A and B
static void flipBitsOfAandB(int A, int B)
{
     
    // Iterator all possible bits
    // of A and B
    for(int i = 0; i < 32; i++)
    {
         
        // If ith bit is set in
        // both A and B
        if (((A & (1 << i)) &
             (B & (1 << i))) != 0)
        {
             
            // Clear i-th bit of A
            A = A ^ (1 << i);
  
            // Clear i-th bit of B
            B = B ^ (1 << i);
        }
    }
  
    // Print A and B
    System.out.print(A + " " + B);
}
   
// Driver Code
public static void main(String[] args)
{
    int A = 7, B = 4;
  
    flipBitsOfAandB(A, B);
}
}
 
// This code is contributed by code_hunt

Python3

# Python3 program to implement
# the above approach
 
# Function to flip bits of A and B
# which are set in both of them
def flipBitsOfAandB(A, B):
     
    # Iterate all possible bits of
    # A and B
    for i in range(0, 32):
         
        # If ith bit is set in
        # both A and B
        if ((A & (1 << i)) and
            (B & (1 << i))):
             
            # Clear i-th bit of A
            A = A ^ (1 << i)
 
            # Clear i-th bit of B
            B = B ^ (1 << i)
             
    print(A, B)
 
# Driver Code 
if __name__ == "__main__" :
     
    A = 7
    B = 4
     
    flipBitsOfAandB(A, B)
     
# This code is contributed by Virusbuddah_

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to flip bits of A and B
// which are set bits in A and B
static void flipBitsOfAandB(int A, int B)
{
     
    // Iterator all possible bits
    // of A and B
    for(int i = 0; i < 32; i++)
    {
         
        // If ith bit is set in
        // both A and B
        if (((A & (1 << i)) &
             (B & (1 << i))) != 0)
        {
             
            // Clear i-th bit of A
            A = A ^ (1 << i);
 
            // Clear i-th bit of B
            B = B ^ (1 << i);
        }
    }
 
    // Print A and B
    Console.Write(A + " " + B);
}
 
// Driver Code
public static void Main(string[] args)
{
    int A = 7, B = 4;
 
    flipBitsOfAandB(A, B);
}
}
 
// This code is contributed by chitranayal

Javascript

<script>
// javascript program to implement
// the above approach
 
 
// Function to flip bits of A and B
// which are set bits in A and B
function flipBitsOfAandB(A , B)
{
     
    // Iterator all possible bits
    // of A and B
    for(i = 0; i < 32; i++)
    {
         
        // If ith bit is set in
        // both A and B
        if (((A & (1 << i)) &
             (B & (1 << i))) != 0)
        {
             
            // Clear i-th bit of A
            A = A ^ (1 << i);
  
            // Clear i-th bit of B
            B = B ^ (1 << i);
        }
    }
  
    // Print A and B
    document.write(A + " " + B);
}
   
// Driver Code
var A = 7, B = 4;
 
flipBitsOfAandB(A, B);
 
// This code is contributed by Princi Singh
 
</script>
Producción: 

3 0

 

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

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:

Encuentre los bits que son bits establecidos tanto en A como en B usando (A y B). 
Borre los bits de A que son bits establecidos tanto en A como en B usando A = (A ^ (A & B)) 
Borre los bits de B que son bits establecidos tanto en A como en B usando B = (B ^ (A & B) )) 
 

Siga los pasos a continuación para resolver el problema:

  • Actualizar A = (A ^ (A & B)) .
  • Actualizar B = (B ^ (A & B)) .
  • Finalmente, imprima los valores actualizados de A y B.

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to flip bits of A and B
// which are set in both of them
void flipBitsOfAandB(int A, int B)
{
 
    // Clear the bits of A which
    // are set in both A and B
    A = A ^ (A & B);
 
    // Clear the bits of B which
    // are set in both A and B
    B = B ^ (A & B);
 
    // Print updated A and B
    cout << A << " " << B;
}
 
// Driver Code
int main()
{
    int A = 10, B = 20;
 
    flipBitsOfAandB(A, B);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
    
class GFG{
    
// Function to flip bits of A and B
// which are set in both of them
static void flipBitsOfAandB(int A, int B)
{
     
    // Clear the bits of A which
    // are set in both A and B
    A = A ^ (A & B);
     
    // Clear the bits of B which
    // are set in both A and B
    B = B ^ (A & B);
  
    // Print updated A and B
    System.out.print(A + " " + B);
}
    
// Driver Code
public static void main(String[] args)
{
    int A = 10, B = 20;
     
    flipBitsOfAandB(A, B);
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program to implement
# the above approach
 
# Function to flip bits of A and B
# which are set in both of them
def flipBitsOfAandB(A, B):
     
    # Clear the bits of A which
    # are set in both A and B
    A = A ^ (A & B)
 
    # Clear the bits of B which
    # are set in both A and B
    B = B ^ (A & B)
 
    # Print updated A and B
    print(A, B)
 
# Driver Code 
if __name__ == "__main__" :
     
    A = 10
    B = 20
     
    flipBitsOfAandB(A, B)
     
# This code is contributed by Virusbuddah_

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
    
// Function to flip bits of A and B
// which are set in both of them
static void flipBitsOfAandB(int A, int B)
{
   
    // Clear the bits of A which
    // are set in both A and B
    A = A ^ (A & B);
     
    // Clear the bits of B which
    // are set in both A and B
    B = B ^ (A & B);
  
    // Print updated A and B
    Console.Write(A + " " + B);
}
    
// Driver Code
public static void Main(String[] args)
{
    int A = 10, B = 20;
     
    flipBitsOfAandB(A, B);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// javascript program to implement
// the above approach
 
    
// Function to flip bits of A and B
// which are set in both of them
function flipBitsOfAandB(A , B)
{
     
    // Clear the bits of A which
    // are set in both A and B
    A = A ^ (A & B);
     
    // Clear the bits of B which
    // are set in both A and B
    B = B ^ (A & B);
  
    // Print updated A and B
    document.write(A + " " + B);
}
    
// Driver Code
var A = 10, B = 20;
 
flipBitsOfAandB(A, B);
 
// This code contributed by shikhasingrajput
 
</script>
Producción: 

10 20

 

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

Publicación traducida automáticamente

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