606

An interviewer recently asked me this question: given three boolean variables, a, b, and c, return true if at least two out of the three are true.

My solution follows:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    else{
        return false;
    }
}

He said that this can be improved further, but how?

19
  • 173
    Inline the return statement.
    – Finglas
    Jun 19, 2010 at 15:48
  • 82
    atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou) Jun 20, 2010 at 7:44
  • 6
    Thorbjørn: Doesn't C use zero/nonzero for bools? I don't think that would even work in C, e.g., atLeastTwo(0,2,0).
    – Ken
    Jun 20, 2010 at 14:52
  • 93
    Why do people upvote the most trivial questions? Jun 22, 2010 at 16:45
  • 52
    Questions that are general and easy to understand get a lot of up votes. Questions that are very specific and technical don't.
    – Jay
    Jun 23, 2010 at 17:37

65 Answers 65

843

Rather than writing:

if (someExpression) {
    return true;
} else {
    return false;
}

Write:

return someExpression;

As for the expression itself, something like this:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a ? (b || c) : (b && c);
}

or this (whichever you find easier to grasp):

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a && (b || c) || (b && c);
}

It tests a and b exactly once, and c at most once.

References

16
  • 150
    +1: lovely solution to the puzzle, but hopefully we don't see anything like this in the real world :)
    – Juliet
    Jun 19, 2010 at 16:02
  • 125
    @Juliet: I don't know, I think if this was a real-world requirement (with real variable names) it would read pretty well. Consider return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam), that looks fine to me. Jun 19, 2010 at 18:30
  • 18
    I don't think that looks bad, but if the requirement in the domain is understood to be "at least two", I think it'd be easier to read atLeastTwo(hasgoodAttendance, passedCoursework, passedExam). The idea of "at least 2 bools are true" is generic enough to deserve its own function.
    – Ken
    Jun 19, 2010 at 23:33
  • 18
    @Lese: Asking the most micro-optimized code in face to face interviews is impractical, and dare I say, useless. Micro-optimizations, when driven by the need, is guided by runtime profiling results, not human instincts (which are known to be terrible). You can certainly ask interviewees the process by which you'd optimize this further; that's more important than the result itself. Jun 20, 2010 at 6:05
  • 18
    The ternary operator is a common idiom that you should be able to read. If you can't read it you should study it until you can. Use of the ternary operator is not something I consider "clever" in the derogatory sense. But yes, I'd put this as the body of a method call if you're commonly using the "at least two" logic.
    – Stephen P
    Jun 22, 2010 at 0:14
510
+500

Just for the sake of using XOR to answer a relatively straight-forward problem...

return a ^ b ? c : a
13
  • 165
    Wow, cool solution. But for me its inverted version is easier to understand: a==b ? a : c
    – Rotsor
    Jun 22, 2010 at 15:50
  • 5
    a ^ b ? c : a ^ b ? c : a ^ b ? c : a Jun 22, 2010 at 23:39
  • 4
    Yay,..XOR gets such a bad press and you seldom get the chance to use it. Jul 16, 2010 at 15:46
  • 19
    @Stimul8d maybe because, for booleans, it's the same as != but less readable? Figuring that out was a eureka moment for me... Sep 10, 2010 at 7:45
  • 2
    I prefer the purely binary form: return ((a^b) & c) | (a & b). It is branch-less (faster) and easy to read : (a or b is true and c is true) or (a and b are both true). Note that (a|b) and (a^b) both work with this formula.
    – flanglet
    Apr 1, 2012 at 20:23
225

Why not implement it literally? :)

(a?1:0)+(b?1:0)+(c?1:0) >= 2

In C you could just write a+b+c >= 2 (or !!a+!!b+!!c >= 2 to be very safe).

In response to TofuBeer's comparison of java bytecode, here is a simple performance test:

class Main
{
    static boolean majorityDEAD(boolean a,boolean b,boolean c)
    {
        return a;
    }

    static boolean majority1(boolean a,boolean b,boolean c)
    {
        return a&&b || b&&c || a&&c;
    }

    static boolean majority2(boolean a,boolean b,boolean c)
    {
        return a ? b||c : b&&c;
    }

