Algoritmo para encontrar una solución para A xor X = B + X

46

Dado el entero A y B, encuentre el entero X para que:

  • A, B <2 * 1e18
  • A xor X = B + X

Dudo mucho que sea posible resolver esta ecuación usando las matemáticas. Este es un problema de codificación que encontré hace 3 años e incluso ahora no puedo resolverlo por mí mismo.

Mi código hasta ahora: (esta es la solución de fuerza bruta)

#include <iostream>

using namespace std;

int main()
{

    unsigned long long a, b;
    cin >> a >> b;
    for (unsigned long long x = 1; x < max(a, b); x++) {
        unsigned long long c = a ^ x;
        unsigned long long d = b + x;
        if (c == d) {
            cout << x << endl;
            break;
            return 0;
        }
    }

    cout << -1; //if no such integer exists

    return 0;
}
AAaAa
fuente
11
Si lees un poco más sobre exclusividad o deberías encontrar la equivalencia algebraica a xor b = a + b mod 2. Intenta pensar en esa equivalencia por un tiempo.
Algún tipo programador el
16
@Someprogrammerdude Eso es si a y b son variables booleanas, es decir, 0 o 1, y xor es un xor booleano. ¿Cuál es la conexión con bitwise xor?
John Kugelman
1
fwiw, creo que usar la fuerza bruta aquí es el camino a seguir a menos que quieras escribir algo que pueda probar ecuaciones más generales. Considere que debe probar su código para asegurarse de que sea correcto y que lo más fácil sería probarlo con un algoritmo de fuerza bruta, pero luego puede usar la fuerza bruta en primer lugar. Por otro lado, la aplicación de las matemáticas eventualmente hará que no sea necesario ejecutar ningún código.
idclev 463035818
1
@molbdnilo Oh, uno de los comentarios sugirió que a xor b = a + b mod 2 y pensé que también se refería a enteros. Eliminaré esa parte de mi publicación.
AAaAa
1
@JohnKugelman Se refería mod 2a la matemática (mod 2), es decir, 3 === 7 (mod 2). El punto es que puedes descubrir una ecuación para el primer bit de X, luego pasar al siguiente bit donde (respetando el carry) obtienes una ecuación para el segundo bit, etc., como la respuesta de Daniel.
Max Langhof

Respuestas:

45

Tenga en cuenta que A + X == (A xor X) + ((A and X)<<1). Entonces:

A xor X = A + X - ((A and X)<<1) = B + X
A - B = (A and X)<<1

Y tenemos:

(A - B) and not (A<<1) = 0    (All bits in (A - B) are also set in (A<<1))
(A - B)>>1 = A and X

Si se cumple la condición, para cualquier número entero Y que no tenga bits establecidos en A, (((A - B) >> 1) o Y) es una solución. Si solo desea una solución, puede usar ((A - B) >> 1), donde Y = 0. De lo contrario, no hay solución.

int solve(int a, int b){
    int x = (a - b) >> 1;
    if ((a ^ x) == b + x)
        return x;
    else
        return ERROR;
}
usuario23013
fuente
15
+1. Esto es al notar que A xor Xes "suma sin llevar", y ((A and X)<<1)es "llevar en la adición". Como A + Xes "suma con carry", la primera ecuación tiene sentido.
justo el
3
(A and X)<<1es básicamente 2*(A and X)y porque esto es igual a A-Besto dice que el problema puede tener una solución solo si A y B son ambos eventos impares o ambos.
axiac
1
Pensé que tendría algo que ver con la resta, pero no llegué a esto a tiempo.
SS Anne
38

No es muy difícil, solo necesita pensar en pequeño: supongamos que estamos escribiendo A, By Xen binario, y Aᵢes el valor correspondiente al bit más a la derecha de 2 .

Sabemos que: Aₒ ⊕ Xₒ = Bₒ + Xₒ.

Usemos un ejemplo para descubrir cómo evaluar eso: A = 15 y B = 6. Convertir a binario:

A = 1 1 1 1           B = 0 1 1 0
X = a b c d           X = a b c d

Ahora tenemos algunas posibilidades. Analicemos los bits más a la derecha de A y B:

1  d = 0 + d

