Intercambios mínimos de bits entre números dados para hacer su Bitwise OR igual a Bitwise AND

Posted on by Rudeus Greyrat

Dados dos números enteros positivos A y B, la tarea es calcular el número mínimo de operaciones necesarias para que Bitwise OR de A y B sea igual Bitwise AND de A y B sean iguales, es decir (A&B)=(A|B) , donde, en en cada operación se eligen dos índices i y j y el i -ésimo bit de A se intercambia con el j -ésimo bit de B. Si no es posible hacer (A&B)=(A|B), imprima -1.

Ejemplos:

Entrada: A = 1, B = 2
Salida: 2
Explicación:
A 10 ≡ 01 2 , B 10 ≡ 10 2
Se puede realizar la siguiente secuencia de movimientos:

  • i = 1, j = 1⇒ A = 11, B = 00 (A|B = 3, A&B = 0).
  • i = 1, j = 0⇒ A = 01, B = 01 (A|B = 1, A&B = 1).

Por lo tanto, se requieren 2 movimientos.

Entrada: A = 27, B = 5
Salida: 3
Explicación:
A 10 ≡ 11011 2 , B 10 ≡ 00101 2
Se puede realizar la siguiente secuencia de movimientos:

  • i = 4, j = 3⇒ A = 01011, B = 01101 (A|B = 15, A&B = 9).
  • i = 2, j = 2⇒ A = 01111, B = 01001 (A|B = 15, A&B = 9).
  • i = 2, j = 1⇒ A = 01011, B = 01011 (A|B = 11, A&B = 11).

Por lo tanto, se requieren 3 movimientos.

 

Enfoque : 
Observación: La principal observación para resolver este problema es que para (A&B)=(A|B) A debe ser igual a B porque si solo se establecen dos bits, entonces solo su Bitwise AND y Bitwise OR son iguales.

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

  1. Cuente el número total de bits establecidos en A y B.
  2. Si el conteo es impar, los dos números no se pueden hacer iguales, así que imprima -1.
  3. Inicializar dos contadores oneZero =0 y zeroOne =0
  4. Atraviese los bits de A y B y haga lo siguiente:
    • Si el bit actual de A está establecido y el bit actual de B no está establecido, es decir (1, 0), incremente oneZero .
    • Si el bit actual de A no está configurado y el bit actual de B está configurado, es decir (0, 1), incremente ceroUno .
  5. Para minimizar el número de operaciones requeridas, es óptimo elegir dos (1, 0) o dos (0, 1) índices e intercambiar cualquiera de ellos, es decir, solo se requieren la mitad de las operaciones oneZero y zeroOne .
  6. Si oneZero es impar (lo que significa que zeroOne también es impar), se requerirían dos operaciones más para convertir (0, 1) y a (1, 0) en (1, 1) y (0, 0)
  7.  Entonces, la respuesta final es (oneZero/2)+(zeroOne/2)+(oneZero%2?2:0).

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

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for counting number of set bit
int countSetBits(int n)
{
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}
// Function to return the count of
// minimum operations required
int minOperations(int A, int B)
{
    // cnt to count the number of bits
    // set in A and in B
    int cnt1 = 0, cnt2 = 0;
    cnt1 += countSetBits(A);
    cnt2 += countSetBits(B);
 
    // if odd numbers of total set bits
    if ((cnt1 + cnt2) % 2 != 0)
        return -1;
    // one_zero = 1 in A and 0 in B at ith bit
    // similarly for zero_one
    int oneZero = 0, zeroOne = 0;
    int ans = 0;
 
    for (int i = 0; i < max(cnt1, cnt2); i++) {
        int bitpos = 1 << i;
        // When bitpos is set in B, unset in B
        if ((!(bitpos & A)) && (bitpos & B))
            zeroOne++;
        // When bitpos is set in A, unset in B
        if ((bitpos & A) && (!(bitpos & B)))
            oneZero++;
    }
    // number of moves is half of
    // number pairs of each group
    ans = (zeroOne / 2) + (oneZero / 2);
    // odd number pairs
    if (zeroOne % 2 != 0)
        ans += 2;
 
    return ans;
}
 
// Driver code
int main()
{
 
    // Input
    int A = 27, B = 5;
 
    // Function call to compute the result
    cout << minOperations(A, B);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
class GFG{
     
// Function for counting number of set bit
static int countSetBits(int n)
{
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
    }
    return count;
}
// Function to return the count of
// minimum operations required
static int minOperations(int A, int B)
{
   
    // cnt to count the number of bits
    // set in A and in B
    int cnt1 = 0, cnt2 = 0;
    cnt1 += countSetBits(A);
    cnt2 += countSetBits(B);
 
    // if odd numbers of total set bits
    if ((cnt1 + cnt2) % 2 != 0)
        return -1;
   
    // one_zero = 1 in A and 0 in B at ith bit
    // similarly for zero_one
    int oneZero = 0, zeroOne = 0;
    int ans = 0;
 
    for (int i = 0; i < Math.max(cnt1, cnt2); i++) {
        int bitpos = 1 << i;
       
        // When bitpos is set in B, unset in B
        if (((bitpos & A) == 0) && ((bitpos & B) != 0))
            zeroOne++;
       
        // When bitpos is set in A, unset in B
        if (((bitpos & A) != 0) && ((bitpos & B) == 0))
            oneZero++;
    }
    // number of moves is half of
    // number pairs of each group
    ans = (zeroOne / 2) + (oneZero / 2);
   
    // odd number pairs
    if (zeroOne % 2 != 0)
        ans += 2;
 
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
     
    // Input
    int A = 27, B = 5;
 
    // Function call to compute the result
    System.out.println( minOperations(A, B));
}
}
 
// This code is contributed by splevel62.

Python3

# Python3 implementation of the above approach
 
# Function for counting number of set bit
def countSetBits(n):
     
    count = 0
    while (n):
        n = n & (n - 1)
        count += 1
         
    return count
     
# Function to return the count of
# minimum operations required
def minOperations(A, B):
     
    # cnt to count the number of bits
    # set in A and in B
    cnt1 = 0
    cnt2 = 0
    cnt1 += countSetBits(A)
    cnt2 += countSetBits(B)
 
    # If odd numbers of total set bits
    if ((cnt1 + cnt2) % 2 != 0):
        return -1
         
    # one_zero = 1 in A and 0 in B at ith bit
    # similarly for zero_one
    oneZero = 0
    zeroOne = 0
    ans = 0
 
    for i in range(max(cnt1, cnt2)):
        bitpos = 1 << i
         
        # When bitpos is set in B, unset in B
        if ((not(bitpos & A)) and (bitpos & B)):
            zeroOne += 1
             
        # When bitpos is set in A, unset in B
        if ((bitpos & A) and (not(bitpos & B))):
            oneZero += 1
             
    # Number of moves is half of
    # number pairs of each group
    ans = (zeroOne // 2) + (oneZero // 2)
     
    # Odd number pairs
    if (zeroOne % 2 != 0):
        ans += 2
 
    return ans
 
# Driver code
if __name__ == '__main__':
 
    # Input
    A = 27
    B = 5
 
    # Function call to compute the result
    print(minOperations(A, B))
     
# This code is contributed by mohit kumar 29

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function for counting number of set bit
static int countSetBits(int n)
{
    int count = 0;
    while (n > 0)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}
 
// Function to return the count of
// minimum operations required
static int minOperations(int A, int B)
{
     
    // cnt to count the number of bits
    // set in A and in B
    int cnt1 = 0, cnt2 = 0;
    cnt1 += countSetBits(A);
    cnt2 += countSetBits(B);
 
    // If odd numbers of total set bits
    if ((cnt1 + cnt2) % 2 != 0)
        return -1;
         
    // one_zero = 1 in A and 0 in B at ith bit
    // similarly for zero_one
    int oneZero = 0, zeroOne = 0;
    int ans = 0;
 
    for(int i = 0; i < Math.Max(cnt1, cnt2); i++)
    {
        int bitpos = 1 << i;
         
        // When bitpos is set in B, unset in B
        if (((bitpos & A) == 0) && (bitpos & B) != 0)
            zeroOne++;
             
        // When bitpos is set in A, unset in B
        if ((bitpos & A) != 0 && ((bitpos & B) == 0))
            oneZero++;
    }
     
    // Number of moves is half of
    // number pairs of each group
    ans = (zeroOne / 2) + (oneZero / 2);
     
    // Odd number pairs
    if (zeroOne % 2 != 0)
        ans += 2;
 
    return ans;
}
 
// Driver code
public static void Main()
{
     
    // Input
    int A = 27, B = 5;
 
    // Function call to compute the result
    Console.Write(minOperations(A, B));
}
}
 
// This code is contributed by bgangwar59

Javascript

<script>
 
// JavaScript implementation of the above approach
 
// Function for counting number of set bit
function countSetBits(n)
{
    let count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}
// Function to return the count of
// minimum operations required
function minOperations(A, B)
{
    // cnt to count the number of bits
    // set in A and in B
    let cnt1 = 0, cnt2 = 0;
    cnt1 += countSetBits(A);
    cnt2 += countSetBits(B);
 
    // if odd numbers of total set bits
    if ((cnt1 + cnt2) % 2 != 0)
        return -1;
    // one_zero = 1 in A and 0 in B at ith bit
    // similarly for zero_one
    let oneZero = 0, zeroOne = 0;
    let ans = 0;
 
    for (let i = 0; i < Math.max(cnt1, cnt2); i++) {
        let bitpos = 1 << i;
        // When bitpos is set in B, unset in B
        if ((!(bitpos & A)) && (bitpos & B))
            zeroOne++;
        // When bitpos is set in A, unset in B
        if ((bitpos & A) && (!(bitpos & B)))
            oneZero++;
    }
    // number of moves is half of
    // number pairs of each group
    ans = parseInt(zeroOne / 2) + parseInt(oneZero / 2);
    // odd number pairs
    if (zeroOne % 2 != 0)
        ans += 2;
 
    return ans;
}
 
// Driver code
 
    // Input
    let A = 27, B = 5;
 
    // Function call to compute the result
    document.write(minOperations(A, B));
     
</script>
Producción

3

Complejidad temporal: O(Log 2 N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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