    static boolean majority3(boolean a,boolean b,boolean c)
    {
        return a&b | b&c | c&a;
    }

    static boolean majority4(boolean a,boolean b,boolean c)
    {
        return (a?1:0)+(b?1:0)+(c?1:0) >= 2;
    }

    static int loop1(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority1(data[i], data[j], data[k])?1:0; 
                sum += majority1(data[i], data[k], data[j])?1:0; 
                sum += majority1(data[j], data[k], data[i])?1:0; 
                sum += majority1(data[j], data[i], data[k])?1:0; 
                sum += majority1(data[k], data[i], data[j])?1:0; 
                sum += majority1(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop2(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority2(data[i], data[j], data[k])?1:0; 
                sum += majority2(data[i], data[k], data[j])?1:0; 
                sum += majority2(data[j], data[k], data[i])?1:0; 
                sum += majority2(data[j], data[i], data[k])?1:0; 
                sum += majority2(data[k], data[i], data[j])?1:0; 
                sum += majority2(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop3(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority3(data[i], data[j], data[k])?1:0; 
                sum += majority3(data[i], data[k], data[j])?1:0; 
                sum += majority3(data[j], data[k], data[i])?1:0; 
                sum += majority3(data[j], data[i], data[k])?1:0; 
                sum += majority3(data[k], data[i], data[j])?1:0; 
                sum += majority3(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop4(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority4(data[i], data[j], data[k])?1:0; 
                sum += majority4(data[i], data[k], data[j])?1:0; 
                sum += majority4(data[j], data[k], data[i])?1:0; 
                sum += majority4(data[j], data[i], data[k])?1:0; 
                sum += majority4(data[k], data[i], data[j])?1:0; 
                sum += majority4(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loopDEAD(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majorityDEAD(data[i], data[j], data[k])?1:0; 
                sum += majorityDEAD(data[i], data[k], data[j])?1:0; 
                sum += majorityDEAD(data[j], data[k], data[i])?1:0; 
                sum += majorityDEAD(data[j], data[i], data[k])?1:0; 
                sum += majorityDEAD(data[k], data[i], data[j])?1:0; 
                sum += majorityDEAD(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static void work()
    {
        boolean [] data = new boolean [10000];
        java.util.Random r = new java.util.Random(0);
        for(int i=0;i<data.length;i++)
            data[i] = r.nextInt(2) > 0;
        long t0,t1,t2,t3,t4,tDEAD;
        int sz1 = 100;
        int sz2 = 100;
        int sum = 0;

        t0 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop1(data, i, sz1, sz2);

        t1 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop2(data, i, sz1, sz2);

        t2 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop3(data, i, sz1, sz2);

        t3 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop4(data, i, sz1, sz2);

        t4 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loopDEAD(data, i, sz1, sz2);

        tDEAD = System.currentTimeMillis();

        System.out.println("a&&b || b&&c || a&&c : " + (t1-t0) + " ms");
        System.out.println("   a ? b||c : b&&c   : " + (t2-t1) + " ms");
        System.out.println("   a&b | b&c | c&a   : " + (t3-t2) + " ms");
        System.out.println("   a + b + c >= 2    : " + (t4-t3) + " ms");
        System.out.println("       DEAD          : " + (tDEAD-t4) + " ms");
        System.out.println("sum: "+sum);
    }

    public static void main(String[] args) throws InterruptedException
    {
        while(true)
        {
            work();
            Thread.sleep(1000);
        }
    }
}

This prints the following on my machine (running Ubuntu on Intel Core 2 + sun java 1.6.0_15-b03 with HotSpot Server VM (14.1-b02, mixed mode)):

First and second iterations:

a&&b || b&&c || a&&c : 1740 ms
   a ? b||c : b&&c   : 1690 ms
   a&b | b&c | c&a   : 835 ms
   a + b + c >= 2    : 348 ms
       DEAD          : 169 ms
sum: 1472612418

Later iterations:

a&&b || b&&c || a&&c : 1638 ms
   a ? b||c : b&&c   : 1612 ms
   a&b | b&c | c&a   : 779 ms
   a + b + c >= 2    : 905 ms
       DEAD          : 221 ms

I wonder, what could java VM do that degrades performance over time for (a + b + c >= 2) case.

And here is what happens if I run java with a -client VM switch:

a&&b || b&&c || a&&c : 4034 ms
   a ? b||c : b&&c   : 2215 ms
   a&b | b&c | c&a   : 1347 ms
   a + b + c >= 2    : 6589 ms
       DEAD          : 1016 ms

Mystery...

And if I run it in GNU Java Interpreter, it gets almost 100 times slower, but the a&&b || b&&c || a&&c version wins then.

Results from Tofubeer with the latest code running OS X:

a&&b || b&&c || a&&c : 1358 ms
   a ? b||c : b&&c   : 1187 ms
   a&b | b&c | c&a   : 410 ms
   a + b + c >= 2    : 602 ms
       DEAD          : 161 ms

Results from Paul Wagland with a Mac Java 1.6.0_26-b03-383-11A511

a&&b || b&&c || a&&c : 394 ms 
   a ? b||c : b&&c   : 435 ms
   a&b | b&c | c&a   : 420 ms
   a + b + c >= 2    : 640 ms
   a ^ b ? c : a     : 571 ms
   a != b ? c : a    : 487 ms
       DEAD          : 170 ms
20
  • 4
    a+b+c >= 2 : this doesn't work with negatives, right? You may have to do the !!a thing, I'm not sure. Jun 19, 2010 at 15:52
  • 8
    <s>-1. You should never do that for C. You don't know what the value of true is (it could just as easily be -1).</s> Actually I guess C99 includes in its standard that true is defined as 1. But I still wouldn't do this. Jun 19, 2010 at 15:52
  • 1
    Is that possible if your input is result of boolean operations? And is that possible for "bool" type in C++?
    – Rotsor
    Jun 19, 2010 at 15:58
  • 2
    @Rotsor: Nobody said the input has to be the result of boolean operations. Even without negatives you're playing with fire, as if you define it as 2 your condition would have false positives. But I don't care about that as much as I dislike the idea of intermingling booleans into arithmetic. Your Java solution is clear in that it does not rely on nuanced conversions from boolean to an integer type. Jun 19, 2010 at 16:05
  • 7
    Be cautious with microbenchmarks: java.sun.com/docs/hotspot/HotSpotFAQ.html#benchmarking_simple
    – BalusC
    Jun 19, 2010 at 20:32
159
return (a==b) ? a : c;

Explanation:

If a==b, then both are true or both are false. If both are true, we have found our two true booleans, and can return true (by returning a). If both are false there cannot be two true booleans even if c is true, so we return false (by returning a). That's the (a==b) ? a part. What about : c ? Well if a==b is false, then exactly one of a or b must be true, so we have found the first true boolean, and the only thing left that matters is if c is also true, so we return c as the answer.

4
  • 11
    c is never even tested... brilliant!
    – CurtainDog
    Jun 23, 2010 at 3:16
  • Uses transitive relation of equality and the fact that a boolean is either true or false +1 May 21, 2013 at 9:32
  • 3
    So elegant! I had to check with pen and paper to believe it:) Kudos to you sir!
    – Adrian
    Aug 16, 2013 at 9:46
  • 9
    I think about this as "if a and b agree, they have the majority vote, so go with whatever it is, else, they disagree, so c is the deciding vote" Dec 24, 2016 at 16:53
146

This kind of questions can be solved with a Karnaugh Map:

      | C | !C
------|---|----
 A  B | 1 | 1 
 A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

from which you infer that you need a group for first row and two groups for first column, obtaining the optimal solution of polygenelubricants:

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case
3
  • 11
    @Justin, The Karnaugh map reduced the number of logical operations from 3 ANDs and 2 ORs to 2 ANDs and 2 ORs. @Jack, Thanks for reminding me of the Karnaugh Map's existence.
    – Tachy
    Jun 21, 2010 at 20:33
  • 15
    +1 for something new. My next functional spec will include a K-map, whether it needs it or it.
    – Justin R.
    Jun 22, 2010 at 7:00
  • 2
    Maybe the poor readability can be compensated by (1) the appropriate table in comment and (2) the appropriate unit test... +1 for something useful learned at school.
    – moala
    Feb 2, 2012 at 15:39
144

Readability should be the goal. Someone who reads the code must understand your intent immediately. So here is my solution.

int howManyBooleansAreTrue =
      (a ? 1 : 0)
    + (b ? 1 : 0)
    + (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;
4
  • 22
    I agree with the premise, but (a && b) || (b && c) || (a && c) is much more readable than your solution IMHO. Jun 19, 2010 at 22:45
  • 65
    Hmm, now I need a "two out of FOUR booleans" version... danatel's version is much easier now.
    – Arafangion
    Jun 20, 2010 at 4:24
  • 7
    Or in Scala: Seq(true, true, false).map(if (_) 1 else 0).sum >= 2
    – retronym
    Jun 23, 2010 at 6:00
  • 5
    @retronym: Hmm, no. The Java way works just fine in Scala and is both more readable and more efficient.
    – Seun Osewa
    Jul 24, 2010 at 20:14
34

You don't need to use the short circuiting forms of the operators.

return (a & b) | (b & c) | (c & a);

This performs the same number of logic operations as your version, however is completely branchless.

7
  • 11
    Why would you want to force 5 evaluations when 1 could do? It really doesn't perform the same number of logic operations in truth. In fact, it would always perform more. Jun 19, 2010 at 15:59
  • 2
    I think mixing binary arithmetic and boolean arithmetic is a bad idea. It is like driving screws in the wall with a wrench. Worst of all is they have different semantics. Jun 19, 2010 at 16:00
  • 12
    @Mark - it might be faster ... depending on the effect of an incorrect branch prediction on the CPU pipeline. However, it is best to leave such micro-optimizations to the JIT compiler.
    – Stephen C
    Jun 19, 2010 at 16:04
  • 4
    It is fine to do something like this in Java (or any other language)... with a couple of caveats: 1) it needs to be faster (in this case, I believe it is, see my second answer) 2) preferable significantly faster (not sure if it is), 3) most importantly documented since it is "odd". As long as it serves a purpose and it is documented it is fine to "break the rules" when it makes sense.
    – TofuBeer
    Jun 19, 2010 at 16:17
  • 11
    @Peter Tillemans There is no mixing with binary operators, in Java these are boolean operators.
    – starblue
    Jun 19, 2010 at 17:28
30

Here's a test-driven, general approach. Not as "efficient" as most of the solutions so far offered, but clear, tested, working, and generalized.

public class CountBooleansTest extends TestCase {
    public void testThreeFalse() throws Exception {
        assertFalse(atLeastTwoOutOfThree(false, false, false));
    }

    public void testThreeTrue() throws Exception {
        assertTrue(atLeastTwoOutOfThree(true, true, true));
    }

    public void testOnes() throws Exception {
        assertFalse(atLeastTwoOutOfThree(true, false, false));
        assertFalse(atLeastTwoOutOfThree(false, true, false));
        assertFalse(atLeastTwoOutOfThree(false, false, true));
    }

    public void testTwos() throws Exception {
        assertTrue(atLeastTwoOutOfThree(false, true, true));
        assertTrue(atLeastTwoOutOfThree(true, false, true));
        assertTrue(atLeastTwoOutOfThree(true, true, false));
    }

    private static boolean atLeastTwoOutOfThree(boolean b, boolean c, boolean d) {
        return countBooleans(b, c, d) >= 2;
    }

    private static int countBooleans(boolean... bs) {
        int count = 0;
        for (boolean b : bs)
            if (b)
                count++;
        return count;
    }
}
14
  • 9
    Wow, I've never seen a fully tested method before seeing this one.
    – Rotsor
    Jun 19, 2010 at 20:41
  • 52
    I personally find this code awful, for so many reasons. I'm not going to downvote, but if I ever saw this in production code I would curse. An extremely simple boolean operation does not need to be complicated like this. Jun 21, 2010 at 5:41
  • 11
    I'd be very interested to know your reasons, @CaptainCasey. I think this is pretty good code. There's a nice generalized function that's easy to understand, easy to verify, and a specific function that takes advantage of it, also easy to understand & verify. In the real world, I'd make them public and put them in another class; other than that - I'd happily put this code into production. Oh - yeah - I'd rename countBooleans() to countTrue(). Jun 21, 2010 at 13:42
  • 5
    if its not about performance, this solution looks nearly perfect for me: very easy to read and extendable. Thats exactly what var-args are made for. Jun 22, 2010 at 9:17
  • 9
    What the hell, people? This is clear and well tested code, and the only reason it looks like a lot is because it includes the tests. A+++, would upvote again. Dec 19, 2010 at 21:59
24

Sum it up. It's called boolean algebra for a reason:

  0 x 0 = 0
  1 x 0 = 0
  1 x 1 = 1

  0 + 0 = 0
  1 + 0 = 1
  1 + 1 = 0 (+ carry)

If you look at the truth tables there, you can see that multiplication is boolean and, and simply addition is xor.

To answer your question:

return (a + b + c) >= 2
5
  • 2
    This is the most elegant solution, in my opinion. Jun 22, 2010 at 10:10
  • 10
    Rookie mistake though, a boolean value is NOT 0, that does not mean its always 1.
    – tomdemuyt
    Jun 22, 2010 at 13:28
  • 14
    Except that the tag on the post says "Java", and you can't write "a+b+c" when they are defined as booleans in Java.
    – Jay
    Jun 23, 2010 at 17:27
  • To work in Java, it would have to be return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2. Nov 15, 2013 at 19:22
  • Duh, I voted this up because I thought it was a C++ question... why am I reading java questions? :/
    – Carlo Wood
    Jan 1, 2018 at 2:48
15
boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}
15

It really depends what you mean by "improved":

Clearer?

boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
    return (a && b) || (a && c) || (b && c);
}

Terser?

boolean moreThanTwo(boolean a, boolean b, boolean c)
{
    return a == b ? a : c;
}

More general?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(boolean b : bs)
    {
        count += b ? 1 : 0;

        if(count > x) return true;
    }

    return false;
}

More scalable?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(int i < 0; i < bs.length; i++)
    {
        count += bs[i] ? 1 : 0;

        if(count > x) return true;

        int needed = x - count;
        int remaining = bs.length - i;

        if(needed >= remaining) return false;
    }

    return false;
}

Faster?

// Only profiling can answer this.

Which one is "improved" depends heavily on the situation.

14

Here's another implementation using map/reduce. This scales well to billions of booleans© in a distributed environment. Using MongoDB:

Creating a database values of booleans:

db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});

Creating the map, reduce functions:

Edit: I like CurtainDog's answer about having map/reduce apply to generic lists, so here goes a map function which takes a callback that determines whether a value should be counted or not.

var mapper = function(shouldInclude) {
    return function() {
        emit(null, shouldInclude(this) ? 1 : 0);
    };
}

var reducer = function(key, values) {
    var sum = 0;
    for(var i = 0; i < values.length; i++) {
        sum += values[i];
    }
    return sum;
}

Running map/reduce:

var result = db.values.mapReduce(mapper(isTrue), reducer).result;

containsMinimum(2, result); // true
containsMinimum(1, result); // false


function isTrue(object) {
    return object.value == true;
}

function containsMinimum(count, resultDoc) {
    var record = db[resultDoc].find().next();
    return record.value >= count;
}
2
  • @Anurag: as much as I love M/R and the exposure that Google recently gave to it (even if it's not the one true M/R from FP), I'd tend to call bullsh!t on your answer. There are billions and billions of lines of code performing Real-World [TM] "stuff" where there ain't a single line of map/reduce used. Someone answering such a question with this is definitely flagged in my book as: "trying to play the smartie". Not to mention most interviewers wouldn't be able to tell if you're trying to bullsh!t them or not because they actually never wrote a single program using M/R in their career. Sep 8, 2011 at 12:41
  • 2
    @Syntax - Everyone is entitled to their opinion. My answer is just one more approach of looking at the problem. Sure, it sounds exaggerated for 3 booleans values, but that doesn't mean I'm trying to be the smarty-pants here. This is a common approach to problem solving that everyone uses - break the problem down into small pieces. That's how mathematical induction works, that's how most recursive algorithms work, and that's how people solve problems in general.
    – Anurag
    Sep 8, 2011 at 23:52
13

Taking the answers (so far) here:

public class X
{
    static boolean a(final boolean a, final boolean b, final boolean c)
    {
    return ((a && b) || (b && c) || (a && c));
    }

    static boolean b(final boolean a, final boolean b, final boolean c)
    {
    return a ? (b || c) : (b && c);
    }

    static boolean c(final boolean a, final boolean b, final boolean c)
    {
    return ((a & b) | (b & c) | (c & a));
    }

    static boolean d(final boolean a, final boolean b, final boolean c)
    {
    return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
    }
}

and running them through the decompiler (javap -c X > results.txt):

Compiled from "X.java"
public class X extends java.lang.Object{
public X();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

static boolean a(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    8
   4:   iload_1
   5:   ifne    24
   8:   iload_1
   9:   ifeq    16
   12:  iload_2
   13:  ifne    24
   16:  iload_0
   17:  ifeq    28
   20:  iload_2
   21:  ifeq    28
   24:  iconst_1
   25:  goto    29
   28:  iconst_0
   29:  ireturn

static boolean b(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    20
   4:   iload_1
   5:   ifne    12
   8:   iload_2
   9:   ifeq    16
   12:  iconst_1
   13:  goto    33
   16:  iconst_0
   17:  goto    33
   20:  iload_1
   21:  ifeq    32
   24:  iload_2
   25:  ifeq    32
   28:  iconst_1
   29:  goto    33
   32:  iconst_0
   33:  ireturn

static boolean c(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   iload_1
   2:   iand
   3:   iload_1
   4:   iload_2
   5:   iand
   6:   ior
   7:   iload_2
   8:   iload_0
   9:   iand
   10:  ior
   11:  ireturn

static boolean d(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    8
   4:   iconst_1
   5:   goto    9
   8:   iconst_0
   9:   iload_1
   10:  ifeq    17
   13:  iconst_1
   14:  goto    18
   17:  iconst_0
   18:  iadd
   19:  iload_2
   20:  ifeq    27
   23:  iconst_1
   24:  goto    28
   27:  iconst_0
   28:  iadd
   29:  iconst_2
   30:  if_icmplt   37
   33:  iconst_1
   34:  goto    38
   37:  iconst_0
   38:  ireturn
}

You can see that the ?: ones are slightly better then the fixed up version of your original. The one that is the best is the one that avoids branching altogether. That is good from the point of view of fewer instructions (in most cases) and better for branch prediction parts of the CPU, since a wrong guess in the branch prediction can cause CPU stalling.

I'd say the most efficient one is the one from moonshadow overall. It uses the fewest instructions on average and reduces the chance for pipeline stalls in the CPU.

To be 100% sure you would need to find out the cost (in CPU cycles) for each instruction, which, unfortunately isn't readily available (you would have to look at the source for hotspot and then the CPU vendors specs for the time taken for each generated instruction).

See the updated answer by Rotsor for a runtime analysis of the code.

1
  • 5
    You're only looking at the bytecode. For all you know, the JIT will take a version with branches in the bytecode and turn it into a version with no branches in native code. But one would tend to think that fewer branches in the bytecode would be better. May 30, 2012 at 0:18
13

Another example of direct code:

int  n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);

It's not the most succinct code, obviously.

Addendum

Another (slightly optimized) version of this:

int  n = -2;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 0);

This might run slightly faster, assuming that the comparison against 0 will use faster (or perhaps less) code than the comparison against 2.

3
  • +1 @Loadmaster, I'm sorry but you're wrong! This is the most succinct answer here. (i.e. briefly AND clearly expressed) ;)
    – Ash
    Jul 19, 2010 at 13:21
  • Micro-optimisation: ++n is faster than n++ because you have to create another copy before doing the increment.
    – M. Mimpen
    Jan 20, 2014 at 13:55
  • @M.Mimpen: Only for class objects. For primitive types (like n above), any decent compiler will compile each ++ operation down into a single CPU instruction, whether it's pre or post. Jan 22, 2014 at 23:40
12

Yet another way to do this but not a very good one:

return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);

The Boolean hashcode values are fixed at 1231 for true and 1237 for false so could equally have used <= 3699

1
  • 1
    or (a?1:0)+(b?1:0)+(c?1:0) >= 2 Jun 20, 2010 at 6:06
12

The most obvious set of improvements are:

// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    return false;
}

and then

// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return ((a && b) || (b && c) || (a && c));
}

