How do I determine if *exactly* one boolean is true, without type conversion?

Question

Given an arbitrary list of booleans, what is the most elegant way of determining that exactly one of them is true?

The most obvious hack is type conversion: converting them to 0 for false and 1 for true and then summing them, and returning sum == 1.

I'd like to know if there is a way to do this without converting them to ints, actually using boolean logic.

(This seems like it should be trivial, idk, long week)

Edit: In case it wasn't obvious, this is more of a code-golf / theoretical question. I'm not fussed about using type conversion / int addition in PROD code, I'm just interested if there is way of doing it without that.

Edit2: Sorry folks it's a long week and I'm not explaining myself well. Let me try this:

In boolean logic, ANDing a collection of booleans is true if all of the booleans are true, ORing the collection is true if least one of them is true. Is there a logical construct that will be true if exactly one boolean is true? XOR is this for a collection of two booleans for example, but any more than that and it falls over.

Solution 1

With plain boolean logic, it may not be possible to achieve what you want. Because what you are asking for is a truth evaluation not just based on the truth values but also on additional information(count in this case). But boolean evaluation is binary logic, it cannot depend on anything else but on the operands themselves. And there is no way to reverse engineer to find the operands given a truth value because there can be four possible combinations of operands but only two results. Given a false, can you tell if it is because of F ^ F or T ^ T in your case, so that the next evaluation can be determined based on that?.

Solution 2

You can actually accomplish this using only boolean logic, although there's perhaps no practical value of that in your example. The boolean version is much more involved than simply counting the number of true values.

Anyway, for the sake of satisfying intellectual curiosity, here goes. First, the idea of using a series of XORs is good, but it only gets us half way. For any two variables x and y,

x ⊻ y

is true whenever exactly one of them is true. However, this does not continue to be true if you add a third variable z,

x ⊻ y ⊻ z

The first part, x ⊻ y, is still true if exactly one of x and y is true. If either x or y is true, then z needs to be false for the whole expression to be true, which is what we want. But consider what happens if both x and y are true. Then x ⊻ y is false, yet the whole expression can become true if z is true as well. So either one variable or all three must be true. In general, if you have a statement that is a chain of XORs, it will be true if an uneven number of variables are true.

Since one is an uneven number, this might prove useful. Of course, checking for an uneven number of truths is not enough. We additionally need to ensure that no more than one variable is true. This can be done in a pairwise fashion by taking all pairs of two variables and checking that they are not both true. Taken together these two conditions ensure that exactly one if the variables are true.

Below is a small Python script to illustrate the approach.

from itertools import product

print("x|y|z|only_one_is_true")
print("======================")
for x, y, z in product([True, False], repeat=3):
    uneven_number_is_true = x ^ y ^ z
    max_one_is_true = (not (x and y)) and (not (x and z)) and (not (y and z))
    only_one_is_true = uneven_number_is_true and max_one_is_true
    print(int(x), int(y), int(z), only_one_is_true)

And here's the output.

x|y|z|only_one_is_true
======================
1 1 1 False
1 1 0 False
1 0 1 False
1 0 0 True
0 1 1 False
0 1 0 True
0 0 1 True
0 0 0 False

Solution 3

After your clarification, here it is with no integers.

 bool IsExactlyOneBooleanTrue( bool *boolAry, int size )
    {
      bool areAnyTrue = false;
      bool areTwoTrue = false;
      for(int i = 0; (!areTwoTrue) && (i < size); i++) {
        areTwoTrue = (areAnyTrue && boolAry[i]);
        areAnyTrue |= boolAry[i];
      }
      return ((areAnyTrue) && (!areTwoTrue));
    }

Solution 4

Sure, you could do something like this (pseudocode, since you didn't mention language):

found = false;
alreadyFound = false;
for (boolean in booleans):
    if (boolean):
        found = true;
        if (alreadyFound):
            found = false;
            break;
        else:
            alreadyFound = true;
return found;

Solution 5

No-one mentioned that this "operation" we're looking for is shortcut-able similarly to boolean AND and OR in most languages. Here's an implementation in Java:

public static boolean exactlyOneOf(boolean... inputs) {
    boolean foundAtLeastOne = false;
    for (boolean bool : inputs) {
        if (bool) {
            if (foundAtLeastOne) {
                // found a second one that's also true, shortcut like && and ||
                return false;
            }
            foundAtLeastOne = true;
        }
    }
    // we're happy if we found one, but if none found that's less than one
    return foundAtLeastOne;
}

View more solutions