596

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

我的解决方案如下:

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

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

4

65 回答 65

835

而不是写:

if (someExpression) {
    return true;
} else {
    return false;
}

写:

return someExpression;

至于表达式本身,是这样的:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a ? (b || c) : (b && c);
}

或者这个(你觉得更容易掌握的那个):

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

它只测试一次,a最多一次。bc

参考

于 2010-06-19T15:46:35.290 回答
504

只是为了使用 XOR 来回答一个相对简单的问题......

return a ^ b ? c : a
于 2010-06-21T17:43:51.500 回答
225

为什么不从字面上实现呢?:)

(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 和 HotSpot Server VM(14.1-b02,混合模式)上运行 Ubuntu):

第一次和第二次迭代:

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 VM 会随着时间的推移降低性能。

如果我使用-clientVM 交换机运行 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 Interpreter中运行它,它会慢近 100 倍,但a&&b || b&&c || a&&c版本会胜出。

Tofubeer 运行 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
于 2010-06-19T15:49:45.967 回答
146
return (a==b) ? a : c;

解释:

如果a==b,则两者都为真或都为假。如果两者都为真,我们找到了两个真布尔值,并且可以返回真(通过返回a)。如果两者都是假的,即使c是真,也不可能有两个真布尔值,所以我们返回假(通过返回a)。这就是(a==b) ? a部分。怎么样: c?那么 ifa==b是假的,那么aorb必须是真的,所以我们找到了第一个真布尔值,剩下的唯一重要的是 ifc也是真的,所以我们c作为答案返回。

于 2010-06-22T05:51:31.423 回答
145

这类问题可以用卡诺图解决:

      | 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
于 2010-06-19T16:10:17.497 回答
142

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

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

return howManyBooleansAreTrue >= 2;
于 2010-06-19T16:03:57.767 回答
34

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

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

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

于 2010-06-19T15:51:42.997 回答
29

这是一种测试驱动的通用方法。不像迄今为止提供的大多数解决方案那样“高效”,但清晰、经过测试、有效且通用。

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;
    }
}
于 2010-06-19T19:58:30.647 回答
24

总结一下。它被称为布尔代数是有原因的:

  0 x 0 = 0
  1 x 0 = 0
  1 x 1 = 1

  0 + 0 = 0
  1 + 0 = 1
  1 + 1 = 0 (+ carry)

如果您查看那里的真值表,您会发现乘法是布尔值,而简单的加法是异或。

要回答您的问题:

return (a + b + c) >= 2
于 2010-06-21T20:00:25.560 回答
15
boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}
于 2010-06-19T17:38:56.243 回答
15

这真的取决于你所说的“改进”是什么意思:

更清晰?

boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
    return (a && b) || (a && c) || (b && c);
}

特塞尔?

boolean moreThanTwo(boolean a, boolean b, boolean c)
{
    return a == b ? a : c;
}

更一般?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(boolean b : bs)
    {
        count += b ? 1 : 0;

        if(count > x) return true;
    }

    return false;
}

更具可扩展性?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(int i < 0; i < bs.length; i++)
    {
        count += bs[i] ? 1 : 0;

        if(count > x) return true;

        int needed = x - count;
        int remaining = bs.length - i;

        if(needed >= remaining) return false;
    }

    return false;
}

快点?

// Only profiling can answer this.

哪一个被“改进”在很大程度上取决于情况。

于 2010-06-22T22:31:13.153 回答
14

这是另一个使用 map/reduce 的实现。这可以很好地扩展到分布式环境中的数十亿个布尔值©。使用 MongoDB:

创建一个values布尔数据库:

db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});

创建地图,减少功能:

编辑:我喜欢CurtainDog 关于将 map/reduce 应用于通用列表的 回答,所以这里有一个 map 函数,它接受一个回调来确定是否应该计算一个值。

var mapper = function(shouldInclude) {
    return function() {
        emit(null, shouldInclude(this) ? 1 : 0);
    };
}

