How do you implement XOR using +-*/ ?

Question

How can the XOR operation (on two 32 bit ints) be implemented using only basic arithmetic operations? Do you have to do it bitwise after dividing by each power of 2 in turn, or is there a shortcut? I don't care about execution speed so much as about the simplest, shortest code.

Edit: This is not homework, but a riddle posed on a hacker.org. The point is to implement XOR on a stack-based virtual machine with very limited operations (similar to the brainfuck language and yes - no shift or mod). Using that VM is the difficult part, though of course made easier by an algorithm that is short and simple.

While FryGuy's solution is clever, I'll have to go with my original ideal (similar to litb's solution) because comparisons are difficult to use as well in that environment.

Answer 1

I'm sorry i only know the straight forward one in head:

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;
}

The alternative in comments can be used instead of the if to avoid branching. But then again, the solution isn't exactly fast either and it makes it look stranger :)

Answer 2

I don't know whether this defeats the point of your question, but you can implement XOR with AND, OR, and NOT, like this:

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

In english, that's "a or b, but not a and b", which maps precisely to the definition of XOR.

Of course, I'm not sticking strictly to your stipulation of using only the arithmetic operators, but at least this a simple, easy-to-understand reimplementation.

Answer 3

It's easier if you have the AND because

A OR B = A + B - (A AND B)

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

Answer 4

I would do it the simple way:

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;

There might be an easier way, but I don't know of one.