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

Bracelet

Answer 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

Mudcat

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

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

@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#. – Volcanic

@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. – Valence

Answer 2

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

Prisca

I love it. Very simple and understandable. – Rabelais

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

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

Answer 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)

Leyba

Answer 4

Another possibility:

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

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

Sacrarium

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. – Osber

@Osber I assume you know about code golf, but if you didn't here you go. – Madelle

Answer 5

Better yet on Python:

result = (1 if a else 0)+(1 if b else 0)+(1 if c else 0) == 1

This can be used also on if statements!

It saved my day for CLI mutually exclusive arguments through Click (everyone hates click)

Mope

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

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

Answer 6

You could also try (in C):

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

Valence

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. – Lauryn

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

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 – Lauryn

Answer 7

Here's a general implementation that fails quickly when more than one bool is found to be true.

Usage:

XOR(a, b, c);

Code:

public static bool XOR(params bool[] bools)
{
    return bools.Where(b => b).AssertCount(1);
}

public static bool AssertCount<T>(this IEnumerable<T> source, int countToAssert)
{
    int count = 0;
    foreach (var t in source)
    {
        if (++count > countToAssert) return false;
    }

    return count == countToAssert;
}

Micheal

Answer 8

f= lambda{ |a| [false, false, true].permutation.to_a.uniq.include? a }
p f.call([false, true, false])
p f.call([false, true, true])

$ true

$ false

Because I can.

Golgi

Answer 9

In C:

#include <stdbool.h>

bool array_xor(size_t array_size, bool[] array) {
    int count = 0;

    for (int i = 0; i < array_size && count < 2; i++) {
        if (array[i]) {
            count++;
        }
    }

    return count == 1;
}

Koger

I'm not sure this works, nor is it simple. – Bedplate

Define "simple". It definitely works, as what it's doing is checking that exactly one element of the array is true. It works for an arbitrarily large array of booleans, not just 3 elements, and short circuits as soon as it finds a second element that is true (hence && count < 2). – Koger

Answer 10

result = ( BOOL_TO_INT( a) + BOOL_TO_INT ( b ) + BOOL_TO_INT ( c ) ) = 1

Tutelary

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Immunity