Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do you implement XOR using +-*/?

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.

like image 351
Michael Borgwardt Avatar asked Dec 17 '08 00:12

Michael Borgwardt


People also ask

How does XOR work with 3 inputs?

For 3 or more inputs, the XOR gate has a value of 1when there is an odd number of 1's in the inputs, otherwise, it is a 0. Notice also that the truth tables for the 3-input XOR and XNOR gates are identical.

How does an XOR gate function?

The XOR ( exclusive-OR ) gate acts in the same way as the logical "either/or." The output is "true" if either, but not both, of the inputs are "true." The output is "false" if both inputs are "false" or if both inputs are "true."


2 Answers

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.

like image 157
FryGuy Avatar answered Oct 01 '22 20:10

FryGuy


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.

like image 38
benjismith Avatar answered Oct 01 '22 19:10

benjismith