检查三个布尔值中是否至少有两个为 true
最近一位面试官问了我这个问题：给定三个布尔变量 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;
}
}
他说这个可以进一步改进，但是如何改进呢？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（30）
而不是写：
写：
至于表达式本身，像这样：
或这样（无论您发现更容易掌握哪个）：
它只测试
a和b一次，并且c最多一次。参考文献
Rather than writing:
Write:
As for the expression itself, something like this:
or this (whichever you find easier to grasp):
It tests
aandbexactly once, andcat most once.References
只是为了使用 XOR 来回答一个相对直接的问题......
Just for the sake of using XOR to answer a relatively straight-forward problem...
为什么不按字面意思来实施呢？ :)
在 C 中，你可以只写
a+b+c >= 2（或者!!a+!!b+!!c >= 2，这样非常安全）。为了响应 TofuBeer 对 java 字节码的比较，这里有一个简单的性能测试：
这在我的机器上打印以下内容（在 Intel Core 2 + sun java 1.6.0_15-b03 上运行 Ubuntu，并使用 HotSpot Server VM（14.1-b02，混合模式））：
第一次和第二次迭代：
后来的迭代：
我想知道，随着时间的推移，java VM 会做什么降低性能 (a + b + c >= 2 ） 案件。
如果我使用
-clientVM 开关运行 java，会发生以下情况：神秘...
如果我在 GNU Java 解释器，它几乎慢了 100 倍，但是
a&&b || b&&c ||那么 a&&c版本获胜。使用运行 OS X 的最新代码得到的 Tofubeer 的结果：
Paul Wagland 使用 Mac Java 1.6.0_26-b03-383-11A511 得到的结果
Why not implement it literally? :)
In C you could just write
a+b+c >= 2(or!!a+!!b+!!c >= 2to be very safe).In response to TofuBeer's comparison of java bytecode, here is a simple performance test:
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:
Later iterations:
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
-clientVM switch:Mystery...
And if I run it in GNU Java Interpreter, it gets almost 100 times slower, but the
a&&b || b&&c || a&&cversion wins then.Results from Tofubeer with the latest code running OS X:
Results from Paul Wagland with a Mac Java 1.6.0_26-b03-383-11A511
解释：
如果
a==b，则两者都为 true 或两者都为 false。如果两者都为 true，我们就找到了两个 true 布尔值，并且可以返回 true（通过返回a）。如果两者都为 false，则即使c为 true，也不可能有两个 true 布尔值，因此我们返回 false（通过返回a）。那是(a==b) 吗？一部分。: c怎么样？如果a==b为 false，则a或b中的一个必须为 true，所以我们找到了第一个 true 布尔值，剩下唯一重要的是c是否也为 true，因此我们返回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 returninga). If both are false there cannot be two true booleans even ifcis true, so we return false (by returninga). That's the(a==b) ? apart. What about: c? Well ifa==bis false, then exactly one ofaorbmust be true, so we have found the first true boolean, and the only thing left that matters is ifcis also true, so we returncas the answer.此类问题可以通过卡诺地图来解决：
从中您推断出您需要一个小组对于第一行和第一列两组，得到多基因润滑剂的最优解：
This kind of questions can be solved with a Karnaugh Map:
from which you infer that you need a group for first row and two groups for first column, obtaining the optimal solution of polygenelubricants:
可读性应该是目标。阅读代码的人必须立即理解您的意图。这是我的解决方案。
Readability should be the goal. Someone who reads the code must understand your intent immediately. So here is my solution.
您不需要使用运算符的短路形式。
返回（a＆b）| （b 和 c）| (c & a);这执行与您的版本相同数量的逻辑操作，但是完全无分支。
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.
这是一个测试驱动的通用方法。不像迄今为止提供的大多数解决方案那样“高效”，但清晰、经过测试、有效且通用。
Here's a test-driven, general approach. Not as "efficient" as most of the solutions so far offered, but clear, tested, working, and generalized.
总结一下。它被称为布尔代数是有原因的：
如果您查看那里的真值表，您可以看到乘法是布尔代数，而简单的加法是异或。
回答你的问题：
Sum it up. It's called boolean algebra for a reason:
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:
这实际上取决于“改进”的含义：
更清晰？
泰瑟？
更一般？
更具可扩展性？
快点？
哪一项“改进”很大程度上取决于具体情况。
It really depends what you mean by "improved":
Clearer?
Terser?
More general?
More scalable?
Faster?
Which one is "improved" depends heavily on the situation.
这是使用 map/reduce 的另一个实现。在分布式环境中，这可以很好地扩展到数十亿个布尔值©。使用 MongoDB：
创建布尔值数据库
值：创建映射、归约函数：
编辑：我喜欢CurtainDog的 回答关于将map/reduce应用于通用列表，因此这里有一个map函数，它接受一个回调来确定是否应该对某个值进行计数。
运行映射/减少：
Here's another implementation using map/reduce. This scales well to billions of booleans© in a distributed environment. Using MongoDB:
Creating a database
valuesof booleans: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.
Running map/reduce:
在这里获取答案（到目前为止）：
并通过反编译器运行它们（javap -c X > results.txt）：
您可以看到 ?: 比原始版本的修复版本稍好。最好的一种是完全避免分支的一种。从指令较少（在大多数情况下）的角度来看，这很好，并且对于 CPU 的分支预测部分更好，因为分支预测中的错误猜测可能会导致 CPU 停顿。
我想说最有效的一个是来自 Moonshadow 的整体。它平均使用最少的指令，并减少 CPU 中管道停顿的机会。
为了 100% 确定，您需要找出每条指令的成本（以 CPU 周期为单位），不幸的是，这并不容易获得（您必须查看热点的来源，然后查看当时的 CPU 供应商规格）针对每个生成的指令进行）。
有关代码的运行时分析，请参阅 Rotsor 的更新答案。
Taking the answers (so far) here:
and running them through the decompiler (javap -c X > results.txt):
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.
直接代码的另一个例子：
显然，这不是最简洁的代码。
附录
另一个（稍微优化的）版本：
假设与 0 的比较将使用比与 2 的比较更快（或可能更少）的代码，这可能会运行得稍快一些。
Another example of direct code:
It's not the most succinct code, obviously.
Addendum
Another (slightly optimized) version of this:
This might run slightly faster, assuming that the comparison against 0 will use faster (or perhaps less) code than the comparison against 2.
还有另一种方法，但不是一个很好的方法：
Boolean哈希码值固定为 1231（表示 true）和 1237（表示 false），因此同样可以使用<= 3699Yet another way to do this but not a very good one:
The
Booleanhashcode values are fixed at 1231 for true and 1237 for false so could equally have used<= 3699最明显的一组改进是：
然后
但是这些改进很小。
The most obvious set of improvements are:
and then
But those improvements are minor.
我不喜欢三元（
从顶部答案中返回 a ? (b || c) : (b && c);），而且我认为我没有见过任何人提一下。它是这样写的：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:在 Clojure 中：
用法：
In Clojure:
Usage:
我想我还没有见过这个解决方案：
它的优点是，一旦达到您正在寻找的数字，它就会崩溃。因此，如果这是“这 1,000,000 个值中至少有 2 个为真”，其中前两个值实际上为真，那么它应该比一些更“正常”的解决方案更快。
I don't think I've seen this solution yet:
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.
我们可以将布尔值转换为整数并执行这个简单的检查：
We can convert the bools to integers and perform this easy check:
由于没有指定如何改进代码，我将努力改进代码，使其更有趣。这是我的解决方案：
如果有人想知道这段代码是否有效，这里有一个使用相同逻辑的简化：
}
这可以进一步归结为以下内容：
但现在它不再有趣了。
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:
In case anyone's wondering if this code works, here's a simplification using the same logic:
}
This can be boiled down further to the following:
But now it's not funny any more.
有太多方法可以做到这一点...
Too many ways to do this...
交流解决方案。
或者您可能更喜欢：
A C solution.
or you may prefer:
字面解释适用于所有主要语言：
但我可能会让人们更容易阅读，并且可以扩展到三种以上 - 这似乎被许多程序员忘记了：
A literal interpretation will work in all major languages:
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:
在C中：
In C:
最简单的方法（IMO）不混乱且易于阅读：
The simplest way (IMO) that is not confusing and easy to read:
作为 @TofuBeer TofuBeer 优秀帖子的补充，请考虑 @pdox pdox 的答案：
还要考虑“javap -c”给出的反汇编版本：
pdox 的答案编译为比之前任何答案都更少的字节代码。它的执行时间与其他的相比如何？
至少在我的计算机上，pdox 的答案仅比 @moonshadow Moonshadow 的答案稍快，使 pdox 的整体速度最快（在我的 HP/Intel 笔记本电脑上）。
As an addition to @TofuBeer TofuBeer's excellent post, consider @pdox pdox's answer:
Consider also its disassembled version as given by "javap -c":
pdox's answer compiles to less byte code than any of the previous answers. How does its execution time compare to the others?
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).
目前使用 Java 8，我真的更喜欢这样的东西：
Currenty with Java 8, I really prefer something like this:
通过真值表计算：
Calculated via a truth table: