Java 检查三个布尔值中是否至少有两个为真
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3076078/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Check if at least two out of three booleans are true
提问by user282886
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.
一位面试官最近问了我这个问题：给定三个布尔变量 a、b 和 c，如果三个中至少有两个为真，则返回真。
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?
他说这可以进一步改善，但如何？
采纳答案by polygenelubricants
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 aand bexactly once, and cat most once.
它测试a和b准确一次，c最多一次。
References
参考
回答by Rotsor
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 >= 2to be very safe).
在 C 中，您可以只编写a+b+c >= 2（或!!a+!!b+!!c >= 2非常安全）。
In response to TofuBeer's comparison of java bytecode, here is a simple performance test:
针对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);
}
}
}
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)):
这会在我的机器上打印以下内容（在 Intel Core 2 + sun java 1.6.0_15-b03 和 HotSpot Server VM（14.1-b02，混合模式）上运行 Ubuntu）：
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 degradesperformance over time for (a + b + c >= 2) case.
我想知道，对于 (a + b + c >= 2) 情况，java VM 会做什么会随着时间的推移降低性能。
And here is what happens if I run java with a -clientVM switch:
如果我使用-clientVM 交换机运行 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
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.
如果我在GNU Java Interpreter 中运行它，它会慢近 100 倍，但a&&b || b&&c || a&&c版本会胜出。
Results from Tofubeer with the latest code running OS X:
使用最新代码运行 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
Results from Paul Wagland with a Mac Java 1.6.0_26-b03-383-11A511
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
回答by TofuBeer
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.
但这些改进是微不足道的。
回答by moonshadow
You don't need to use the short circuiting forms of the operators.
您不需要使用运算符的短路形式。
return (a & b) | (b & c) | (c & a);
return (a & b) | (b & c) | (c & a);
This performs the same number of logic operations as your version, however is completely branchless.
这执行与您的版本相同数量的逻辑操作，但完全无分支。
回答by danatel
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;
回答by Hyman
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
回答by TofuBeer
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):
并通过反编译器运行它们（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.
您可以看到 ?: 比原始版本的修复版本略好。最好的一种是完全避免分支的一种。从更少的指令（在大多数情况下）和 CPU 的分支预测部分的角度来看，这很好，因为分支预测中的错误猜测会导致 CPU 停顿。
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.
我会说最有效的是来自moonshadow的整体。它平均使用最少的指令并减少 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).
为了 100% 确定您需要找出每条指令的成本（以 CPU 周期为单位），不幸的是这不是现成的（您必须查看热点的来源，然后查看 CPU 供应商的规格）为每个生成的指令采取）。
See the updated answer by Rotsor for a runtime analysis of the code.
有关代码的运行时分析，请参阅 Rotsor 的更新答案。
回答by malu
boolean atLeastTwo(boolean a, boolean b, boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
回答by David R Tribble
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.
这可能会运行得稍微快一些，假设与 0 的比较将使用比与 2 的比较更快（或可能更少）的代码。
回答by Carl Manaster
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;
}
}