But those improvements are minor.

10

I don't like ternary (return a ? (b || c) : (b && c); from the top answer), and I don't think I've seen anyone mention it. It is written like this:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a) {
        return b||c;
    } 
    else {
        return b&&C;
    }
0
8

In Clojure:

(defn at-least [n & bools]
  (>= (count (filter true? bools)) n)

Usage:

(at-least 2 true false true)
1
  • 2
    +1 Great generic version shows the power of the Lisps. Thanks,
    – dsmith
    Jun 22, 2010 at 0:13
7

I don't think I've seen this solution yet:

boolean atLeast(int howMany, boolean[] boolValues) {
  // check params for valid values

  int counter = 0;
  for (boolean b : boolValues) {
    if (b) {
      counter++;

      if (counter == howMany) {
        return true;
      }
    }
  }
  return false;
}

Its advantage is that once it reaches the number that you're looking for, it breaks. So if this was "at least 2 out of this 1,000,000 values are true" where the first two are actually true, then it should go faster than some of the more "normal" solutions.

6
  • That should probably be: if (++counter == howMany) instead of incrementing and then checking separately.
    – Joe Enos
    Jun 21, 2010 at 22:55
  • 2
    Or even shorter: if (b && (++counter == howMany))
    – Joe Enos
    Jun 21, 2010 at 22:56
  • 1
    I'd do boolean ... boolValues so it's easier to call, but still takes an array
    – Stephen
    Jun 21, 2010 at 23:15
  • I'm not up to date on my Java - didn't know that existed. Kind of a strange syntax, but it's useful - every once in a while I'll do that in C# (params keyword), and it does make things nicer to call. Or, I don't know about Java, but in .NET, arrays and all collections implement IEnumerable<T>, so I'd probably use whatever Java's equivalent is.
    – Joe Enos
    Jun 21, 2010 at 23:44
  • How does the performance of this compare against the 2of3 example? return a ? (b || c) : (b && c); Jun 24, 2010 at 11:54
7

We can convert the bools to integers and perform this easy check:

(int(a) + int(b) + int(c)) >= 2
1
  • I don't understand why this isn't the official answer: it's the most concise, the fastest in execution and the simplest to understand. And in C you don't need to transtype: a+b+c>=2
    – dargaud
    Dec 14, 2021 at 12:30
6

Since it wasn't specified how the code should be improved, I shall endeavour to improve the code by making it more amusing. Here's my solution:

boolean atLeastTwo(boolean t, boolean f, boolean True) {
    boolean False = True;
    if ((t || f) && (True || False)) 
        return "answer" != "42";
    if (t && f) 
        return !"France".contains("Paris");
    if (False == True) 
        return true == false;
    return Math.random() > 0.5;
}

In case anyone's wondering if this code works, here's a simplification using the same logic:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a || b) && (c)) 
        return true;
    if (a && b) 
        return true;
    if (true) 
        return false;
    // The last line is a red herring, as it will never be reached:
    return Math.random() > 0.5; 

}