var reducer = function(key, values) {
    var sum = 0;
    for(var i = 0; i < values.length; i++) {
        sum += values[i];
    }
    return sum;
}

运行地图/减少:

var result = db.values.mapReduce(mapper(isTrue), reducer).result;

containsMinimum(2, result); // true
containsMinimum(1, result); // false


function isTrue(object) {
    return object.value == true;
}

function containsMinimum(count, resultDoc) {
    var record = db[resultDoc].find().next();
    return record.value >= count;
}
于 2010-06-19T23:03:40.703 回答
13

在这里回答(到目前为止):

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 停顿。

我想说最有效的一个是整体来自moonshadow的那个。它平均使用最少的指令并减少 CPU 中流水线停顿的机会。

为了 100% 确定您需要找出每条指令的成本(以 CPU 周期为单位),不幸的是,这并不容易获得(您必须查看热点的来源,然后查看 CPU 供应商的规格为每个生成的指令采取)。

有关代码的运行时分析,请参阅 Rotsor 的更新答案。

于 2010-06-19T16:14:39.830 回答
13

直接代码的另一个例子:

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 的比较更快(或可能更少)的代码,这可能会运行得稍快一些。

于 2010-06-19T19:34:40.387 回答
12

最明显的改进是:

// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    return false;
}

进而

// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return ((a && b) || (b && c) || (a && c));
}

但这些改进很小。

于 2010-06-19T15:51:21.533 回答
12

还有另一种方法可以做到这一点,但不是很好:

return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);

哈希码值固定为 1231 表示真,Boolean1237 表示假,因此同样可以使用<= 3699

于 2010-06-20T04:32:35.943 回答
10

我不喜欢三元(return a ? (b || c) : (b && c);来自最佳答案),而且我认为我没有看到有人提到它。它是这样写的:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a) {
        return b||c;
    } 
    else {
        return b&&C;
    }
于 2010-06-21T17:16:28.353 回答
8

Clojure中:

(defn at-least [n & bools]
  (>= (count (filter true? bools)) n)

用法:

(at-least 2 true false true)
于 2010-06-21T22:24:04.477 回答
7

我认为我还没有看到这个解决方案:

boolean atLeast(int howMany, boolean[] boolValues) {
  // check params for valid values

  int counter = 0;
  for (boolean b : boolValues) {
    if (b) {
      counter++;

      if (counter == howMany) {
        return true;
      }
    }
  }
  return false;
}

它的优点是,一旦达到您要查找的数字,它就会中断。因此,如果这是“这 1,000,000 个值中至少有 2 个是正确的”,而前两个实际上是正确的,那么它应该比一些更“正常”的解决方案更快。

于 2010-06-21T22:23:18.127 回答
7

我们可以将布尔值转换为整数并执行以下简单检查:

(int(a) + int(b) + int(c)) >= 2
于 2011-07-10T11:41:47.310 回答
6

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

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

但现在已经不好笑了。

于 2011-10-12T08:13:35.150 回答
5
Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
     return (System.Convert.ToInt16(val1) +
             System.Convert.ToInt16(val2) +
             System.Convert.ToInt16(val3)) > 1;
}

有太多方法可以做到这一点...

于 2010-06-21T17:16:25.427 回答
5

交流解决方案。

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;
}
于 2010-06-21T19:23:40.437 回答
5

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

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;
}
于 2010-06-21T21:48:02.930 回答
4

最简单的方法(IMO),不会令人困惑且易于阅读:

// Three booleans, check if two or more are true

return ( a && ( b || c ) ) || ( b && c );
于 2010-06-20T12:11:58.283 回答
4
return 1 << $a << $b << $c >= 1 << 2;
于 2010-06-21T19:58:24.377 回答
4

通过真值表计算:

return (a & b) | (c & (a ^ b));
于 2010-06-22T05:02:57.010 回答
4

作为@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 月影的回答稍微快一点,这使得 pdox 的整体速度最快(在我的 HP/Intel 笔记本电脑上)。

于 2010-06-22T20:23:04.083 回答
4

在 C 中:

return !!a + !!b + !!c >= 2;
于 2011-01-29T12:16:23.407 回答
4

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

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return Stream.of(a, b, c).filter(active -> active).count() >= 2;
}
于 2016-11-10T15:17:37.047 回答
3

这种阅读效果更好:

if (a) {
    return b || c;
} 
else {
    return b && c;
}
于 2010-06-22T01:10:13.093 回答
3

仅供参考,这只是全加器的进位。在硬件中,您可以使用逻辑努力来根据不同的布尔表达式确定最佳电路。我猜想传统的 XOR 解决方案会比海报展示的不那么简洁的表达方式花费更多的精力。

于 2010-06-22T05:54:47.307 回答
3

在红宝石中:

[a, b, c].count { |x| x } >= 2

可以在 JavaVM 上的 JRuby 中运行。;-)

于 2010-06-23T03:00:30.663 回答
3

看到这个问题我的第一个想法是:

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

看了其他帖子,我承认

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

优雅得多。我想知道相对运行时间是什么。

不过,无论如何,我认为这种解决方案比

return a&b | b&c | a&c;

多样性,因为它更容易扩展。如果稍后我们添加第四个必须测试的变量怎么办?如果变量的数量是在运行时确定的,并且传递给我们一个未知大小的布尔数组怎么办?依赖于计数的解决方案比依赖于列出所有可能组合的解决方案更容易扩展。此外,在列出所有可能的组合时,我怀疑更容易出错。就像尝试为“any 3 of 4”编写代码一样,并确保您既不会遗漏任何代码,也不会重复任何代码。现在尝试使用“任意 5 of 7”。

于 2010-06-23T17:33:43.480 回答
3

他可能不是在寻找像按位比较运算符这样复杂的东西(通常不是复杂的,但使用布尔值,使用按位运算符非常奇怪)或非常迂回的东西,比如转换为 int 并将它们相加。

解决这个问题最直接、最自然的方法是使用如下表达式:

a ? (b || c): (b && c)

如果您愿意,可以将它放在一个函数中,但这并不是很复杂。该解决方案在逻辑上简洁高效。

于 2010-06-25T09:19:53.703 回答
3

它应该是:

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

此外, iftrue会自动转换为1and :false0

(a + b*c) * (b + c*a) > 0
于 2010-09-05T14:56:36.470 回答
2

三元运算符使书呆子的汁液流动起来,但它们可能会令人困惑(使代码的可维护性降低,从而增加了错误注入的可能性)。Jeff Attwood在这里说得很好:

这是一个完美的例子,将完全无意义的一次性写入时间节省与数十次读取时间理解惩罚进行权衡——这让我思考。

避免三元运算符,我创建了以下函数:

function atLeastTwoTrue($a, $b, $c) {
        $count = 0;

        if ($a) { $count++; }
        if ($b) { $count++; }
        if ($c) { $count++; }

        if ($count >= 2) {
                return true;
        } else {
                return false;
        }
}

这和其他一些解决方案一样酷吗?不,更容易理解吗?是的。这会导致代码更易于维护、错误更少吗?是的。

于 2010-06-21T17:13:56.210 回答
2

绝对是一个关于你如何解决问题/思考的问题,而不是你的实际编码能力。

一个稍微简洁的版本可能是

返回 ((a ^ b) && (b ^ c)) ^ b

但就像之前的海报所说的那样,如果我在我正在处理的任何代码中看到这一点,就会有人听到。:)

于 2010-06-21T21:30:21.437 回答
2

如果目标是为三个操作数返回按位三分之二的值,那么算术和迭代方法往往相对无效。在许多 CPU 架构上,一个好的形式是“return ((a | b) & c) | (a & b);”。这需要四个布尔运算。在单累加器机器(在小型嵌入式系统中很常见)上,每个字节可能总共需要 7 条指令。形式“返回(a & b) | (a & c) | (b & c);” 可能看起来更好看,但它需要五个布尔运算,或者在单累加器机器上每个字节需要九条指令。

