检查三个布尔值中是否至少有两个是真的

这种问题可以通过卡诺图来解决:

      | 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

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

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

return howManyBooleansAreTrue >= 2;

return (a==b) ? a : c;

说明:

如果a==b,那么两者都是真的或两者都是假的.如果两者都是真的,我们找到了两个真正的布尔值,并且可以返回true(通过返回a).如果两者都是假的,即使c是真的也不会有两个真正的布尔值,所以我们返回false(通过返回a).那是(a==b) ? a一部分.怎么样: c？好吧,如果a==b是假的,那么恰好是一个a或b必须是真的,所以我们找到了第一个真正的布尔值,唯一重要的是if c也是真的,所以我们返回c作为答案.

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

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

总结一下.它被称为布尔代数,原因如下:

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

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

如果你看一下那里的真值表,你可以看到乘法是布尔值,而且只是加法是xor.

回答你的问题:

return (a + b + c) >= 2

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

这真的取决于你所说的"改进":

更清晰？

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.

哪一个"改进"在很大程度上取决于具体情况.

这是使用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;
}

运行map/reduce:

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

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

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."":()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
}

您可以看到？:1比原始版本的固定版本略好一些.最好的是完全避免分支的那个.从较少指令(在大多数情况下)的观点来看,这是好的,并且对于CPU的分支预测部分更好,因为分支预测中的错误猜测可能导致CPU停滞.

我认为最有效的一个是来自moonshadow整体的那个.它平均使用最少的指令,并减少CPU中流水线停顿的可能性.

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

请参阅Rotsor的更新答案,以获取代码的运行时分析.

直接代码的另一个例子:

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的比较使用更快(或可能更少)的代码.

最明显的改进是:

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

但这些改进很小.

另一种方法是做到这一点,但不是一个非常好的方式:

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

该Boolean哈希码值是固定的,在1231真正和1237为false,所以可以同样使用了<= 3699

我不喜欢三元(return a ? (b || c) : (b && c);从最佳答案),我不认为我见过有人提过它.它是这样写的:

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

在Clojure中:

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

用法:

(at-least 2 true false true)

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

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个是真的",前两个实际上是真的,那么它应该比一些更"正常"的解决方案更快.

我们可以将bools转换为整数并执行这个简单的检查:

(int(a) + int(b) + int(c)) >= 2

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

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

但现在不再有趣了.

Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
     return (System.Convert.ToInt16(val1) +
             System.Convert.ToInt16(val2) +
             System.Convert.ToInt16(val3)) > 1;
}

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

AC解决方案.

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