This can be boiled down further to the following:

return ((a || b) && (c)) || (a && b);

But now it's not funny any more.

0
5
Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
     return (System.Convert.ToInt16(val1) +
             System.Convert.ToInt16(val2) +
             System.Convert.ToInt16(val3)) > 1;
}

Too many ways to do this...

1
  • 3
    Look more like C#. This should be mentioned as such in the answer since the question is Java-targeted :)
    – BalusC
    Jun 21, 2010 at 17:41
5

A C solution.

int two(int a, int b, int c) {
  return !a + !b + !c < 2;
}

or you may prefer:

int two(int a, int b, int c) {
  return !!a + !!b + !!c >= 2;
}
0
5

A literal interpretation will work in all major languages:

return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;

But I would probably make it easier for people to read, and expandable to more than three - something that seems to be forgotten by many programmers:

boolean testBooleans(Array bools)
{
     int minTrue = ceil(bools.length * .5);
     int trueCount = 0;

     for(int i = 0; i < bools.length; i++)
     {
          if(bools[i])
          {
               trueCount++;
          }
     }
     return trueCount >= minTrue;
}
4
return 1 << $a << $b << $c >= 1 << 2;
3
  • Didn't see Suvega's answer before posing this, pretty much the same thing.
    – Kevin
    Jun 21, 2010 at 19:59
  • Does this really work? I assume this is PHP, but I don't have access to it, but I'll just ask you: what happens if $a is 0?
    – Mark Edgar
    Jun 22, 2010 at 11:17
  • @Mark It actually doesn't work if $a is 0. That was an oversight. Thanks for pointing that out. :)
    – Kevin
    Jun 22, 2010 at 12:47
