检查三个布尔值中的至less两个是否为真
面试官最近问我这个问题：给定三个布尔variablesa，b和c，如果三个中至less有两个是真的，则返回true。
我的解决scheme是：
boolean atLeastTwo(boolean a, boolean b, boolean c) { if ((a && b) || (b && c) || (a && c)) { return true; } else{ return false; } } 他表示，这可以进一步改善，但如何？
而不是写作：
if (someExpression) { return true; } else { return false; }
写：
return someExpression;
至于expression本身，像这样的东西：
boolean atLeastTwo(boolean a, boolean b, boolean c) { return a ? (b || c) : (b && c); }
或者这个（你发现哪一个更容易理解）：
boolean atLeastTwo(boolean a, boolean b, boolean c) { return a && (b || c) || (b && c); }
它testinga和b一次， c至多一次。
参考
- JLS 15.25有条件的运营商？ ：
只是为了使用异或来回答一个相对直接的问题…
return a ^ b ? c : a
为什么不从字面上实现呢？ 🙂
(a?1:0)+(b?1:0)+(c?1:0) >= 2
在C中你可以写a+b+c >= 2 （或者!!a+!!b+!!c >= 2是非常安全的）。
为了回应TofuBeer对java字节码的比较，下面是一个简单的性能testing：
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); } } }
这将在我的机器上打印以下内容（在Intel Core 2 + sun java 1.6.0_15-b03上使用HotSpot Server VM（14.1-b02，混合模式）运行Ubuntu）：
第一次和第二次迭代：
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
后来的迭代：
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
我想知道，Java VM会如何降低 （a + b + c> = 2）情况下的性能。
如果我用-client VM开关运行java，会发生什么情况：
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
神秘…
如果我在GNU Java解释器中运行它，它会慢100倍，但是a&&b || b&&c || a&&c a&&b || b&&c || a&&c a&&b || b&&c || a&&c版本胜出。
Tofubeer使用最新的代码运行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
Paul Wagland使用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
这样的问题可以用卡诺图解决：
| C | !C ------|---|---- AB | 1 | 1 A !B | 1 | 0 !A !B | 0 | 0 !AB | 1 | 0
从中推断出第一行需要一个组，第一行需要两个组，获得多能渗透液的最优解：
(C && (A || B)) || (A && B) <---- first row ^ | first column without third case
可读性应该是目标。 阅读代码的人必须立即理解你的意图。 所以这是我的解决scheme。
int howManyBooleansAreTrue = (a ? 1 : 0) + (b ? 1 : 0) + (c ? 1 : 0); return howManyBooleansAreTrue >= 2;
return (a==b) ? a : c;
说明：
如果a==b ，那么两者都是真的或者两者都是假的。 如果两者都是真的，我们find了两个真正的布尔值，并且可以返回true（通过返回a ）。 如果两者都是假的，即使c为真，也不能有两个真正的布尔值，所以我们返回false（通过返回a ）。 那是(a==b) ? a 一部分。 那么: c ？ 那么如果a==b是假的，那么a或b的a必须是真的，所以我们find了第一个真正的布尔值，唯一剩下的就是如果c也是真的，所以我们返回c作为答案。
您不需要使用操作员的短路forms。
return (a & b) | (b & c) | (c & a);
这将执行与您的版本相同数量的逻辑操作，但完全无分支。
这是一个testing驱动的一般方法。 并不像迄今为止提供的大多数解决scheme那样“高效”，而是清晰，经过testing，工作和推广。
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; } }
总结一下。 这就是所谓的布尔代数：
0 x 0 = 0 1 x 0 = 0 1 x 1 = 1 0 + 0 = 0 1 + 0 = 1 1 + 1 = 0 (+ carry)
如果你看看那里的真值表，你可以看到乘法是布尔值，而简单的加法就是异或。
回答你的问题：
return (a + b + c) >= 2
boolean atLeastTwo(boolean a, boolean b, boolean c) { return ((a && b) || (b && c) || (a && c)); }
在这里回答（到目前为止）：
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); } }
并通过反编译器运行它们（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 }
你可以看到？：那些比原来固定的版本要好一些。 最好的一个是避免分支的一个。 从较less的指令（在大多数情况下）的angular度来看，这是好的，对于CPU的分支预测部分来说更好，因为分支预测中的错误猜测会导致CPU停止。
我认为最有效率的是从总体上来看， 它平均使用最less的指令，减less了CPU中pipe道延迟的机会。
为了100％确定，你需要找出每条指令的成本（在CPU周期中），不幸的是，这些成本并不是很容易得到的（你必须查看热点的来源，然后CPU厂商规定时间为每个生成的指令采取）。
有关代码的运行时分析，请参阅由Rotsor更新的答案。
这是另一个使用map / reduce的实现。 这在分布式环境中可以很好地扩展到数十亿布尔值 。 使用MongoDB：
创build布尔values的数据库values ：
db.values.insert({value: true}); db.values.insert({value: false}); db.values.insert({value: true});
创build地图，减lessfunction：
编辑 ：我喜欢CurtainDog的有关地图/减less应用到generics列表的 答案 ，所以这里有一个映射函数，它需要一个callback，确定是否应该计数一个值。
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; }
运行地图/减less：
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; }
直接代码的另一个例子：
int n = 0; if (a) n++; if (b) n++; if (c) n++; return (n >= 2);
这显然不是最简洁的代码。
附录
这个的另一个（稍微优化）版本：
int n = -2; if (a) n++; if (b) n++; if (c) n++; return (n >= 0);
这可能运行得稍微快一点，假设与0进行的比较将比使用2的比较使用更快（或者更less）的代码。
这真的取决于你所说的“改进”：
更清晰？
boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c) { return (a && b) || (a && c) || (b && c); }
更简洁？
boolean moreThanTwo(boolean a, boolean b, boolean c) { return a == b ? a : c; }
更一般？
boolean moreThanXTrue(int x, boolean[] bs) { int count = 0; for(boolean b : bs) { count += b ? 1 : 0; if(count > x) return true; } return false; }
更具扩展性？
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; }
更快？
// Only profiling can answer this.
哪一个“改进”很大程度上取决于情况。
最明显的一组改进是：
// 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; }
接着
// 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)); }
但是这些改进都很小。
还有另一种方式做到这一点，但不是一个很好的方法：
return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);
布尔哈希码值固定为1231为真，1237为假，因此可以同样使用<= 3699
我不喜欢三元（ return a ? (b || c) : (b && c);从最上面的答案），我不认为我见过任何人提到它。 它是这样写的：
boolean atLeastTwo(boolean a, boolean b, boolean c) { if (a) { return b||c; } else { return b&&C; }
在Clojure中 ：
(defn at-least [n & bools] (>= (count (filter true? bools)) n)
用法：
(at-least 2 true false true)
我不认为我已经看到这个解决scheme了：
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; }
它的优点是，一旦达到你要查找的数量，就会中断。 所以如果这个“至less有两百万个值是真的”，其中前两个是真的，那么它应该比一些更“正常”的解决scheme更快。
由于没有规定如何改进代码，我会努力通过使代码更有趣来改进代码。 这是我的解决scheme：
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; }
如果有人想知道这个代码是否工作，这里使用相同的逻辑简化：
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;
}
这可以进一步归结为以下几点：
return ((a || b) && (c)) || (a && b);
但现在不再有趣了。
Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3)) { return (System.Convert.ToInt16(val1) + System.Convert.ToInt16(val2) + System.Convert.ToInt16(val3)) > 1; }
太多的方法来做到这一点…
We can convert the bools to integers and perform this easy check:
(int(a) + int(b) + int(c)) >= 2
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 );
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; }
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).
AC 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; }
return 1 << $a << $b << $c >= 1 << 2;
In Ruby:
[a, b, c].count { |x| x } >= 2
Which could be run in JRuby on the JavaVM. 😉
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.
In C:
return !!a + !!b + !!c >= 2;
