language-agnostic - operator - different than in c

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

Question

¿Cómo se puede implementar la operación XOR (en dos entradas de 32 bits) usando 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, sino un acertijo planteado en 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 cambio o mod). 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 haría de la manera más simple:

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 sé de ninguna.

Answer 2

Lo siento, solo sé el directo 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 comentarios se puede usar en lugar del if para evitar la bifurcación. Pero, de nuevo, la solución tampoco es exactamente rápida y hace que parezca extraño :)

Answer 3

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

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

En inglés, eso es "a o b, pero no a y b", que se corresponde exactamente con la definición de XOR.

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

Answer 4

Es más fácil si tienes el AND 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);
}