¿Cómo implementa XOR usando + - * /?

Question

¿Cómo se puede implementar la operación XOR (en dos entradas de 32 bits) utilizando solo operaciones aritméticas básicas? ¿Tienes que hacerlo en bit a bit después de dividir por cada potencia de 2 por turno, o hay un atajo? No me importa tanto la velocidad de ejecución como el código más simple y corto.

Editar: Esto no es tarea, pero un enigma que plantea en una hacker.org. El objetivo es implementar XOR en una máquina virtual basada en pila con operaciones muy limitadas (similar al lenguaje brainfuck y sí, sin desplazamiento o modificación). Usar esa máquina virtual es la parte difícil, aunque, por supuesto, es más fácil gracias a un algoritmo breve y simple.

Si bien la solución de FryGuy es inteligente, tendré que ir con mi ideal original (similar a la solución de litb) porque las comparaciones son difíciles de usar también en ese entorno.

Answer 1

lo siento yo sólo sé que el sencillo una en la cabeza:

uint32_t mod_op(uint32_t a, uint32_t b) { 
    uint32_t int_div = a/b; 
    return a - (b * int_div); 
} 

uint32_t xor_op(uint32_t a, uint32_t b) { 
    uint32_t n = 1u; 
    uint32_t result = 0u; 
    while(a != 0 || b != 0) { 
     // or just: result += n * mod_op(a - b, 2); 
     if(mod_op(a, 2) != mod_op(b, 2)) { 
      result += n; 
     } 
     a /= 2; 
     b /= 2; 
     n *= 2; 
    } 
    return result; 
} 

La alternativa en los comentarios se puede utilizar en lugar del caso para evitar la ramificación. Pero, de nuevo, la solución tampoco es exactamente rápida y lo hace parecer extraño :)

Answer 2

No sé si esto derrota el punto de su pregunta, pero puede implementar XOR con Y, O, y NO , de esta manera:

uint xor(uint a, uint b) { 
    return (a | b) & ~(a & b); 
} 

En Inglés, que es "a o B, pero no a y b", que mapea con precisión a la definición de XOR.

Por supuesto, no me estoy apegando estrictamente a su estipulación de usar solo operadores aritméticos, pero al menos esta es una reimplementación simple y fácil de entender.

Answer 3

Es más fácil si usted tiene la Y porque

A o B = A + B - (A y B)

A XOR B = A + B - 2 (A y B)

int customxor(int a, int b) 
{ 
    return a + b - 2*(a & b); 
} 

Answer 4

lo haría de la forma más sencilla:

uint xor(uint a, uint b):  

uint ret = 0; 
uint fact = 0x80000000; 
while (fact > 0) 
{ 
    if ((a >= fact || b >= fact) && (a < fact || b < fact)) 
     ret += fact; 

    if (a >= fact) 
     a -= fact; 
    if (b >= fact) 
     b -= fact; 

    fact /= 2; 
} 
return ret; 

puede haber una manera más fácil, pero no lo sé de uno.