检查三个布尔值中至少有两个为真

612

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

我的解决方案如下:

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

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


173
将返回语句内联。 - Finglas
82
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou) - Andrew Grimm
6
Thorbjørn 问道:C语言中是否使用0/非0来表示布尔值?我认为这种情况在C语言中不适用,例如atLeastTwo(0,2,0)。请问您的看法? - Ken
93
为什么人们会给那些最琐碎的问题点赞? - BlueRaja - Danny Pflughoeft
52
通俗易懂的问题会得到很多赞,而过于具体和技术性的问题则不会。 - Jay
显示剩余14条评论
65个回答

15

这要看你所谓的“改进”是什么意思:

更清晰了吗?

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

Terser是什么?

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.

哪个是“改善”的取决于具体情况。


14

以下是使用map/reduce实现的另一种方法。这适用于在分布式环境中处理数十亿个©布尔值。使用MongoDB:

创建一个名为values的布尔类型数据库:

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

创建 map 和 reduce 函数:

编辑:我喜欢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;
}

@Anurag:尽管我非常喜欢M/R和Google最近对它的推广(即使它不是FP中真正的M/R),但我倾向于认为你的回答是胡说八道。有数十亿行代码执行着现实世界的“东西”,其中没有一行使用map/reduce。回答这样的问题,用这个作为答案,在我的书中肯定会被标记为:“试图表现聪明”。更不用说大多数面试官无法判断你是否在胡说八道,因为他们实际上从未在自己的职业生涯中编写过一个使用M/R的程序。 - SyntaxT3rr0r
2
@Syntax - 每个人都有自己的观点。我的回答只是另一种看待问题的方法。当然,对于3个布尔值来说,听起来有些夸张,但这并不意味着我在这里想要显摆。这是解决问题的常见方法,每个人都在使用——将问题分解成小块。这就是数学归纳法的工作原理,也是大多数递归算法的工作原理,也是人们通常解决问题的方式。 - Anurag

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周期为单位),不幸的是这并不容易(您需要查看 hotspot 的源代码,然后查看 CPU 供应商规格的每个生成指令所需的时间)。
请参见 Rotsor 的更新答案,了解关于代码的运行时分析。

5
你只是看着字节码而已。你并不知道JIT会将带有分支的字节码转换为无分支的本机代码版本。但人们往往认为,在字节码中减少分支会更好。 - David Conrad

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进行比较的代码更快(或者更少),那么这样做可能会略微提高运行速度。


+1 @Loadmaster,很抱歉但您错了!这是这里最简洁明了的答案。(即简要且清晰地表达);) - Ash
微优化:++nn++ 更快因为在执行递增操作之前需要创建另一个副本 - M. Mimpen
仅适用于类对象。对于原始类型(如上面的 n),任何像样的编译器都将每个 ++ 操作编译成单个 CPU 指令,无论是前缀还是后缀。 - David R Tribble

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

但是这些改进很小。


12

还有一种方法可以做到这一点,但并不是特别好的方法:

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

Boolean 的哈希码值对于 true 固定为 1231,而 false 则为 1237,因此也可以使用 <= 3699


1
返回翻译后的文本:或者(a?1:0)+(b?1:0)+(c?1:0)>= 2 - Peter Lawrey

9

我不喜欢三目运算符(来自顶部回答的return a ? (b || c) : (b && c);),我认为我没有看到有人提到过它。它的写法是这样的:

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

8

Clojure中:

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

使用方法:

(at-least 2 true false true)

2
+1,很棒的通用版本展示了Lisp的强大之处。谢谢。 - dsmith

7

我们可以将布尔值转换为整数,然后执行这个简单的检查:

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

我不明白为什么这不是官方答案:它最简洁,执行速度最快,最容易理解。在C语言中,您无需转换类型:a+b+c>=2 - dargaud

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

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


可能应该这样写: 如果(++counter == howMany) 而不是分别进行递增和检查。 - Joe Enos
2
甚至更短:如果(b && (++counter == howMany)) - Joe Enos
1
我会使用 boolean ... boolValues 这种方式来使调用更加方便,但仍然需要传入一个数组。 - Stephen
我对Java不是很了解-不知道那个存在。这有点奇怪的语法,但它很有用-有时我会在C#中使用(params关键字),并且它确实使调用更加方便。或者,我不知道Java,但在.NET中,数组和所有集合都实现IEnumerable<T>,所以我可能会使用Java的等效物。 - Joe Enos
这个代码的性能与2of3示例相比如何? 返回a ? (b || c) : (b && c); - Iain Sproat
如果你想要三个中的两个,并且确定你想要三个中的两个,永远不会改变主意并想要四个中的两个,并且不介意你的代码难以阅读,那么 a?(b||c):(b&&c) 的例子肯定可以为你节省一两微秒的时间。 - Joe Enos

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接