Recuento de posibles pares cuya suma y bit a bit XOR se da

Dados dos enteros S y X que representan la suma y el XOR bit a bit respectivamente de dos enteros, la tarea es encontrar el recuento de todos los pares posibles de modo que su suma sea igual a S y el XOR bit a bit sea igual a X .

Ejemplos:

Entrada: S = 9, X = 5
Salida: 4
Explicación: (2, 7), (3, 6), (6, 3), (7, 2) satisface completamente las condiciones dadas.
También se puede ver que ningún otro par satisface la condición dada.
Entonces la posibilidad total es 4.

Entrada: S = 3, X = 3
Salida: 4
Explicación: Solo (1, 2), (2, 1), (3, 0) y (0, 3) satisfacen la condición dada.

Planteamiento: La solución al problema se basa en la siguiente observación:

Considere dos números a y b . Su suma se puede escribir como
a+b = (a XOR b) + (a AND b)*2

Lo anterior se puede demostrar de la siguiente manera:
si se suman dos bits x e y , el acarreo (digamos c ) será ( x Y y ) y está a una posición a la izquierda del único bit. Entonces, c = 2 * (x AND y)
El valor del bit más a la derecha (es decir, en la misma posición que los bits individuales) será ( x XOR y )
Por lo tanto, x + y = (x XOR y) + 2 * (X y Y)

Entonces, al agregar a y b , este procedimiento se repite para cada bit. Por lo tanto, se puede decir que la suma será 
a+b = (a XOR b) + (a AND b)*2 
S = X + 2*A donde A es el AND bit a bit de los dos números.
A = (S – X)/2

Según la observación anterior, el recuento se puede obtener a partir de los valores de bit de A y X según el siguiente caso

• Si el i- ^ésimo bit de X y A son 0, entonces solo hay un par posible para esa posición de bit.
• Si el i ^-ésimo bit de X es 1 y el de A es 0, entonces hay dos pares posibles para esa posición de bit.
• Si el i ^-ésimo bit de X es 0 y el de A es 1, entonces solo hay un par posible para esa posición de bit.
• No puede haber una situación en la que el i-ésimo bit en X sea 1 y el i- ^ésimo bit de A también sea 1.

De acuerdo con el principio de multiplicación de la permutación , para obtener el número de pares posibles que satisfacen la condición dada, simplemente multiplique todas las posibilidades. Siga los pasos mencionados a continuación para implementar la idea:

• Encuentre AND bit a bit de dos números usando la fórmula anterior.
• Si no es un número entero, entonces no existe solución 
• De lo contrario, para el valor dado de XOR ( X ) y AND (digamos A ), verifique cada bit 
  • Encuentre el número de posibilidades para ese bit usando los casos anteriores.
  • Multiplica estas posibilidades con la respuesta final. 
• Al final, el número total de posibilidades calculado según las condiciones anteriores es la respuesta requerida.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// total number of possible pairs
int count_all_possible_pair(int sum_value,
                            int xor_value)
{
    double and_value
        = ((sum_value - xor_value) / 2.0);
 
    // If and value is not an integer
    // then no pair is possible
    int check = and_value;
    if (check != and_value)
        return 0;
 
    int count = 1;
 
    // Traversing the bits of the sum_value
    // from MSB position
    for (int i = 1; i <= 32; i++) {
        int and_bit = (check >> i) & 1;
        int xor_bit = (xor_value >> i) & 1;
 
        // If both the bit is 0, only 1 possibility
        if (and_bit == 0 && xor_bit == 0)
            count = count * 1;
 
        // If Xor bit is 0 and And bit 1,
        // then only 1 possibility
        else if (xor_bit == 0 && and_bit == 1)
            count = count * 1;
 
        // If Xor bit is 1, And bit is 0,
        // then there are 2 possibilities
        else if (xor_bit == 1 && and_bit == 0)
            count = count * 2;
 
        // If Xor bit and And bit both 1,
        // no such case is possible
        else
            return 0;
    }
 
    // Return the count of possible pairs
    return count;
}
 
// Driver code
int main()
{
    int S = 9, X = 5;
 
    // Function call
    cout << count_all_possible_pair(S, X);
    return 0;
}

// Java code to implement the approach
 
public class GFG {
     
    // Function to calculate
    // total number of possible pairs
    static int count_all_possible_pair(int sum_value,
                                int xor_value)
    {
        double and_value
            = ((sum_value - xor_value) / 2.0);
     
        // If and value is not an integer
        // then no pair is possible
        int check = (int)and_value;
        if (check != and_value)
            return 0;
     
        int count = 1;
     
        // Traversing the bits of the sum_value
        // from MSB position
        for (int i = 1; i <= 32; i++) {
            int and_bit = (check >> i) & 1;
            int xor_bit = (xor_value >> i) & 1;
     
            // If both the bit is 0, only 1 possibility
            if (and_bit == 0 && xor_bit == 0)
                count = count * 1;
     
            // If Xor bit is 0 and And bit 1,
            // then only 1 possibility
            else if (xor_bit == 0 && and_bit == 1)
                count = count * 1;
     
            // If Xor bit is 1, And bit is 0,
            // then there are 2 possibilities
            else if (xor_bit == 1 && and_bit == 0)
                count = count * 2;
     
            // If Xor bit and And bit both 1,
            // no such case is possible
            else
                return 0;
        }
     
        // Return the count of possible pairs
        return count;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int S = 9, X = 5;
     
        // Function call
        System.out.println(count_all_possible_pair(S, X));
    }
}
 
