最近面试官问了我这个问题：给定三个布尔型变量a、b和c，如果其中至少有两个是true，则返回true。
我的解决方案如下：
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改善，但如何呢？
检查三个布尔值中至少有两个为真
612
- user282886
19
65个回答
847
不要这样写：
if (someExpression) {
return true;
} else {
return false;
}
编写代码：
return someExpression;
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);
}
它只测试a和b一次，而c最多测试一次。
参考资料
- polygenelubricants
16
150+1：这是一个可爱的解决方案，但希望我们在现实世界中不会看到类似的情况 :) - Juliet
125@Juliet: 我不知道，我认为如果这是一个现实中的需求（具有真实的变量名），它应该会读起来很好。请考虑
return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam)，在我看来这看起来很好。 - Andrzej Doyle18我认为这看起来并不糟糕，但是如果该领域的要求被理解为“至少两个”，那么我认为更容易阅读
atLeastTwo（hasgoodAttendance，passedCoursework，passedExam）。 “至少有2个布尔值为真”的想法足够通用，可以拥有自己的功能。 - Ken18在面试中要求最微观优化的代码是不切实际的，也可以说是无用的。微观优化是在需要时由运行时分析结果指导的，而不是由人类直觉引导的（人类直觉被认为是可怕的）。你可以问面试者如何进一步优化这个过程；这比结果本身更重要。 - polygenelubricants
18三元运算符是一种常见的惯用语，您应该能够理解它。如果您无法理解它，请学习直到能够理解为止。在我看来，使用三元运算符并不是“聪明”的贬义意义。但是，如果您经常使用“至少两个”逻辑，我会将其放在方法调用体中。 - Stephen P
显示剩余11条评论
510
只是为了利用异或来回答一个相对简单的问题...
return a ^ b ? c : a
- Tim Stone
13
166哇，很棒的解决方案。
但对我来说，它的倒置版本更容易理解：a==b ? a : c。 - Rotsor
5a ^ b ? c : a ^ b ? c : a ^ b ? c : a - alexanderpas
4耶，异或门总是被贬低，而且你很少有机会使用它。 - EightyOne Unite
19@Stimul8d也许是因为对于布尔类型来说，它与!=相同，但可读性较差？对此的领悟对我来说是一个顿悟时刻... - Tikhon Jelvis
2我更喜欢纯二进制形式：return ((a^b) & c) | (a & b)。它是无分支（更快）和易读的：（a或b为真且c为真）或（a和b都为真）。请注意，（a|b）和（a^b）都可与此公式配合使用。 - flanglet
显示剩余8条评论
228
为什么不直接实现呢？ :)
(a?1:0)+(b?1:0)+(c?1:0) >= 2
在C语言中，你可以直接写a+b+c >= 2（或!!a+!!b+!!c >= 2以确保安全）。
针对TofuBeer关于Java字节码的比较，这里有一个简单的性能测试：
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);
}
}
}
在我的机器上（运行Ubuntu，Intel Core 2处理器，Sun Java 1.6.0_15-b03和HotSpot Server VM（14.1-b02，混合模式）），这将打印以下内容：
第一次和第二次迭代：
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虚拟机在处理 (a + b + c >= 2) 的情况下，有哪些会导致性能逐渐下降的问题。
如果我在运行Java时使用 -client 虚拟机开关，会发生什么：
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 Interpreter中运行它，速度减慢了近100倍，但a&&b || b&&c || a&&c的版本会取胜。
在OS X上最新代码的Tofubeer结果:
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
使用Mac Java 1.6.0_26-b03-383-11A511版本，由Paul Wagland获得的结果。
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
- Rotsor
20
4“a+b+c >= 2”：这个公式对于负数行不通，对吗？你可能需要使用“!!a”的方式，但我不确定。 - polygenelubricants
8实际上，我猜C99标准中将true定义为1。但是我仍然不会这样做。你永远不应该这样做，因为你不知道true的值是多少（它可能很容易就是-1）。 - Mark Peters
1如果您的输入是布尔运算的结果，那么这是否可能？在C++中的“bool”类型是否支持此操作？ - Rotsor
2@Rotsor：没有人说输入必须是布尔运算的结果。即使没有负数，如果你将其定义为2，你的条件也会出现误报。但我更不喜欢将布尔值与算术混合在一起的想法。你的Java解决方案很清晰，因为它不依赖于从布尔类型到整数类型的微妙转换。 - Mark Peters
7小心使用微基准测试：http://java.sun.com/docs/hotspot/HotSpotFAQ.html#benchmarking_simple - BalusC
显示剩余15条评论
162
return (a==b) ? a : c;
解释:
如果 a==b，那么两个布尔值要么都是 true，要么都是 false。如果两者都为 true，我们找到了两个 true 布尔值，可以通过返回 a 来返回 true。如果两者都为 false，即使 c 为 true，也不可能有两个 true 布尔值，所以我们通过返回 a 来返回 false。这就是 (a==b) ? a 部分。那么 : c 怎么样呢？如果 a==b 为 false，那么恰好 a 或 b 中的一个必须为 true，因此我们找到了第一个 true 布尔值，并且唯一重要的是 c 是否也为 true，因此我们返回 c 作为答案。
- pdox
4
11C从未被测试过...太棒了！ - CurtainDog
利用等式的传递性和布尔值只能为真或假的事实 +1。 - Christophe Roussy
3太优雅了！我不得不用纸笔检查才能相信它 :) 向您致敬，先生！ - Adrian
11我理解这句话的意思是：“如果
a 和 b 达成一致，他们就占据了多数票，所以就按照他们的决定行动；否则，如果他们不同意，那么 c 就成为了决定性的投票者。” - Ben Millwood146
可以使用卡诺图来解决这种类型的问题：
| C | !C
------|---|----
A B | 1 | 1
A !B | 1 | 0
!A !B | 0 | 0
!A B | 1 | 0
根据这个推断，您需要为第一行分配一个组，并为第一列分配两个组，以获得polygenelubricants的最佳解决方案:
(C && (A || B)) || (A && B) <---- first row
^
|
first column without third case
- Jack
3
11@Justin，卡诺图将逻辑运算次数从3个AND和2个OR降至2个AND和2个OR。@Jack，谢谢你提醒我卡诺图的存在。 - Tachy
15对于某些新的东西，我会点赞。我的下一个功能规格说明将包括一个K-map，无论它是否需要。 - Justin R.
2也许可以通过（1）适当的注释表格和（2）适当的单元测试来弥补可读性差的问题...因为从中学到了有用的东西，所以加一分。 - moala
145
可读性应该是目标。阅读代码的人必须立刻理解你的意图。所以这是我的解决方案。
int howManyBooleansAreTrue =
(a ? 1 : 0)
+ (b ? 1 : 0)
+ (c ? 1 : 0);
return howManyBooleansAreTrue >= 2;
- danatel
4
22我同意这个前提，但是在我看来，(a && b) || (b && c) || (a && c) 比你的解决方案更易读。 - Adrian Grigore
65现在我需要一个“四个布尔值中的两个”版本……danatel的版本现在要容易得多。 - Arafangion
7在Scala中：
Seq(true, true, false).map(if (_) 1 else 0).sum >= 2可以翻译为：将布尔值序列 Seq(true, true, false) 中的每个元素转换为整数（对于true转换为1，false转换为0），然后将所有元素加起来。如果和大于或等于2，则返回true；否则返回false。 - retronym5嗯，不对。Java的方式在Scala中完全可行，而且更易读、更高效。 - Seun Osewa
34
您不需要使用运算符的短路形式。
return (a & b) | (b & c) | (c & a);
这个实现与您的版本执行相同数量的逻辑操作，但完全无需分支。
- moonshadow
7
11为什么要强制进行5次评估，如果1次就可以呢？实际上，它并没有执行相同数量的逻辑操作。事实上，它总是会执行更多的操作。 - Mark Peters
2我认为混合使用二进制算术和布尔逻辑是一个坏主意。这就像用扳手在墙上拧螺钉一样。最糟糕的是它们有不同的语义。 - Peter Tillemans
12@Mark - 这可能会更快...取决于错误分支预测对CPU流水线的影响。然而，最好将这种微小优化留给JIT编译器。 - Stephen C
4在Java（或任何其他语言）中这样做是可以的，但需要注意以下几点：1）它需要更快（在这种情况下，我相信是的，可以参考我的第二个答案）；2）最好要明显更快（不确定是否如此）；3）最重要的是需要有文档记录，因为这种方式比较“奇怪”。只要它有意义并且有文档记录，打破规则也无妨。 - TofuBeer
11@Peter Tillemans 在Java中，不存在二进制运算符的混合使用，它们被称为布尔运算符。 - starblue
显示剩余2条评论
30
这里有一个测试驱动的通用方法。它不像目前提供的大多数解决方案那么“高效”，但是清晰、经过测试、可行，而且具有通用性。
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;
}
}
- Carl Manaster
14
9哇，我从来没有看过一个 完全 被测试过的方法，在看到这个之前。 - Rotsor
52就我个人而言，出于很多原因，我认为这段代码很糟糕。我不会给它点踩的，但如果我在生产代码中看到它，我会咒骂。一个非常简单的布尔运算不需要像这样变得复杂。 - CaptainCasey
11非常想知道你的原因，@CaptainCasy。我认为这是相当不错的代码。有一个好的通用函数，易于理解和验证，还有一个利用它的特定函数，也容易理解和验证。在实际应用中，我会将它们公开并放入另一个类中；除此之外 - 我很乐意将这段代码投入生产。哦 - 是的 - 我会将countBooleans（）重命名为countTrue（）。 - Carl Manaster
5如果不考虑性能，这个解决方案对我来说几乎完美：非常易读且可扩展。这正是可变参数的设计初衷。 - atamanroman
9什么鬼，大家怎么了？这是经过清晰和充分测试的代码，它看起来像很多只是因为它包括了测试。 A + + +，我会再次点赞。 - Christoffer Hammarström
显示剩余9条评论
24
简而言之，它被称为布尔代数是有原因的：
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
- memet
5
2这是我认为最优雅的解决方案。 - Torbjørn Kristoffersen
10新手犯了个错误，布尔值不是0就是1，但并不总是1。 - tomdemuyt
14除了帖子上标签写着“Java”，在Java中当它们被定义为布尔值时，你不能写“a+b+c”。 - Jay
要在Java中工作，它应该是
return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2。 - David R Tribble我投了赞成票，因为我以为这是一个C++的问题...为什么我在看Java的问题？ :/ - Carlo Wood
15
boolean atLeastTwo(boolean a, boolean b, boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
- malu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)- Andrew GrimmatLeastTwo(0,2,0)。请问您的看法？ - Ken