Sabemos que dsolo puede ser 0 o 1, así que:

for d = 0
1  d = 0 + d    =>    1  0 = 0 + 0    =>    1 = 0 (not possible)

for d = 1
1  d = 0 + d    =>    1  1 = 0 + 1    =>    0 = 1 (not possible)

Es notable que XOR se comporta como una suma binaria (con la diferencia de que XOR no crea un arrastre para la siguiente suma de bits):

    XOR           SUM
0  0 = 0  |   0 + 0 = 0
0  1 = 1  |   0 + 1 = 1
1  0 = 1  |   1 + 0 = 1
1  1 = 0  |   1 + 1 = 0

por lo que no siempre será posible encontrar una X que satisfaga A ⊕ X = B + X, porque no hay un valor dque satisfaga 1 + d = 0 + d.

De todos modos, si existe X, puede encontrarlo de esta manera, de derecha a izquierda, encontrando poco a poco.


EJEMPLO DE TRABAJO COMPLETO

A = 15, B = 7:

A = 1 1 1 1           B = 0 1 1 1
X = a b c d           X = a b c d

1  d = 1 + d 

Aquí, se aplican tanto d = 0 como d = 1, ¿entonces qué? Necesitamos verificar el siguiente bit. Supongamos que d = 1:

A = 1 1 1 1           B = 0 1 1 1
X = a b c d           X = a b c d

1  d = 1 + d    =>    1  1 = 1 + 1    =>    0 = 0 (possible)

BUT 1 + 1 = 0 generates a carryover for the next bit sum:

Instead of 1  c = 1 + c, we have 1  c = 1 + c (+1) =
                                   1  c = c  (not possible)

entonces en este caso, d debe ser 0.

carryover                              0
         A = 1 1 1 1           B = 0 1 1 1
         X = a b 0 0           X = a b 0 0
        -----------------------------------
                   0                     0

we know that c must be 0:

carryover                            0 0
         A = 1 1 1 1           B = 0 1 1 1
         X = a b 0 0           X = a b 0 0
        -----------------------------------
                 1 1                   1 1

pero que hay de b? necesitamos verificar el siguiente bit, como siempre:

if b = 0, there won't be a carryover, so we'll have:

1  a = 0 + a  (and this is not possible)

so we try b = 1:

1  b = 1 + b    =>    1  1 = 1 + 1    =>    0 = 0 (with carryover)

y ahora, por a:

carryover                          1 0 0
         A = 1 1 1 1           B = 0 1 1 1
         X = a 1 0 0           X = a 1 0 0
        -----------------------------------
               0 0 0                 0 0 0


1  a = 0 + a (+1)    =>    1  a = 1 + a

aquí apuede ser 0 y 1, pero debe ser 0, para evitar un arrastre en la suma B + X.

Entonces, X = 0 1 0 0entonces X = 4.


CÓDIGO

#include <iostream>
using namespace std;

inline int bit(int a, int n) {
    if(n > 31) return 0; 
    return (a & ( 1 << n )) >> n; 
}

int main(){
    int A = 19;
    int B = 7;

    int X = 0;
    int carryover = 0;
    int aCurrent, aNext, bCurrent, bNext;

    for(int i = 0; i < 32; i++){
        aCurrent =  bit(A, i);      bCurrent =  bit(B, i);
        aNext =     bit(A, i + 1);  bNext =     bit(B, i + 1);

        if(aCurrent == 0 && bCurrent == 0){
            if(carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
            }
            carryover = 0;
        }
        else if(aCurrent == 0 && bCurrent == 1){
            if(!carryover) {X = -1; break;}
            if(aNext == bNext){
                X += 1 << i;
            }
            carryover = 1;
        }
        else if(aCurrent == 1 && bCurrent == 0){
            if(!carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
                carryover = 1;
            }
            else {
                carryover = 0;
            }
        }
        else if(aCurrent == 1 && bCurrent == 1){
            if(carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
                carryover = 1;
            }
            else {
                carryover = 0;
            }
        }

    }

    if(X != -1) cout<<"X = "<<X<<endl;
    else cout<<"X doesnt exist"<<endl;

    return 0;
}

Puedes probarlo aquí .

Daniel
fuente