CODEWITHSUNDEEP
boolean-expression
Vilx-
Vilx-

Reputation: 107012

How to write the following boolean expression?

I've got three boolean values A, B and C. I need to write an IF statement which will execute if and only if no more than one of these values is True. In other words, here is the truth table:

 A | B | C | Result
---+---+---+--------
 0 | 0 | 0 |   1
 0 | 0 | 1 |   1
 0 | 1 | 0 |   1
 0 | 1 | 1 |   0
 1 | 0 | 0 |   1
 1 | 0 | 1 |   0
 1 | 1 | 0 |   0
 1 | 1 | 1 |   0

What is the best way to write this? I know I can enumerate all possibilities, but that seems... too verbose. :P

Added: Just had one idea:

!(A && B) && !(B && C) && !(A && C)

This checks that no two values are set. The suggestion about sums is OK as well. Even more readable maybe...

(A?1:0) + (B?1:0) + (C?1:0) <= 1

P.S. This is for production code, so I'm going more for code readability than performance.

Added 2: Already accepted answer, but for the curious ones - it's C#. :) The question is pretty much language-agnostic though.

Upvotes: 1

Views: 3991

Answers (11)

recursive
recursive

Reputation: 86144

There are many answers here, but I have another one!

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

Upvotes: 2

David Hedlund
David Hedlund

Reputation: 129832

how about treating them as integer 1's and 0's, and checking that their sum equals 1?

EDIT:

now that we know that it's c#.net, i think the most readable solution would look somewhat like

public static class Extensions
{
    public static int ToInt(this bool b)
    {
        return b ? 1 : 0;
    }
}

the above tucked away in a class library (appcode?) where we don't have to see it, yet can easily access it (ctrl+click in r#, for instance) and then the implementation will simply be: 

public bool noMoreThanOne(params bool[] bools) 
{ 
    return bools.ToList().Sum(b => b.ToInt()) <= 1; 
}

...

bool check = noMoreThanOne(true, true, false, any, amount, of, bools);

Upvotes: 11

Dave Gamble
Dave Gamble

Reputation: 4174

Code demonstration of d's solution:

int total=0;
if (A) total++;
if (B) total++;
if (C) total++;

if (total<=1) // iff no more than one is true.
{
    // execute

}

Upvotes: 0

Matt Howells
Matt Howells

Reputation: 41296

I'd go for maximum maintainability and readability.

static bool ZeroOrOneAreTrue(params bool[] bools)
{
    return NumThatAreTrue(bools) <= 1;
}

static int NumThatAreTrue(params bool[] bools)
{
    return bools.Where(b => b).Count();
}

Upvotes: 3

plinth
plinth

Reputation: 49199

I like the addition solution, but here's a hack to do that with bit fields as well.

inline bool OnlyOneBitSet(int x)
{
    // removes the leftmost bit, if zero, there was only one set.
    return x & (x-1) == 0;
}

// macro for int conversion
#define BOOLASINT(x) ((x)?1:0)

// turn bools a, b, c into the bit field cba
int i = (BOOLASINT(a) << 0) | BOOLASINT(b) << 1 | BOOLASINT(c) << 2;

if (OnlyOneBitSet(i)) { /* tada */ }

Upvotes: 0

Guffa
Guffa

Reputation: 700730

If you turn the logic around, you want the condition to be false if you have any pair of booleans that are both true:

if (! ((a && b) || (a && c) || (b && c))) { ... }

For something completely different, you can put the booleans in an array and count how many true values there are:

if ((new bool[] { a, b, c }).Where(x => x).Count() <= 1) { ... }

Upvotes: 3

Swan
Swan

Reputation:

Depends whether you want something where it's easy to understand what you're trying to do, or something that's as logically simple as can be. Other people are posting logically simple answers, so here's one where it's more clear what's going on (and what the outcome will be for different inputs):

  def only1st(a, b, c):
    return a and not b and not c

  if only1st(a, b, c) or only1st(b, a, c) or only1st(c, a, b):
    print "Yes"
  else:
    print "No"

Upvotes: 0

Martin B
Martin B

Reputation: 24180

A general way of finding a minimal boolean expression for a given truth table is to use a Karnaugh map:

http://babbage.cs.qc.edu/courses/Minimize/

There are several online minimizers on the web. The one here (linked to from the article, it's in German, though) finds the following expression:

(!A && !B) || (!A && !C) || (!B && !C)

If you're going for code readability, though, I would probably go with the idea of "sum<=1". Take care that not all languages guarantee that false==0 and true==1 -- but you're probably aware of this since you've taken care of it in your own solution.

Upvotes: 1

Vicky
Vicky

Reputation: 13244

(A XOR B XOR C) OR NOT (A OR B OR C)

Edit: As pointed out by Vilx, this isn't right.

If A and B are both 1, and C is 0, A XOR B will be 0, the overall result will be 0.

How about: NOT (A AND B) AND NOT (A AND C) AND NOT (B AND C)

Upvotes: 6

Swanand
Swanand

Reputation: 12426

Good ol' logic:

+ = OR
. = AND

R = Abar.Bbar.Cbar + Abar.Bbar.C + Abar.B.Cbar + A.Bbar.Cbar
  = Abar.Bbar.(Cbar + C) + Abar.B.Cbar + A.Bbar.Cbar
  = Abar.Bbar + Abar.B.Cbar + A.Bbar.Cbar
  = Abar.Bbar + CBar(A XOR B)
  = NOT(A OR B) OR (NOT C AND (A XOR B))

Take the hint and simplify further if you want.

And yeah, get your self familiar with Karnaugh Maps

Upvotes: 0

Pasi Savolainen
Pasi Savolainen

Reputation: 2500

You shold familiarize yourself with Karnaugh maps. Concept is most often applied to electronics but is very useful here too. It's very easy (thought Wikipedia explanation does look long -- it's thorough).

Upvotes: 9

Related Questions