Verifique se pelo menos dois de três booleanos são verdadeiros

579

Um entrevistador recentemente me fez esta pergunta: dadas três variáveis ​​booleanas, a, bec, retornam true se pelo menos duas das três forem verdadeiras.

Minha solução é a seguinte:

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

Ele disse que isso pode ser melhorado ainda mais, mas como?

user282886
fonte
170
Inline a declaração de retorno.
Finglas
45
Parece uma entrevista de "quem tem o mais alto QI". Eu falharia.
Chris Dutrow
79
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)
Andrew Grimm
92
Por que as pessoas votam nas perguntas mais triviais?
BlueRaja - Danny Pflughoeft
46
Perguntas gerais e fáceis de entender recebem muitos votos positivos. Perguntas muito específicas e técnicas não.
Jay

Respostas:

820

Em vez de escrever:

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

Escreva:

return someExpression;

Quanto à própria expressão, algo como isto:

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

ou isso (o que você achar mais fácil de entender):

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

Ele testa ae bexatamente uma vez, ec no máximo uma vez.

Referências

poligenelubrificantes
fonte
144
+1: lovely solução para o quebra-cabeça, mas espero que não vemos nada parecido com isso no mundo real :)
Julieta
124
@ Juliet: Eu não sei, acho que se esse fosse um requisito do mundo real (com nomes de variáveis ​​reais), seria muito bom. Considere return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam), isso parece bom para mim.
Andrzej Doyle
18
Eu não acho que isso parece ruim , mas se o requisito no domínio for entendido como "pelo menos dois", acho que seria mais fácil de ler atLeastTwo(hasgoodAttendance, passedCoursework, passedExam). A idéia de "pelo menos 2 bools são verdadeiros" é genérica o suficiente para merecer sua própria função.
Ken
17
@Lese: Pedir o código mais micro-otimizado nas entrevistas cara a cara é impraticável, e ouso dizer, inútil. As micro-otimizações, quando orientadas pela necessidade, são guiadas por resultados de criação de perfil em tempo de execução, não por instintos humanos (que são conhecidos por serem terríveis). Você certamente pode perguntar aos entrevistados o processo pelo qual você otimizaria isso ainda mais; isso é mais importante que o resultado em si.
polygenelubricants
17
O operador ternário é um idioma comum que você deve poder ler. Se você não consegue ler, deve estudá-lo até conseguir. O uso do operador ternário não é algo que considero "inteligente" no sentido depreciativo. Mas sim, eu colocaria isso como o corpo de uma chamada de método se você estiver usando a lógica "pelo menos dois".
Stephen P
494

Apenas para usar o XOR para responder a um problema relativamente direto ...

return a ^ b ? c : a
Tim Stone
fonte
160
Uau, solução legal. Mas, para mim, sua versão invertida é mais fácil de entender: a == b? a: c
Rotsor
5
a ^ b? c: a ^ b? c: a ^ b? c: a
alexanderpas
4
Sim, o XOR recebe uma pressão tão ruim e você raramente tem a chance de usá-la.
EightyOne Unite
19
@ Stimul8d talvez porque, para os booleanos, seja o mesmo que! =, Mas menos legível? Descobrindo isso foi um momento eureka para mim ...
Tikhon Jelvis
2
Prefiro a forma puramente binária: return ((a ^ b) & c) | (a e b). É sem ramificação (mais rápida) e fácil de ler: (a ou b é verdadeiro e c é verdadeiro) ou (a e b são ambos verdadeiros). Observe que (a | b) e (a ^ b) funcionam com essa fórmula.
Flanglet
217

Por que não implementá-lo literalmente? :)

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

Em C, você pode escrever a+b+c >= 2(ou!!a+!!b+!!c >= 2 para ser muito seguro).

Em resposta à comparação do TofuBeer do bytecode Java, aqui está um teste de desempenho simples:

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

Isso imprime o seguinte na minha máquina (executando o Ubuntu no Intel Core 2 + sun java 1.6.0_15-b03 com a VM do HotSpot Server (14.1-b02, modo misto)):

Primeira e segunda iterações:

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

Iterações posteriores:

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

Gostaria de saber o que java VM fazer isso degrada desempenho ao longo do tempo no caso (a + b + c> = 2).

E aqui está o que acontece se eu executar o java com um -clientswitch VM:

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

Mistério...

E se eu executá-lo no GNU Java Interpreter , fica quase 100 vezes mais lento, mas oa&&b || b&&c || a&&c versão vence então.

Resultados do Tofubeer com o código mais recente executando o 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

Resultados de Paul Wagland com um 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
Rotsor
fonte
4
a+b+c >= 2: isso não funciona com negativos, certo? Você pode ter que fazer a !!acoisa, não tenho certeza.
polygenelubricants
8
<s> -1. Você nunca deve fazer isso por C. Você não sabe qual é o valor de true (poderia ser tão facilmente quanto -1). </s> Na verdade, acho que C99 inclui em seu padrão que true é definido como 1. Mas Eu ainda não faria isso.
Mark Peters
1
Isso é possível se sua entrada for resultado de operações booleanas? E isso é possível para o tipo "bool" em C ++?
Rotsor
2
@Rotsor: Ninguém disse que a entrada deve ser o resultado de operações booleanas. Mesmo sem negativos, você está brincando com fogo, como se o definisse como 2, sua condição teria falsos positivos. Mas não me importo com isso tanto quanto não gosto da ideia de misturar booleanos em aritmética. Sua solução Java é clara, pois não depende de conversões diferenciadas do tipo booleano para um número inteiro.
Mark Peters
7
Seja cauteloso com as
marcas de microbench
143

Esse tipo de pergunta pode ser resolvido com um mapa de Karnaugh :

      | C | !C
------|---|----
 A  B | 1 | 1 
 A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

a partir do qual você deduz que precisa de um grupo para a primeira linha e dois grupos para a primeira coluna, obtendo a solução ideal de poligenelubrificantes:

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case
Jack
fonte
10
@ Justin, o mapa de Karnaugh reduziu o número de operações lógicas de 3 ANDs e 2 ORs para 2 ANDs e 2 ORs. @ Jack, obrigado por me lembrar da existência do mapa de Karnaugh.
Tachy
14
+1 para algo novo. Minha próxima especificação funcional incluirá um K-map, seja ele necessário ou não.
Justin R.
2
Talvez a baixa legibilidade possa ser compensada por (1) a tabela apropriada no comentário e (2) o teste unitário apropriado ... +1 para algo útil aprendido na escola.
moala 02/02
140

Legibilidade deve ser o objetivo. Alguém que lê o código deve entender sua intenção imediatamente. Então aqui está a minha solução.

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

return howManyBooleansAreTrue >= 2;
danatel
fonte
21
Eu concordo com a premissa, mas (a && b) || (b && c) || (a && c) é muito mais legível que a sua solução IMHO.
Adrian Grigore
62
Hmm, agora eu preciso de uma versão "dois dos QUATRO booleanos" ... a versão da danatel é muito mais fácil agora.
Arafangion
6
Ou em Scala:Seq(true, true, false).map(if (_) 1 else 0).sum >= 2
retroceda
5
@retronym: Hmm, não. O modo Java funciona bem no Scala e é mais legível e mais eficiente.
Seun Osewa
134
return (a==b) ? a : c;

Explicação:

Se a==b, então ambos são verdadeiros ou ambos são falsos. Se ambos são verdadeiros, encontramos nossos dois booleanos verdadeiros e podemos retornar true (retornando a). Se ambos são falsos, não pode haver dois booleanos verdadeiros, mesmo que csejam verdadeiros; portanto, retornamos falso (retornando a). Essa é a (a==b) ? aparte. Que tal : c? Bem sea==b for falso, então exatamente um de aou bdeve ser verdadeiro; portanto, encontramos o primeiro booleano verdadeiro, e a única coisa que importa é se ctambém é verdadeiro; portanto, retornamos ccomo resposta.

Boann
fonte
8
c nunca é testado ... brilhante!
precisa saber é o seguinte
Usos relação transitiva da igualdade e o fato de que um booleano é verdadeiro ou falso +1
Christophe Roussy
3
Tão elegante! Eu tive que checar com caneta e papel para acreditar :) Parabéns a você, senhor!
Adrian
3
Eu penso sobre isso como "se ae bconcordam, eles têm a maioria, para ir com o que é, então, eles discordam, então cé o voto de qualidade"
Ben Millwood
34

Você não precisa usar as formas de curto-circuito dos operadores.

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

Isso executa o mesmo número de operações lógicas que sua versão, porém é completamente sem ramificação.

sombra da Lua
fonte
11
Por que você deseja forçar cinco avaliações quando eu poderia fazer? Realmente não executa o mesmo número de operações lógicas na verdade. De fato, sempre teria um desempenho maior.
Mark Peters
2
Eu acho que misturar aritmética binária e aritmética booleana é uma má idéia. É como apertar parafusos na parede com uma chave inglesa. O pior de tudo é que eles têm semânticas diferentes.
Peter Tillemans
12
@ Mark - pode ser mais rápido ... dependendo do efeito de uma previsão de ramificação incorreta no pipeline da CPU. No entanto, é melhor deixar essas micro otimizações para o compilador JIT.
Stephen C
4
É bom fazer algo assim em Java (ou em qualquer outra linguagem) ... com algumas ressalvas: 1) precisa ser mais rápido (neste caso, acredito que seja, veja minha segunda resposta) 2) preferível significativamente mais rápido (não tenho certeza se é), 3) o mais importante, pois é "ímpar". Desde que sirva a um propósito e esteja documentado, não há problema em "quebrar as regras" quando fizer sentido.
TofuBeer
11
@ Peter Tillemans Não há mistura com operadores binários, em Java esses são operadores booleanos.
starblue
27

Aqui está uma abordagem geral orientada a testes. Não é tão "eficiente" quanto a maioria das soluções oferecidas até agora, mas é clara, testada, funcionando e generalizada.

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;
    }
}
Carl Manaster
fonte
8
Uau, nunca vi um método totalmente testado antes de ver este.
Rotsor
51
Pessoalmente, acho esse código horrível, por muitas razões. Eu não vou votar, mas se eu já visse isso no código de produção, eu xingaria. Uma operação booleana extremamente simples não precisa ser complicada assim.
precisa saber é o seguinte
10
Eu ficaria muito interessado em saber seus motivos, @CaptainCasey. Eu acho que esse é um código muito bom. Há uma boa função generalizada que é fácil de entender, fácil de verificar e uma função específica que tira proveito dela, também fácil de entender e verificar. No mundo real, eu os tornava públicos e os colocava em outra classe; além disso - eu felizmente colocaria esse código em produção. Ah - sim - eu renomearia countBooleans () para countTrue ().
precisa saber é o seguinte
5
se não se trata de desempenho, esta solução parece quase perfeita para mim: muito fácil de ler e extensível. É exatamente para isso que são feitos os var-args.
atamanroman
7
Que diabos, gente? Este é um código claro e bem testado, e a única razão pela qual parece muito é porque inclui os testes. A +++, votaria novamente.
Christoffer Hammarström
24

Resumir. É chamado álgebra booleana por um motivo:

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

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

Se você olhar para as tabelas verdadeiras, poderá ver que a multiplicação é booleana e, simplesmente, adição é xor.

Para responder sua pergunta:

return (a + b + c) >= 2
memet
fonte
2
Esta é a solução mais elegante, na minha opinião.
Torbjørn Kristoffersen
9
Erro de principiante, porém, um valor booleano não for 0, isso não significa que é sempre 1.
tomdemuyt
13
Exceto que a tag na postagem diz "Java" e você não pode escrever "a + b + c" quando definidos como booleanos em Java.
Jay
Para trabalhar em Java, teria que ser return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2.
precisa
Duh, votei nisso porque achei que era uma pergunta em C ++ ... por que estou lendo perguntas sobre java? : /
Carlo Wood
15
boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}
malu
fonte
15

Realmente depende do que você quer dizer com "aprimorado":

Mais claro?

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

Mais general?

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

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

        if(count > x) return true;
    }

    return false;
}

Mais escalável?

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

Mais rápido?

// Only profiling can answer this.

Qual deles é "melhorado" depende muito da situação.

kerkeslager
fonte
14

Aqui está outra implementação usando mapear / reduzir. Isso escala bem para bilhões de booleanos © em um ambiente distribuído. Usando o MongoDB:

Criando um banco valuesde dados de booleanos:

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

Criando o mapa, reduza as funções:

Edit : Eu gosto da resposta do CurtainDog sobre aplicar o mapa / reduzir a listas genéricas, então aqui vai uma função de mapa que recebe um retorno de chamada que determina se um valor deve ser contado ou não.

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

Mapa em execução / redução:

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
fonte
@ Anurag: por mais que eu goste de M / R e da exposição que o Google recentemente deu a ele (mesmo que não seja o verdadeiro M / R da FP), eu tenderia a chamar besteira! T em sua resposta. Existem bilhões e bilhões de linhas de código executando o "material" do Mundo Real [TM], onde não há uma única linha de mapa / redução usada. Alguém responder tal pergunta um com esta é definitivamente sinalizado no meu livro como: "tentando jogar o smartie" . Sem mencionar que a maioria dos entrevistadores não seria capaz de dizer se você está tentando enganá-los ou não, porque eles nunca escreveram um único programa usando M / R em sua carreira.
SyntaxT3rr0r
2
@ Syntax - Todo mundo tem direito a sua opinião. Minha resposta é apenas mais uma abordagem para analisar o problema. Claro, parece exagerado para 3 valores booleanos, mas isso não significa que estou tentando ser a espertinha aqui. Essa é uma abordagem comum à solução de problemas usada por todos - decomponha o problema em pequenos pedaços. É assim que a indução matemática funciona, é assim que funcionam os algoritmos mais recursivos e é assim que as pessoas resolvem os problemas em geral.
Anurag
13

Tomando as respostas (até agora) aqui:

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

e executando-os pelo descompilador (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
}

Você pode ver que os?: Ones são um pouco melhores que a versão corrigida do seu original. O melhor é o que evita ramificações por completo. Isso é bom do ponto de vista de menos instruções (na maioria dos casos) e melhor para partes de previsão de ramificação da CPU, pois uma suposição incorreta na previsão de ramificação pode causar paralisação da CPU.

Eu diria que o mais eficiente é o da sombra da lua em geral. Ele usa o menor número de instruções, em média, e reduz a chance de paralisações de pipeline na CPU.

Para ter 100% de certeza de que você precisaria descobrir o custo (em ciclos de CPU) para cada instrução, que infelizmente não está disponível (você precisaria procurar a fonte do hotspot e, em seguida, os fornecedores de CPU especifica o tempo. tomadas para cada instrução gerada).

Consulte a resposta atualizada por Rotsor para uma análise em tempo de execução do código.

TofuBeer
fonte
5
Você está apenas olhando para o bytecode. Pelo que você sabe, o JIT pegará uma versão com ramificações no bytecode e a transformará em uma versão sem ramificações no código nativo. Mas alguém tenderia a pensar que menos ramificações no bytecode seriam melhores.
David Conrad
13

Outro exemplo de código direto:

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

Não é o código mais sucinto, obviamente.

Termo aditivo

Outra versão (ligeiramente otimizada) disso:

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

Isso pode ser um pouco mais rápido, supondo que a comparação contra 0 use código mais rápido (ou talvez menos) do que a comparação contra 2.

David R Tribble
fonte
+1 @Loadmaster, desculpe, mas você está errado! Esta é a resposta mais sucinta aqui. (isto é, brevemente e claramente expresso);)
Ash
Micro-otimização: ++né mais rápido do que n++ porque você precisa criar outra cópia antes de fazer o incremento .
M. Mimpen
@ M.Mimpen: Apenas para objetos de classe. Para tipos primitivos (como nacima), qualquer compilador decente compilará cada ++operação em uma única instrução de CPU, seja pré ou pós.
precisa saber é o seguinte
12

Ainda outra maneira de fazer isso, mas não muito boa:

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

Os Booleanvalores de código de hash são fixados em 1231 para true e 1237 para false, portanto, poderiam igualmente ter usado<= 3699

barrowc
fonte
1
ou (a? 1: 0) + (b? 1: 0) + (c? 1: 0)> = 2
Peter Lawrey
12

O conjunto mais óbvio de melhorias são:

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

e depois

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

Mas essas melhorias são pequenas.

TofuBeer
fonte
10

Não gosto de ternário ( return a ? (b || c) : (b && c);da primeira resposta) e acho que não vi ninguém mencionar isso. Está escrito assim:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a) {
        return b||c;
    } 
    else {
        return b&&C;
    }
Roman A. Taycher
fonte
8

Em Clojure :

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

Uso:

(at-least 2 true false true)
Vagif Verdi
fonte
2
+1 Ótima versão genérica mostra o poder dos Lisps. Obrigado,
dsmith
6

Acho que ainda não vi essa solução:

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

Sua vantagem é que, uma vez atingido o número que você está procurando, ele quebra. Portanto, se isso foi "pelo menos 2 dos 1.000.000 valores são verdadeiros", onde os dois primeiros são realmente verdadeiros, deve ser mais rápido do que algumas das soluções mais "normais".

Joe Enos
fonte
Provavelmente deveria ser: if (++ counter == howMany) em vez de incrementar e depois verificar separadamente.
Joe Enos
2
Ou ainda mais curto: if (b && (++ contra == howMany))
Joe Enos
1
Eu faria boolean ... boolValuespor isso é mais fácil de chamada, mas ainda recebe um array
Stephen
Não estou atualizado no meu Java - não sabia que isso existia. É uma sintaxe estranha, mas é útil - de vez em quando eu faço isso em C # (palavra-chave params), e isso torna as coisas mais agradáveis ​​de se chamar. Ou, eu não sei sobre Java, mas no .NET, matrizes e todas as coleções implementam IEnumerable <T>, então provavelmente usaria o equivalente de Java.
Joe Enos
Como o desempenho disso se compara ao exemplo 2of3? retornar um? (b || c): (b && c);
usar o seguinte
6

