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

我的解决方案如下:

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

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


当前回答

可读性应该是目标。阅读代码的人必须立即理解您的意图。这就是我的解。

int howManyBooleansAreTrue =
      (a ? 1 : 0)
    + (b ? 1 : 0)
    + (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;

其他回答

作为@TofuBeer TofuBeer精彩帖子的补充,考虑@pdox pdox的回答:

static boolean five(final boolean a, final boolean b, final boolean c)
{
    return a == b ? a : c;
}

再考虑一下它的分解版本,如"javap -c"所给出的:

static boolean five(boolean, boolean, boolean);
  Code:
    0:    iload_0
    1:    iload_1
    2:    if_icmpne    9
    5:    iload_0
    6:    goto    10
    9:    iload_2
   10:    ireturn

Pdox的答案编译成的字节代码比之前的任何答案都要少。它的执行时间与其他的相比如何?

one                5242 ms
two                6318 ms
three (moonshadow) 3806 ms
four               7192 ms
five  (pdox)       3650 ms

至少在我的电脑上,pdox的回答比@moonshadow moonshadow的回答稍微快一点,使得pdox的回答是最快的(在我的惠普/英特尔笔记本电脑上)。

我不喜欢三元(return a ?(b || c):(b && c);从最上面的答案),我想我没有看到任何人提到过它。它是这样写的:

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

它应该是:

(a || b && c) && (b || c && a)

此外,如果true自动转换为1,false自动转换为0:

(a + b*c) * (b + c*a) > 0

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

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

这个问题的非约简解是:

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

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

bc + ab + ac

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

b(a ^ c) + ac