XOR of three values

Question

What is the simplest way to do a three-way exclusive OR?

In other words, I have three values, and I want a statement that evaluates to true IFF only one of the three values is true.

So far, this is what I've come up with:

((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))

Is there something simpler to do the same thing?

---

Here's the proof that the above accomplishes the task:

a = true; b = true; c = true
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> false

a = true; b = true; c = false
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> false

a = true; b = false; c = true
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> false

a = true; b = false; c = false
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> true

a = false; b = true; c = true
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> false

a = false; b = true; c = false
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> true

a = false; b = false; c = true
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> true

a = false; b = false; c = false
((a ^ b) && (a ^ c) && !(b && c)) || ((b ^ a) && (b ^ c) && !(a && c)) || ((c ^ a) && (c ^ b) && !(a && b))
=> false

Solution 1

For exactly three terms, you can use this expression:

(a ^ b ^ c) && !(a && b && c)

The first part is true iff one or three of the terms are true. The second part of the expression ensures that not all three are true.

Note that the above expression does NOT generalize to more terms. A more general solution is to actually count how many terms are true, so something like this:

int trueCount =
   (a ? 1 : 0) +
   (b ? 1 : 0) +
   (c ? 1 : 0) +
   ... // more terms as necessary 

return (trueCount == 1); // or some range check expression etc

Solution 2

bool result = (a?1:0)+(b?1:0)+(c?1:0) == 1;

Solution 3

a^b^c is only 1 if an uneven number of variables is 1 (two '1' would cancel each other out). So you just need to check for the case "all three are 1":

result = (a^b^c) && !(a&&b&&c)

Solution 4

Another possibility:

a ? !b && !c : b ^ c

which happens to be 9 characters shorter than the accepted answer :)

Solution 5

You could also try (in C):

!!a + !!b + !!c == 1

View more solutions

Comments

[Aaron D]

I love it. Very simple and understandable.

[Ani]

Great, but the general solution does not short-circuit.

[kaspersky]

a ? 1 : 0 can be simplified to !!a

[blgt]

This is only valid in some languages [eg. javascript], and it's not a simplification. In a language which auto-converts boolean to number for +, if a, b, and c are already boolean, you also don't need the double negation !!: just a+b+c===1 will be equivalent.

[kaspersky]

@blgt, my mistake, I should specify that I meant to be an answer for C language.

[blgt]

Using !! to guarantee a C true is 1 is actually pretty neat. A bit paranoid in the context of a boolean logic question though. If the rest of your code is well-written a+b+c==1 should still be sufficient

[gerardw]

The simplest and must understandable when reading the code (well, I'd add few spaces)

[Drew Noakes]

@gg.kaspersky, only in JavaScript, C, and languages which have truthy/falsy tests via the ! operator. For example, this wouldn't work in Java or C#.

[kaspersky]

@DrewNoakes, when I made the comment, I thought for some reason that the question was C specific. Indeed, certain syntax constructs are valid only in certain languages.

[Vlasec]

Kinda glad this is not the accepted answer for readability reasons, but still, I had to upvote as shortness still has some kinky appeal to me. On university in C class, we had a contest in writing the shortest source code that generates a song similar to Heidis Kuken, and I was in TOP 5 in a contest.

[Drdilyor]

python converts bool to int, so result = bool(a) + bool(b) + bool(c) == 1

[Pier Carlo Cadoppi]

and if a, b and c are already booleans, you can simply say result = a + b + c == 1

[Jivan Pal]

In Haskell: list_xor xs = sum ( map (\x -> if x then 1 else 0) xs ) == 1