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?
This question is related to
java
boolean
boolean-logic
One thing I haven't seen others point out is that a standard thing to do in the "please write me some code" section of the job interview is to say "Could you improve that?" or "Are you completely happy with that" or "is that as optimized as possible?" when you say you are done. It's possible you heard "how would you improve that" as "this might be improved; how?". In this case changing the if(x) return true; else return false; idiom to just return x is an improvement - but be aware that there are times they just want to see how you react to the question. I have heard that some interviewers will insist there is a flaw in perfect code just to see how you cope with it.
If I convert the booleans into a number, and if the number is not a power of two, it has at least two trues.
a*4 + b*2 + c*1 = N
return( N != 0 && (N&(N-1)) != 0)
I am just giving an alternative.
Just for the sake of using XOR to answer a relatively straight-forward problem...
return a ^ b ? c : a
Definitely a question that's more about how you solve problems/think than your actual coding ability.
A slightly terser version could be
return ((a ^ b) && (b ^ c)) ^ b
But like a previous poster said, if I saw this in any code I was working on, someone would be getting an earful. :)
In Ruby:
[a, b, c].count { |x| x } >= 2
Which could be run in JRuby on the JavaVM. ;-)
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.
The simplest form using ternary operators to solve the problem is:
return a ? (b ? true : c) : (b ? c : false);
You may also want to invest finding a solution by using double negation of the requirement, meaning to say, instead of at least two true values, you need to satisfy the condition at most one false value.
Another one:
return a? b||c : b&&c
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.
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.
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.
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...
This sort of is reading better:
if (a) {
return b || c;
}
else {
return b && c;
}
In Clojure:
(defn at-least [n & bools]
(>= (count (filter true? bools)) n)
Usage:
(at-least 2 true false true)
return 1 << $a << $b << $c >= 1 << 2;
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
I found this solution.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
bool result = !(a ^ b ^ c) && !(!a & !b & !c) || (a & b & c);
return result;
}
He's probably not looking for anything convoluted like bitwise comparison operators (not normally convoluted but with booleans, it's extremely odd to use bitwise operators) or something that is very roundabout like converting to int and summing them up.
The most direct and natural way to solve this is with an expression like this:
a ? (b || c): (b && c)
Put it in a function if you prefer, but it's not very complicated. The solution is logically concise and efficient.
It should be:
(a || b && c) && (b || c && a)
Also, if true is automatically converted to 1 and false to 0:
(a + b*c) * (b + c*a) > 0
boolean atLeastTwo(boolean a, boolean b, boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
Let the three boolean values be A,B and C....
You can use a k-MAP and come with a boolean expression ...
In this case boolean expression will be A(B+C) + C
or if((A && (B || C )) || C ) { return true; } else return false;
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
We can convert the bools to integers and perform this easy check:
(int(a) + int(b) + int(c)) >= 2
It seems to me that three out of three are quite arbitrary numbers, and the function should work with an arbitrary number. So in order to answer the question, I'd write a function that would work out if x in an array were true, for example,
bool istrue ( int x, bool[] list)
y = count true in list
return y >= x
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;
}
I think the simplest solution is:
return (a && b) || c;
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.
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;
}
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.
In C:
return !!a + !!b + !!c >= 2;
The 2 and 3 in the question posed are decidedly magic-numberish. The 'correct' answer will depend on whether the interviewer was trying to get at your grasp of boolean logic (and I don't think pdox's answer could be bested in this respect) or your understanding of architectural issues.
I'd be inclined to go with a map-reduce solution that will accept any sort of list with any arbitrary condition.
C:
if (!!a + !!b + !!c >= 2)
function atLeastTwoTrue($a, $b, $c) {
int count = 0;
count = (a ? count + 1 : count);
count = (b ? count + 1 : count);
count = (c ? count + 1 : count);
return (count >= 2);
}
How about (a||b) && (a||c) - Java, uses three comparisons instead of the OP's six.
Wrong, I should have checked earlier.
My first thought when I saw the question was:
int count=0;
if (a)
++count;
if (b)
++count;
if (c)
++count;
return count>=2;
After seeing other posts, I admit that
return (a?1:0)+(b?1:0)+(c?1:0)>=2;
is much more elegant. I wonder what the relative runtimes are.
In any case, though, I think this sort of solution is much better than a solution of the
return a&b | b&c | a&c;
variety because is is more easily extensible. What if later we add a fourth variable that must be tested? What if the number of variables is determined at runtime, and we are passed an array of booleans of unknown size? A solution that depends on counting is much easier to extend than a solution that depends on listing every possible combination. Also, when listing all possible combinations, I suspect that it is much easier to make a mistake. Like try writing the code for "any 3 of 4" and make sure you neither miss any nor duplicate any. Now try it with "any 5 of 7".
FYI, this is just the carry-out bit of a full adder. In hardware, you could use the logical effort to determine the optimal circuit based on the different boolean expressions. I would guess that the traditional XOR solution would take more effort than the less succinct expression that the poster presented.
public static boolean atLeast(int atLeastToBeTrue, boolean...bools){
int booleansTrue = 0;
for(boolean tmp : bools){
booleansTrue += tmp ? 1 : 0;
}
return booleansTrue >= atLeastToBeTrue;
}
You can choose how many at least you want to be true from varargs a.k.a boolean[] :-)
Calculated via a truth table:
return (a & b) | (c & (a ^ b));
If the goal is to return a bitwise two-out-of-three value for three operands, arithmetic and iterative approaches are apt to be relatively ineffective. On many CPU architectures, a good form would be "return ((a | b) & c) | (a & b);". That takes four boolean operations. On single-accumulator machines (common in small embedded systems) that's apt to take a total of seven instructions per byte. The form "return (a & b) | (a & c) | (b & c);" is perhaps nicer looking, but it would require five boolean operations, or nine instructions per byte on a single-accumulator machine.
Incidentally, in CMOS logic, computing "not two out of three" requires twelve transistors (for comparison, an inverter requires two, a two-input NAND or NOR requires four, and a three-input NAND or NOR requires six).
X = OR(a+b,c)
a b c X
1 1 0 1
0 0 1 1
0 1 1 1
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;
}
}
Function ko returns the answer:
static int ho(bool a)
{
return a ? 1 : 0;
}
static bool ko(bool a, bool b, bool c)
{
return ho(a) + ho(b) + ho(c) >= 2 ? true : false;
}
Taking another approach to this using Java 8's Stream functionality, for any number of booleans with an arbitrary required amount. The Stream short circuits if it hits the limit before processing all of the elements:
public static boolean atLeastTrue(int amount, Boolean ... booleans) {
return Stream.of(booleans).filter(b -> b).limit(amount).count() == amount;
}
public static void main(String[] args){
System.out.println("1,2: " + atLeastTrue(1, true, false, true));
System.out.println("1,1: " + atLeastTrue(1, false, true));
System.out.println("1,0: " + atLeastTrue(1, false));
System.out.println("1,1: " + atLeastTrue(1, true, false));
System.out.println("2,3: " + atLeastTrue(2, true, false, true, true));
System.out.println("3,2: " + atLeastTrue(3, true, false, true, false));
System.out.println("3,3: " + atLeastTrue(3, true, true, true, false));
}
Output:
1,2: true
1,1: true
1,0: false
1,1: true
2,3: true
3,2: false
3,3: true
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 );
int count=0;
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if (a)
count++;
if (b)
count++;
if (c)
count++;
if (count>1)
return true;
else
return false;
}
How about this one:
(a - b) ? c : a
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
My first thought was
return (a||b)&&(b||c)
but for ease of reading I liked the proposed a+b+c>=2 solution that you guys suggested better
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).
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;
}
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
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.
Ternary operators get the nerd juices flowing, but they can be confusing (making code less maintainable, thus increasing the potential for bug injection). Jeff Attwood said it well here:
It's a perfect example of trading off an utterly meaningless one time write-time savings against dozens of read-time comprehension penalties-- It Makes Me Think.
Avoiding ternary operators, I've created the following function:
function atLeastTwoTrue($a, $b, $c) {
$count = 0;
if ($a) { $count++; }
if ($b) { $count++; }
if ($c) { $count++; }
if ($count >= 2) {
return true;
} else {
return false;
}
}
Is this as cool as some of the other solutions? No. Is it easier to understand? Yes. Will that lead to more maintainable, less buggy code? Yes.
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;
}
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;
In C#, off of the top of my head:
public bool lol(int minTrue, params bool[] bools)
{
return bools.Count( ( b ) => b ) >= minTrue;
}
should be pretty quick.
A call would look like this:
lol( 2, true, true, false );
This way, you are leaving the rules (two must be true) up to the caller, instead of embedding them in the method.
The best answer to the question should be "As an employee, it's important I write it so that my meaning is clear while maintaining efficiency where necessary for performance." Here's how I'd write it:
function atLeastTwoAreTrue(a, b, c) {
return (a && b) || (b && c) || (a && c);
}
In reality, the test is so contrived that writing a method that's the fastest, most cryptic possible is perfect acceptable if you accomodate it with a simple comment. But, in general, in this one-liner world, we need more readable code in this world. :-)
I believe using plain boolean operators (a || b) && (b || c) is fine and is simpler.
You can swap any of the 3 letters with any of the other two and it's still the same expresion.
The non-reduced solution to this problem is:
a'bc + abc' + abc + ab'c
Reducing using K-Maps, one gets:
bc + ab + ac
One could reduce this further by using exclusive or on the a'bc and abc' minterms and combining the abc and ab'c minterms:
b(a ^ c) + ac
Not in context of performance but good code(extensible and readable code that can be reused)
static boolean trueBooleans (int howMany,boolean ... bools)
{
int total = 0;
for (boolean b:bools)
if (b && (++total == howMany)) return true;
return false;
}
In my humble opinion when writing Java, easy handling unexpected changes and no duplicated code are more important than concise (domain of script languages) or fast program.
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.
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;
}
Source: Stackoverflow.com