// This code is contributed by AnkThon

# Python3 code to implement the approach
 
# Function to calculate
# total number of possible pairs
def count_all_possible_pair(sum_value, xor_value) :
    and_value = ((sum_value - xor_value) / 2.0);
 
    # If and value is not an integer
    # then no pair is possible
    check = int(and_value);
    if (check != and_value) :
        return 0;
 
    count = 1;
 
    # Traversing the bits of the sum_value
    # from MSB position
    for i in range(1 , 33) :
        and_bit = ((check >> i) & 1);
        xor_bit = ((xor_value >> i) & 1);
 
        # If both the bit is 0, only 1 possibility
        if (and_bit == 0 and xor_bit == 0) :
            count = count * 1;
 
        # If Xor bit is 0 and And bit 1,
        # then only 1 possibility
        elif (xor_bit == 0 and and_bit == 1) :
            count = count * 2;
 
        # If Xor bit is 1, And bit is 0,
        # then there are 2 possibilities
        elif (xor_bit == 1 and and_bit == 0) :
            count = count * 2;
 
        # If Xor bit and And bit both 1,
        # no such case is possible
        else :
            return 0;
 
    # Return the count of possible pairs
    return count;
 
# Driver code
if __name__ == "__main__" :
 
    S = 9; X = 5;
 
    # Function call
    print(count_all_possible_pair(S, X));
 
    # This code is contributed by AnkThon

// C# code to implement the approach
using System;
public class GFG {
 
  // Function to calculate
  // total number of possible pairs
  static int count_all_possible_pair(int sum_value,
                                     int xor_value)
  {
    double and_value
      = ((sum_value - xor_value) / 2.0);
 
    // If and value is not an integer
    // then no pair is possible
    int check = (int)and_value;
    if (check != and_value)
      return 0;
 
    int count = 1;
 
    // Traversing the bits of the sum_value
    // from MSB position
    for (int i = 1; i <= 32; i++) {
      int and_bit = (check >> i) & 1;
      int xor_bit = (xor_value >> i) & 1;
 
      Console.WriteLine("value:" + i);
      Console.WriteLine(and_bit+"test"+xor_bit);
      // If both the bit is 0, only 1 possibility
      if (and_bit == 0 && xor_bit == 0)
        count = count * 1;
 
      // If Xor bit is 0 and And bit 1,
      // then only 1 possibility
      else if (xor_bit == 0 && and_bit == 1)
        count = count * 1;
 
      // If Xor bit is 1, And bit is 0,
      // then there are 2 possibilities
      else if (xor_bit == 1 && and_bit == 0)
        count = count * 2;
 
      // If Xor bit and And bit both 1,
      // no such case is possible
      else
        return 0;
    }
 
    // Return the count of possible pairs
    return count;
  }
 
  // Driver code
  public static void Main ()
  {
    int S = 9, X = 5;
 
    // Function call
    Console.Write(count_all_possible_pair(S, X));
  }
}
 
// This code is contributed by gfgking

// JavaScript code to implement the approach
 
// Function to calculate
// total number of possible pairs
function count_all_possible_pair(sum_value, xor_value)
{
    var and_value = Math.floor((sum_value - xor_value) / 2.0);
 
    // If and value is not an integer
    // then no pair is possible
    var check = and_value;
    if (check != and_value)
        return 0;
 
    var count = 1;
 
    // Traversing the bits of the sum_value
    // from MSB position
    for (var i = 1; i <= 32; i++) {
        var and_bit = (check >> i) & 1;
        var xor_bit = (xor_value >> i) & 1;
 
        // If both the bit is 0, only 1 possibility
        if (and_bit == 0 && xor_bit == 0)
            count = count * 1;
 
        // If Xor bit is 0 and And bit 1,
        // then only 1 possibility
        else if (xor_bit == 0 && and_bit == 1)
            count = count * 1;
 
        // If Xor bit is 1, And bit is 0,
        // then there are 2 possibilities
        else if (xor_bit == 1 && and_bit == 0)
            count = count * 2;
 
        // If Xor bit and And bit both 1,
        // no such case is possible
        else
            return 0;
    }
 
    // Return the count of possible pairs
    return count;
}
 
// Driver code
var S = 9;
var X = 5;
 
// Function call
document.write(count_all_possible_pair(S, X));
 
// This code is contributed by phasing17

4

Complejidad de tiempo: O(N) donde N es el número de bits en la suma dada S
Espacio auxiliar: O(1)