Contar valores cuyo Bitwise OR con A es igual a B

Dados dos enteros A y B , la tarea es contar los posibles valores de X que satisfagan la condición A | X = segundo .
Nota: | representa la operación OR bit a bit .

Ejemplos:

Entrada: A = 2, B = 3
Salida: 2
Explicación:
Dado que, 2 | 1 = 3 y 2 | 3 = 3. Por lo tanto, los posibles valores de x son 1 y 3.

Entrada: A = 5, B = 7
Salida: 4

Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre el rango [1, B] y verificar para cada número, si su Bitwise OR con A es igual a B. Si se cumple la condición, incremente el conteo.
Complejidad temporal: O(b)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

• Convierta los números A y B en sus respectivas representaciones binarias .

Tabla de verdad de la operación OR bit a bit:
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

• Para cada bit con la misma posición, cuente el número de formas en que el i ^-ésimo bit de A se puede convertir en el i ^-ésimo bit de B realizando una operación OR bit a bit .



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

• Inicialice una variable y almacene el resultado requerido.
• Atraviesa los bits de a y b simultáneamente usando la variable i
  • Si el i-ésimo bit de a está activado y el i-ésimo bit de b también está activado, entonces el i-ésimo bit de x puede tomar 2 valores, es decir, 0 o 1. Por lo tanto, multiplique la respuesta por 2.
  • Si el i-ésimo bit de a no está configurado y el i-ésimo bit de b está configurado, entonces el i-ésimo bit de x puede tomar solo 1 valor, es decir, 1. Por lo tanto, multiplique la respuesta por 1.
  • Si el i-ésimo bit de a está establecido y el i-ésimo bit de b no está establecido, no importa cuál sea el i-ésimo bit de x , el i-ésimo bit de a no se puede convertir en el i-ésimo bit de b . Por lo tanto, actualice ans a 0 y salga del bucle .
• Imprime el valor de ans 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 possible values of // X whose Bitwise OR with A is equal to B int numWays(int a, int b) {        // Store the required result     int res = 1;        // Iterate over all bits     while (a && b) {            // If i-th bit of a is set         if ((a & 1) == 1) {                // If i-th bit of b is set             if ((b & 1) == 1) {                    // The i-th bit in x                 // can be both 1 and 0                 res = res * 2;             }             else {                    // a|x is equal to 1                 // Therefore, it cannot                 // be converted to b                 return 0;             }         }            // Right shift a and b by 1         a = a >> 1;         b = b >> 1;     }        return res; }    // Driver Code int main() {     // Given Input     int a = 2, b = 3;        // Function Call     cout << numWays(a, b);        return 0; }

Producción:

2

Complejidad de tiempo: O(max(log a, log b))
Espacio auxiliar: O(1)