顺便说一下,在 CMOS 逻辑中,计算“三分之二”需要十二个晶体管(为了比较,反相器需要两个,二输入 NAND 或 NOR 需要四个,三输入 NAND 或 NOR 需要六个)。

于 2010-06-21T23:04:33.333 回答
2

我没有看到其他人指出的一件事是,在求职面试的“请给我写一些代码”部分做的标准事情是说“你能改进一下吗?” 或“您对此是否完全满意”或“是否已尽可能优化?” 当你说你完成了。您可能会听到“您将如何改进”作为“这可能会得到改进;如何?”。在这种情况下,将if(x) return true; else return false;成语改为 justreturn x是一种改进——但请注意,有时他们只是想看看你对这个问题的反应。我听说有些面试官会坚持认为完美的代码存在缺陷,只是为了看看你是如何应对的。

于 2010-06-22T00:07:47.080 回答
2

对这个问题的最佳答案应该是“作为一名员工,重要的是我写它以便我的意思是明确的,同时在必要时保持效率以提高绩效。” 我是这样写的:

function atLeastTwoAreTrue(a, b, c) {
    return (a && b) || (b && c) || (a && c);
}

实际上,测试是如此人为,以至于如果您使用简单的注释来适应它,那么编写一个最快、最神秘的方法是完全可以接受的。但是,总的来说,在这个单线世界中,我们需要在这个世界中更具可读性的代码。:-)

于 2010-06-22T04:36:25.843 回答
2

C#中,我脑海中浮现:

public bool lol(int minTrue, params bool[] bools)
{
    return bools.Count( ( b ) => b ) >= minTrue;
}

应该很快。

调用如下所示:

lol( 2, true, true, false );

这样,您将规则(两个必须为真)留给调用者,而不是将它们嵌入方法中。

于 2010-06-22T19:04:08.757 回答
2
int count=0;

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a)
        count++;
    if (b)
        count++;
    if (c)
        count++;

    if (count>1)
        return true;
    else
        return false;
}
于 2010-06-22T23:33:21.697 回答
2

提出的问题中的 2 和 3 绝对是魔术数字。“正确”的答案将取决于面试官是否试图了解您对布尔逻辑的掌握(我认为 pdox 的答案在这方面可能不是最好的)或您对架构问题的理解。

我倾向于使用 map-reduce 解决方案,该解决方案将接受具有任意条件的任何类型的列表。

于 2010-06-23T03:32:16.753 回答
2

我找到了这个解决方案。

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    bool result = !(a ^ b ^ c) && !(!a & !b & !c) || (a & b & c);
    return result;
}
于 2010-06-23T04:45:30.670 回答
2

让三个布尔值是 A、B 和 C....

您可以使用 k-MAP 并附带一个布尔表达式......

在这种情况下,布尔表达式将为 A(B+C) + C

或 if((A && (B || C )) || C ) { return true; } 否则返回假;

于 2010-07-29T10:47:20.870 回答
2

这个问题的非简化解决方案是:

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

使用 K-Maps 减少,得到:

bc + ab + ac

可以通过在 a'bc 和 abc' 最小术语上使用独占或并结合 abc 和 ab'c 最小术语来进一步减少这种情况:

b(a ^ c) + ac
于 2011-07-12T17:56:48.550 回答
2

怎么样(a||b) && (a||c)- Java,使用三个比较而不是 OP 的六个。

错了,我应该早点检查。

于 2011-09-15T19:54:53.317 回答
2

不是在性能方面,而是在良好的代码(可重用的可扩展和可读代码)

     static boolean trueBooleans (int howMany,boolean ... bools)
     {
      int total = 0;

      for (boolean b:bools)
        if (b && (++total == howMany)) return true;


      return false;
    }

以我的拙见,在编写 Java 时,轻松处理意外更改和没有重复代码比简洁(脚本语言领域)或快速程序更重要。

于 2012-02-01T13:35:15.677 回答
1

X = OR(a+b,c)

ABC X

1 1 0 1

0 0 1 1

0 1 1 1

于 2010-06-21T22:33:03.567 回答
1

C:

if (!!a + !!b + !!c >= 2)
于 2010-08-04T09:20:29.863 回答
1

如果我将布尔值转换为数字,并且该数字不是 2 的幂,则它至少有两个 true。

a*4 + b*2 + c*1 = N
return( N != 0 && (N&(N-1)) != 0)

我只是提供一个替代方案。

于 2012-01-30T14:27:13.337 回答
1

这个怎么样:

(a - b) ? c : a
于 2012-04-20T17:48:36.677 回答
1

使用 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
于 2014-12-16T03:59:20.983 回答
0
函数 atLeastTwoTrue($a, $b, $c) {

  整数计数 = 0;
  count = (a ? count + 1 : count);
  计数 = (b ? 计数 + 1 : 计数);
  计数 = (c ? 计数 + 1 : 计数);
  返回(计数> = 2);
}
于 2010-06-21T18:08:12.930 回答
0

在我看来,三分之三是非常任意的数字,并且该函数应该与任意数字一起使用。因此,为了回答这个问题,我会编写一个函数来计算数组中的 x 是否为真,例如,

bool istrue ( int x, bool[] list)
    y = count true in list
    return y >= x
于 2011-01-18T20:33:08.810 回答
0

使用三元运算符解决问题的最简单形式是:

return a ? (b ? true : c) : (b ? c : false);

您可能还想通过对需求的双重否定来投资寻找解决方案,这意味着您需要最多满足一个假值而不是至少两个真值。

于 2012-01-31T20:45:00.400 回答
0

函数ko返回答案:

static int ho(bool a)
{
    return a ? 1 : 0;
}

static bool ko(bool a, bool b, bool c)
{
    return ho(a) + ho(b) + ho(c) >= 2 ? true : false;
}
于 2012-03-27T13:28:20.593 回答
0
public static boolean atLeast(int atLeastToBeTrue, boolean...bools){
    int booleansTrue = 0;
    for(boolean tmp : bools){
        booleansTrue += tmp ? 1 : 0;
    }
    return booleansTrue >= atLeastToBeTrue;
}

您可以从aka中选择at least您想要真实的数量:-)varargsboolean[]

于 2015-02-08T19:31:18.490 回答
0

这在算术运算的帮助下非常简单。

boolean a = true;
boolean b = false;
boolean c = true;


// Exactly One boolean value true.
if((a?1:0)+(b?1:0)+(c?1:0)==1) 
   return true;
else
   return false;

// Exactly 2 boolean value true.
if((a?1:0)+(b?1:0)+(c?1:0)==2) 
   return true;
else
   return false;

这就是你如何增加常量的值来检查有多少布尔值true

于 2021-05-11T08:31:09.013 回答
0

如果您有很多布尔值,那么运算符重载很容易。

operator fun Boolean.unaryPlus() = if (this) 1 else 0
// ...
if(+bool1 + +bool2 + ... + +boolN > 2) {
    // ...
}
于 2022-01-01T14:53:07.320 回答
-1

另一个:

return a? b||c : b&&c
于 2018-05-05T18:38:09.387 回答
-4

我相信使用普通的布尔运算符 (a || b) && (b || c) 很好而且更简单。

您可以将 3 个字母中的任何一个与其他两个字母中的任何一个交换,它仍然是相同的表达式。

于 2010-06-22T00:07:14.490 回答
-6

我认为最简单的解决方案是:

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

于 2013-04-23T15:12:26.700 回答
-7

我的第一个想法是

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

但为了便于阅读,我喜欢你们建议的更好的 a+b+c>=2 解决方案

于 2010-06-21T20:11:57.293 回答