首页 文章

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

提问于
浏览
563

一位采访者最近问我这个问题:给定三个布尔变量a,b和c,如果三个中至少有两个为真,则返回true .

我的解决方案是:

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

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

30 回答

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

    说明:

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

  • 212

    在C:

    return !!a + !!b + !!c >= 2;
    
  • 12

    我不喜欢三元(顶部答案中的 return a ? (b || c) : (b && c); ),而且我没有看到有人提到它 . 它是这样写的:

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

    这是一种以测试为导向的通用方法 . 不像迄今为止提供的大多数解决方案那样“高效”,而是清晰,经过测试,工作和推广 .

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

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

    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
    
  • 142

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

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

  • 13

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

    更清晰?

    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.
    

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

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

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

  • 13

    最简单的方法(IMO)不会让人感到困惑和易读:

    // Three booleans, check if two or more are true
    
    return ( a && ( b || c ) ) || ( b && c );
    
  • 27

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

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

    但现在不再有趣了 .

  • 14

    在Ruby中:

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

    哪个可以在JavaVM上的JRuby中运行 . ;-)

  • 12

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

    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
    }
    

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

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

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

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

  • 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 moonshadow的答案略快,使得pdox的整体速度最快(在我的HP / Intel笔记本电脑上) .

  • 5

    最明显的改进包括:

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

    但这些改进很小 .

  • 10

    而不是写:

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

    它只测试 ab 一次,最多测试 c 一次 .

    参考文献

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

    一个C解决方案 .

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

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

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

    Boolean 哈希码值固定为1231为真,1237为false,因此可能同样使用 <= 3699

  • 24

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

    int howManyBooleansAreTrue =
          (a ? 1 : 0)
        + (b ? 1 : 0)
        + (c ? 1 : 0);
    
    return howManyBooleansAreTrue >= 2;
    
  • 4

    直接代码的另一个例子:

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

    不是显然,最简洁的代码 .

    Addendum

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

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

    这可能会稍快一些,假设与0的比较将比使用2的比较使用更快(或可能更少)的代码 .

  • 6

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

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

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

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

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

    如果你愿意,可以把它放在一个函数中,但它不是很复杂 . 该解决方案在逻辑上简洁而有效 .

  • 131

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

    return a ^ b ? c : a
    
  • 4

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

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

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

  • 15

    这样的问题可以用_465128解决:

    | 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
    
  • 3

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

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

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

    创建一个数据库 values 的布尔值:

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

    创建 Map ,减少功能:

    Edit :我喜欢CurtainDog's answer关于将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;
    }
    
  • 3

    为什么不按字面意思实现呢? :)

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

    这将在我的机器上打印以下内容(使用HotSpot Server VM(14.1-b02,混合模式)在Intel Core 2 sun java 1.6.0_15-b03上运行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可以做什么会降低性能 .

    如果我用 -client VM开关运行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中运行它,它会慢几百倍,但 a&&b || b&&c || a&&c 版本会胜出 .

    使用运行OS X的最新代码从Tofubeer获得的结果:

    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
    
  • 6
    return 1 << $a << $b << $c >= 1 << 2;
    
  • 6

    Clojure

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

    用法:

    (at-least 2 true false true)
    

相关问题