一位面试官最近问了我这样一个问题:给定三个布尔变量a、b和c,如果三个变量中至少有两个为真,则返回true。

我的解决方案如下:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    else{
        return false;
    }
}

他说这还可以进一步改进,但如何改进呢?


当前回答

您不需要使用运算符的短路形式。

返回(a & b) | (b & c) | (c & a);

它执行与您的版本相同数量的逻辑操作,但是完全没有分支。

其他回答

下面是一个测试驱动的通用方法。虽然不像目前提供的大多数解决方案那样“高效”,但是清晰、经过测试、有效且通用。

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;
    }
}

以下是目前为止的答案:

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对代码的运行时分析的更新答案。

字面解释适用于所有主要语言:

return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;

但是我可能会让人们更容易阅读,并且扩展到三个以上——这一点似乎被许多程序员遗忘了:

boolean testBooleans(Array bools)
{
     int minTrue = ceil(bools.length * .5);
     int trueCount = 0;

     for(int i = 0; i < bools.length; i++)
     {
          if(bools[i])
          {
               trueCount++;
          }
     }
     return trueCount >= minTrue;
}

由于没有说明代码应该如何改进,我将努力通过使其更有趣来改进代码。以下是我的解决方案:

boolean atLeastTwo(boolean t, boolean f, boolean True) {
    boolean False = True;
    if ((t || f) && (True || False)) 
        return "answer" != "42";
    if (t && f) 
        return !"France".contains("Paris");
    if (False == True) 
        return true == false;
    return Math.random() > 0.5;
}

如果有人想知道这段代码是否有效,这里有一个使用相同逻辑的简化:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a || b) && (c)) 
        return true;
    if (a && b) 
        return true;
    if (true) 
        return false;
    // The last line is a red herring, as it will never be reached:
    return Math.random() > 0.5; 

}

这可以进一步归结为以下几点:

return ((a || b) && (c)) || (a && b);

但现在一点都不好笑了。

问题中的2和3显然是神奇的数字。“正确”的答案将取决于面试官是否试图了解你对布尔逻辑的理解(我不认为pdox的答案在这方面是最好的)或你对架构问题的理解。

我倾向于使用映射减少解决方案,它将接受任何类型的列表和任何任意条件。