Podemos converter os bools em números inteiros e executar esta verificação fácil:

(int(a) + int(b) + int(c)) >= 2
vine'th
fonte
6

Como não foi especificado como o código deve ser aprimorado, tentarei melhorar o código, tornando-o mais divertido. Aqui está a minha solução:

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

Caso alguém esteja se perguntando se esse código funciona, aqui está uma simplificação usando a mesma lógica:

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; 

}

Isso pode ser resumido ainda mais ao seguinte:

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

Mas agora não é mais engraçado.

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

Muitas maneiras de fazer isso ...

Duby
fonte
3
Parece mais com C #. Isto deve ser mencionado como tal na resposta porque a questão é Java-alvo :)
BalusC
5

Solução CA.

int two(int a, int b, int c) {
  return !a + !b + !c < 2;
}

ou você pode preferir:

int two(int a, int b, int c) {
  return !!a + !!b + !!c >= 2;
}
Mark Edgar
fonte
4
return 1 << $a << $b << $c >= 1 << 2;
Kevin
fonte
Não vi a resposta da Suvega antes de colocar isso, praticamente a mesma coisa.
Kevin
Isso realmente funciona? Suponho que seja PHP, mas não tenho acesso a ele, mas vou perguntar: o que acontece se $ a for 0?
Mark Edgar
@ Mark Na verdade, não funciona se $ a é 0. Isso foi um descuido. Obrigado por apontar isso. :)
Kevin
4

A maneira mais simples (IMO) que não é confusa e fácil de ler:

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

return ( a && ( b || c ) ) || ( b && c );
abelito
fonte
Funcionalmente, é o mesmo. Sintaticamente, facilita a leitura para os que não estão acostumados ao uso do operador condicional do ponto de interrogação. Estou disposto a apostar que mais pessoas sabem usar operadores AND e OR do que o número de pessoas que sabem usar operadores condicionais de ponto de interrogação. A pergunta original pede uma "resposta aprimorada". A resposta aceita simplifica a resposta, mas levanta uma questão muito interessante sobre o que se considera melhoria. Você programa para legibilidade universal ou simplicidade? Para mim, esta é uma melhoria em relação a resposta aceita :)
Abelito
Preferências pessoais. Para mim, é muito mais fácil entender o operador ternário mais limpo do que esta solução.
Nico
1
Ah, sim, eu vi esse problema e fiquei pensando por que ninguém mais mencionou essa solução. Se você escrever a lógica do OP como álgebra booleana, obterá A B + A C + B C, que possui cinco operações. Pela propriedade associativa, você pode escrever A * (B + C) + B C, que possui quatro operações.
Vivian River
É o mesmo que a resposta de Jack (19 de junho) (C && (A || B)) || (A && B)acabou de alterar os nomes das variáveis ​​* ...
user85421
4

Uma interpretação literal funcionará em todos os principais idiomas:

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

Mas eu provavelmente facilitaria a leitura e a expansão para mais de três pessoas - algo que parece ser esquecido por muitos programadores:

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;
}
blakecallens
fonte
4

Como complemento da excelente publicação de @TofuBeer TofuBeer, considere a resposta de @pdox pdox:

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

Considere também sua versão desmontada, conforme fornecida por "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

A resposta do pdox é compilada com menos código de bytes que qualquer uma das respostas anteriores. Como o tempo de execução se compara aos outros?

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

Pelo menos no meu computador, a resposta do pdox é apenas um pouco mais rápida que a resposta de @moonshadow moonshadow, tornando o pdox o mais rápido em geral (no meu laptop HP / Intel).

Rex Barzee
fonte
3

Em Ruby:

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

O que poderia ser executado no JRuby no JavaVM. ;-)

user373826
fonte
3

Ele provavelmente não está procurando nada complicado como operadores de comparação bit a bit (normalmente não complicado, mas com booleanos, é extremamente estranho usar operadores bit a bit) ou algo que seja muito indireto, como converter para int e resumi-los.

A maneira mais direta e natural de resolver isso é com uma expressão como esta:

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

Coloque-o em uma função, se preferir, mas não é muito complicado. A solução é logicamente concisa e eficiente.

stinky472
fonte
3

Em C:

return !!a + !!b + !!c >= 2;
Matt Joiner
fonte
Na verdade, esta resposta está errada ... deve ser> = 2, pois você precisa de pelo menos dois booleanos verdadeiros, não exatamente dois.
Paul Wagland 19/09/11
@ Paul Wagland: Obrigado pela captura.
Matt Joiner
@ergosys: Eu respondi duas vezes?
precisa saber é o seguinte