一位面试官最近问了我这样一个问题:给定三个布尔变量a、b和c，如果三个变量中至少有两个为真，则返回true。
我的解决方案如下:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改进，但如何改进呢?
当前回答
最简单的方式(IMO)，不容易混淆，容易阅读:
// Three booleans, check if two or more are true
return ( a && ( b || c ) ) || ( b && c );
其他回答
return (a==b) ? a : c;
解释:
如果a==b，则两者都为真或都为假。如果两者都为真，我们已经找到了两个真布尔值，并可以返回真(通过返回a)。如果两者都为假，即使c为真，也不可能有两个真布尔值，因此我们返回假(通过返回a)。这是(a==b) ?一个部分。c呢?如果a==b为假，那么a或b中只有一个为真，所以我们找到了第一个真布尔值，剩下的唯一问题是c是否也为真，所以我们返回c作为答案。
为什么不逐字执行呢?：）
(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);
}
}
}
这将在我的机器上打印以下内容(在Intel Core 2 + sun java 1.6.0_15-b03上运行Ubuntu，带有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
我想知道，对于(a + b + c >= 2)情况，java虚拟机可以做什么来降低性能。
下面是如果我用-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版本胜出。
在运行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
供你参考，这只是一个完整加法器的执行部分。在硬件中，您可以根据不同的布尔表达式使用逻辑工作来确定最佳电路。我猜传统的异或解决方案要比海报上展示的不那么简洁的表达式花费更多的精力。
这个问题的非约简解是:
a'bc + abc' + abc + ab'c
减少使用k - map，可以得到:
bc + ab + ac
可以通过在a'bc和abc' minterms上使用exclusive或，并结合abc和ab'c minterms来进一步减少此值:
b(a ^ c) + ac
在c#中，我首先想到的是:
public bool lol(int minTrue, params bool[] bools)
{
return bools.Count( ( b ) => b ) >= minTrue;
}
应该很快。
调用应该是这样的:
lol( 2, true, true, false );
这样，您就将规则(两个必须为真)留给调用者，而不是将它们嵌入到方法中。