4

In C:

return !!a + !!b + !!c >= 2;
4
  • Actually, this answer is wrong… it should be >= 2, since you need at least two true booleans, not exactly two. Sep 19, 2011 at 19:15
  • @Paul Wagland: Thanks for the catch. Sep 19, 2011 at 23:16
  • @ergosys: Wth I answered twice? Jan 31, 2012 at 7:16
  • Nice one. I'd prefer this one since it will allow you to expand it to "three out of four" etc. Wondering if there is a caveat to counting the number of true's and comparing that to the amount though.
    – Remi
    Sep 8, 2020 at 9:58
4

The simplest way (IMO) that is not confusing and easy to read:

// Three booleans, check if two or more are true

return ( a && ( b || c ) ) || ( b && c );
4
  • Functionally, it is the same. Syntactically, it makes it easier to read for those unaccustomed to the use of the question mark conditional operator. I am willing to bet more people know how to use AND and OR operators than the number of people who know how to use question mark conditional operators. The original question asks for an "improved answer".. The accepted answer does simplify the answer, but raises a very interesting question of what does one consider improvement. Do you program for universal readability or for simplicity? To me, this is an improvement over the accepted answer :)
    – abelito
    Jun 21, 2010 at 18:48
  • Personal preferences. For me it's way more easy to understand the cleaner ternary operator than this solution.
    – nico
    Jun 21, 2010 at 20:00
  • 1
    Ah yeah, I saw this problem and was wondering why no one else mentioned this solution. If you write out the OP's logic as boolean algebra, you get AB+AC+BC, which has five operations. By the associative property, you can write A*(B+C)+BC, which has four operations. Jun 22, 2010 at 16:40
  • It's the same as Jack's answer (Jun. 19th) (C && (A || B)) || (A && B) just changed the *variable` names...
    – user85421
    Jun 25, 2010 at 11:32
4

As an addition to @TofuBeer TofuBeer's excellent post, consider @pdox pdox's answer:

static boolean five(final boolean a, final boolean b, final boolean c)
{
    return a == b ? a : c;
}

Consider also its disassembled version as given by "javap -c":

static boolean five(boolean, boolean, boolean);
  Code:
    0:    iload_0
    1:    iload_1
    2:    if_icmpne    9
    5:    iload_0
    6:    goto    10
    9:    iload_2
   10:    ireturn

pdox's answer compiles to less byte code than any of the previous answers. How does its execution time compare to the others?

one                5242 ms
two                6318 ms
three (moonshadow) 3806 ms
four               7192 ms
five  (pdox)       3650 ms

At least on my computer, pdox's answer is just slightly faster than @moonshadow moonshadow's answer, making pdox's the fastest overall (on my HP/Intel laptop).

0
4

Currenty with Java 8, I really prefer something like this:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return Stream.of(a, b, c).filter(active -> active).count() >= 2;
}
3
  • Instead of Arrays.asList(a, b, c).stream(), you can have Stream.of(a, b, c)...
    – Tunaki
    Nov 10, 2016 at 15:37
  • Very heavyweight.
    – Boann
    Nov 10, 2016 at 17:17
  • 1
    @Boan I think is more important the code reveals intention than early optimizations...
    – coder
    Nov 16, 2016 at 16:50
4

Calculated via a truth table:

return (a & b) | (c & (a ^ b));
1
  • 4
    Well, the original solution is easier.
    – z-index
    Jun 22, 2010 at 5:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.