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

我的解决方案如下:

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

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


当前回答

另一种方法是使用Java 8的Stream功能,用于任意数量的布尔值。如果Stream在处理所有元素之前达到极限,则会短路:

public static boolean atLeastTrue(int amount, Boolean ... booleans) {
    return Stream.of(booleans).filter(b -> b).limit(amount).count() == amount;
}

public static void main(String[] args){
    System.out.println("1,2: " + atLeastTrue(1, true, false, true));
    System.out.println("1,1: " + atLeastTrue(1, false, true));
    System.out.println("1,0: " + atLeastTrue(1, false));
    System.out.println("1,1: " + atLeastTrue(1, true, false));
    System.out.println("2,3: " + atLeastTrue(2, true, false, true, true));
    System.out.println("3,2: " + atLeastTrue(3, true, false, true, false));
    System.out.println("3,3: " + atLeastTrue(3, true, true, true, false));
}

输出:

1,2: true
1,1: true
1,0: false
1,1: true
2,3: true
3,2: false
3,3: true

其他回答

以下是目前为止的答案:

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

X = OR(a+b,c)

a b c X

1, 1, 0, 1

0, 0, 1, 1

0, 1, 1, 1

另一个直接代码的例子:

int  n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);

显然,这不是最简洁的代码。

齿顶高

另一个(稍微优化的)版本:

int  n = -2;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 0);

这可能会运行得稍微快一点,假设与0的比较将比与2的比较使用更快(或更少)的代码。

这个问题的非约简解是:

a'bc + abc' + abc + ab'c

减少使用k - map,可以得到:

bc + ab + ac

可以通过在a'bc和abc' minterms上使用exclusive或,并结合abc和ab'c minterms来进一步减少此值:

b(a ^ c) + ac

目前的Java 8,我真的更喜欢这样的东西:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return Stream.of(a, b, c).filter(active -> active).count() >= 2;
}