一位面试官最近问了我这样一个问题:给定三个布尔变量a、b和c，如果三个变量中至少有两个为真，则返回true。
我的解决方案如下:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改进，但如何改进呢?
当前回答
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.
其他回答
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);
}
C解。
int two(int a, int b, int c) {
return !a + !b + !c < 2;
}
或者你可能更喜欢:
int two(int a, int b, int c) {
return !!a + !!b + !!c >= 2;
}
以下是目前为止的答案:
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
}
你可以看到?:那些比你原来的修复版本稍好。最好的方法是完全避免分支的方法。从更少的指令(在大多数情况下)的角度来看，这很好，对于CPU的分支预测部分来说也更好，因为分支预测中的错误猜测可能会导致CPU失速。
我觉得最有效的是《月影》里的那个。它平均使用最少的指令，减少了CPU中管道停顿的机会。
为了100%确定，您需要找出每条指令的成本(以CPU周期为单位)，不幸的是，这是不容易获得的(您必须查看热点的源代码，然后查看CPU供应商的规格，以确定每条生成指令所花费的时间)。
请参阅Rotsor对代码的运行时分析的更新答案。
这类问题可以用卡诺图来解决:
| C | !C
------|---|----
A B | 1 | 1
A !B | 1 | 0
!A !B | 0 | 0
!A B | 1 | 0
由此推断，第一行需要一组，第一列需要两组，得到聚基因润滑剂的最优解:
(C && (A || B)) || (A && B) <---- first row
^
|
first column without third case
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.
