Maximiza la expresión (A AND X) * (B AND X) | Manipulación de bits

Dados dos enteros positivos A y B tales que A != B , la tarea es encontrar un entero positivo X que maximice la expresión (A AND X) * (B AND X) .
Ejemplo: 
 

Entrada: A = 9 B = 8 
Salida: 8 
(9 Y 8) * (8 Y 8) = 8 * 8 = 64 (máximo posible)
Entrada: A = 11 y B = 13 
Salida: 9 
 

Enfoque ingenuo: uno puede ejecutar un ciclo de 1 a max (A, B) y puede encontrar fácilmente X que maximiza la expresión dada.
Enfoque eficiente: Se sabe que, 
 

(a – b) ² ≥ 0 
lo que implica (a + b) ² – 4*a*b ≥ 0 
lo que implica a * b ≤ (a + b) ² / 4
Por lo tanto, concluye que a * b será máximo cuando a * b = (a + b) 2/4 ^lo 
que implica a = b 
Del resultado anterior, (A Y X) * (B Y X) será máximo cuando (A Y X) = (B Y X) 
 

Ahora X se puede encontrar como: 
 

A = 11 = 1011 
B = 13 = 1101 
X = ? = abcd
En el 0° lugar: (1 Y d) = (1 Y d) implica d = 0, 1 pero para maximizar (A Y X) * (B Y X) d = 1 
En el 1° lugar: (1 Y d) = (0 Y d) implica c = 0 
En segundo lugar: (0 Y d) = (1 Y d) implica b = 0 
En 3er lugar: (1 Y d) = (1 Y d) implica a = 0, 1 pero para maximizar (A Y X) * (B Y X) a = 1
Por lo tanto, X = 1001 = 9 
 

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 32
 
// Function to find X according
// to the given conditions
int findX(int A, int B)
{
    int X = 0;
 
    // int can have 32 bits
    for (int bit = 0; bit < MAX; bit++) {
 
        // Temporary ith bit
        int tempBit = 1 << bit;
 
        // Compute ith bit of X according to
        // given conditions
        // Expression below is the direct
        // conclusion from the illustration
        // we had taken earlier
        int bitOfX = A & B & tempBit;
 
        // Add the ith bit of X to X
        X += bitOfX;
    }
 
    return X;
}
 
// Driver code
int main()
{
    int A = 11, B = 13;
 
    cout << findX(A, B);
 
    return 0;
}

// C implementation of the approach
#include <stdio.h>
 
#define MAX 32
 
// Function to find X according
// to the given conditions
int findX(int A, int B)
{
    int X = 0;
 
    // int can have 32 bits
    for (int bit = 0; bit < MAX; bit++) {
 
        // Temporary ith bit
        int tempBit = 1 << bit;
 
        // Compute ith bit of X according to
        // given conditions
        // Expression below is the direct
        // conclusion from the illustration
        // we had taken earlier
        int bitOfX = A & B & tempBit;
 
        // Add the ith bit of X to X
        X += bitOfX;
    }
 
    return X;
}
 
// Driver code
int main()
{
    int A = 11, B = 13;
    printf("%d", findX(A, B));
    return 0;
}
 
// This code is contributed by phalasi.

// Java implementation of the approach
class GFG
{
static int MAX = 32;
 
// Function to find X according
// to the given conditions
static int findX(int A, int B)
{
    int X = 0;
 
    // int can have 32 bits
    for (int bit = 0; bit < MAX; bit++)
    {
 
        // Temporary ith bit
        int tempBit = 1 << bit;
 
        // Compute ith bit of X according to
        // given conditions
        // Expression below is the direct
        // conclusion from the illustration
        // we had taken earlier
        int bitOfX = A & B & tempBit;
 
        // Add the ith bit of X to X
        X += bitOfX;
    }
    return X;
}
 
// Driver code
public static void main(String []args)
{
    int A = 11, B = 13;
 
    System.out.println(findX(A, B));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
MAX = 32
 
# Function to find X according
# to the given conditions
def findX(A, B) :
 
    X = 0;
 
    # int can have 32 bits
    for bit in range(MAX) :
 
        # Temporary ith bit
        tempBit = 1 << bit;
 
        # Compute ith bit of X according to
        # given conditions
        # Expression below is the direct
        # conclusion from the illustration
        # we had taken earlier
        bitOfX = A & B & tempBit;
 
        # Add the ith bit of X to X
        X += bitOfX;
 
    return X;
 
# Driver code
if __name__ == "__main__" :
     
    A = 11; B = 13;
    print(findX(A, B));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
static int MAX = 32;
 
// Function to find X according
// to the given conditions
static int findX(int A, int B)
{
    int X = 0;
 
    // int can have 32 bits
    for (int bit = 0; bit < MAX; bit++)
    {
 
        // Temporary ith bit
        int tempBit = 1 << bit;
 
        // Compute ith bit of X according to
        // given conditions
        // Expression below is the direct
        // conclusion from the illustration
        // we had taken earlier
        int bitOfX = A & B & tempBit;
 
        // Add the ith bit of X to X
        X += bitOfX;
    }
    return X;
}
 
// Driver code
public static void Main(String []args)
{
    int A = 11, B = 13;
 
    Console.WriteLine(findX(A, B));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to find X according
// to the given conditions
function findX( A,  B)
{
    var X = 0;
    var MAX = 32;
 
   
    // int can have 32 bits
    for (var bit = 0; bit < MAX; bit++)
    {
   
        // Temporary ith bit
         
        var tempBit = 1 << bit;
   
        // Compute ith bit of X according to
        // given conditions
        // Expression below is the direct
        // conclusion from the illustration
        // we had taken earlier
         
        var bitOfX = A & B & tempBit;
   
        // Add the ith bit of X to X
        X += bitOfX;
    }
    return X;
}
   
// Driver code
    var A = 11, B = 13;
    document.write(findX(A, B));
   
  // This code is contributed by bunnyram19.
</script>

9

Complejidad de tiempo: O (MAX)

Espacio Auxiliar: O(1)