Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have

if (!b && c || a && c)
  //do action a
else 
  //...

Due to some internal relationship between a, b, and c. !b && c || a && c is proved to be equivalent to (! a && b) || c.

I just wonder will (! a && b) || c be simpler than !b && c || a && c? Can you prove it? Assume the chances of a,b,c to be True or False is equal.

I'm not asking which style is better. I'm asking which statement has lower computational complexity. Just like asking quick sort and Bubble Sort, which has lower computational complexity. You will not answer it depends, it is related to compiler and hardware because some hardware have special instruction for Bubble Sort. I hope to hear nlog(n) and n^2.

share|improve this question
    
do you mean ((!b && c) || (a && c)) or (((!b && c) || a) && c) –  Pieter B Aug 30 '13 at 7:59
3  
This isn't something that will be provable in general. It will depend on the data type used (which you haven't specified), how the code interacts with your optimizer, the actual values and how they interact with your branch-prediction hardware etc. If you're interested, benchmark it. If you're very interested, benchmark it and examine the compiler output (assembler, bytecode or whatever it may be). –  Useless Aug 30 '13 at 8:06
    
@PieterB I mean ((!b && c) || (a && c)) . OR has less priority than AND. –  LoveRight Aug 30 '13 at 8:23
2  
As boolean operations are among the least expensive instructions to execute and "if"s are one of the areas that hardware optimization concentrates on (speculative execution, instruction re-ordering etc.) then I would be surprised if you could measure any difference between the two versions. –  James Anderson Aug 30 '13 at 8:43
1  
The fewer operations you need to do, the less computationally complex it is. This is obvious. Mathematical proofs and Big O notation don't really make sense here, because the time taken averages out as a constant factor, so both will be of O(n) –  TZHX Aug 30 '13 at 9:34
show 7 more comments

4 Answers

a good optimizer will make any difference here moot

you can think in how the short circuit works:

with if ((!b && c) || (a && c)) you get

if(b)goto OR2;
if(c)goto then_lbl;
OR2:
if(!a)goto else_lbl;
if(!c)goto else_lbl;
then_lbl://...

while with if((! a && b) || c) (the actual equivalent) you get

if(a) goto OR2;
if(b) goto then_lbl;
OR2:
if(!c) goto else_lbl;
then_lbl://..

so there is no real difference (you always go through 2 or 3 branches)

But I'll repeat my point: this kind of micro optimization is utterly useless to worry about unless it is part of a provable bottleneck and most times the problem isn't a malformed if statement

here you'll find that readability trumps speed

share|improve this answer
add comment

Are you sure it's

(! a && b)

rather than

!(a && b)

?

If not, the brackets are unnecessary and just lead to confusion.

Either way, generally the less operations you have the better for the computer, and in both AND or OR conditions it's better to put the "simplest" first, your most effective way of writing this for the computer (not necessarily the reader) would be:

c || b && ! a

This is assuming C-style operator precedence for the logical operators.

share|improve this answer
    
I'm sure it's (! a && b) || c. The brackets are unnecessary. Sorry for confusing. –  LoveRight Aug 30 '13 at 8:31
add comment

The two statements have the same computational complexity. Both execute in constant time (in complexity terms), which can be written O(1). Since the number of input states is finite (8), it could hardly be otherwise.

If a, b and c are general expressions rather than variable, !b && c || a && c may cause c to be evaluated twice. If c is not idempotent (i.e. if running c a second time doesn't necessarily do what it did the first time), all bets are off. The two expressions you propose also don't execute a, b and c in the same order in all cases, so if their running time depends on the order in which they are called, again, all bets are off.

If what you're wondering is not, in fact, the computational complexity (which deals with asymptotic measures of amounts of computation) but exact the number of computation steps, then the answer is that there is no general answer. The exact number of computation steps depends on which model of computation you choose. For asymptotic analysis, the choice of model is mostly irrelevant: any reasonable model gives the same result (or sometimes there are a few reasonable choices of model, and you need to say which one you're using). If you want a finer analysis, you have to provide a detailed model.

It is completely useless to refine the analysis in this case because the practical difference is going to hinge on a lot of factors that cannot readily be predicted, including:

  • what machine code the compiler generates (which depends on the compiler, the compiler version, the optimization settings, the target CPU, and the surrounding code);
  • the exact model of CPU (since this will be affected by the amount of prefetching, the branch prediction, the instruction and data pipelines depth, etc.);
  • what other code executed before (since this influences the state of the pipelines, the cache, the branch predictor, etc.).
share|improve this answer
add comment

Well cant really answer this because

if (!b && c || a && c)

is not equal to

if ((! a && b) || c)

The truth tables for each are below, abc output:

000 0
001 1
010 0
011 0
100 0
101 1
110 0
111 1

this doesnt match the above

000 0
001 1
010 1
011 1
100 0
101 1
110 0
111 1

test program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int a,b,c;


int main ( void )
{
    for(a=0;a<2;a++)
    for(b=0;b<2;b++)
    for(c=0;c<2;c++)
    {
        printf("%u%u%u ",a,b,c);
        if (!b && c || a && c)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    printf("\n");

    for(a=0;a<2;a++)
    for(b=0;b<2;b++)
    for(c=0;c<2;c++)
    {
        printf("%u%u%u ",a,b,c);
        if ((! a && b) || c)
        {
            printf("1\n");
        }
        else
        {
            printf("0\n");
        }
    }

    return(0);
}

Please add more parenthesis to improve the order of operations, and/or post an equivalent equation, then we can talk about how they differ in complexity.

This is equivalent

    if (c && (!(!a && b)))

note clang's opinion on this syntax:

fun.c:5:12: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if (!b && c || a && c) return(1);
        ~~~^~~~ ~~
fun.c:5:12: note: place parentheses around the '&&' expression to silence this
      warning
    if (!b && c || a && c) return(1);
           ^
        (      )
fun.c:5:22: warning: '&&' within '||' [-Wlogical-op-parentheses]
    if (!b && c || a && c) return(1);
                ~~ ~~^~~~
fun.c:5:22: note: place parentheses around the '&&' expression to silence this
      warning
    if (!b && c || a && c) return(1);
                     ^
                   (     )

Using arm as a test target, the answer is not going to be deterministic BTW, it is compiler and target and system dependent on which is faster, less computation, etc. Looks on the surface with an arm and its instruction set features the first solution with gcc is clean and deterministic (no branches).

This will of course change with each compiler and target and also with whatever code surrounds that if statement. (note the version of gcc and clang/llvm can/will create different results).

unsigned int bool1 ( unsigned int a, unsigned int b, unsigned int c )
{
    if (!b && c || a && c) return(1);
    return(0);
}

unsigned int bool2 ( unsigned int a, unsigned int b, unsigned int c )
{
    if (c && (!(!a && b))) return(1);
    return(0);
}

//gcc

//00000000 <bool1>:
   //0: e2900000    adds    r0, r0, #0
   //4: 13a00001    movne   r0, #1
   //8: e3510000    cmp r1, #0
   //c: 03800001    orreq   r0, r0, #1
  //10: e3520000    cmp r2, #0
  //14: 03a00000    moveq   r0, #0
  //18: 12000001    andne   r0, r0, #1
  //1c: e12fff1e    bx  lr

//00000020 <bool2>:
  //20: e3520000    cmp r2, #0
  //24: 0a000005    beq 40 <bool2+0x20>
  //28: e2711001    rsbs    r1, r1, #1
  //2c: 33a01000    movcc   r1, #0
  //30: e3500000    cmp r0, #0
  //34: 01a00001    moveq   r0, r1
  //38: 13810001    orrne   r0, r1, #1
  //3c: e12fff1e    bx  lr
  //40: e1a00002    mov r0, r2
  //44: e12fff1e    bx  lr

//clang

//bool1:                                  @ @bool1
    //cmp   r1, #0
    //bne   .LBB0_2
    //cmp   r2, #0
    //movne r0, #1
    //movne pc, lr
//.LBB0_2:                                @ %lor.lhs.false
    //cmp   r2, #0
    //movne r2, #1
    //cmp   r0, #0
    //movne r0, #1
    //and   r0, r0, r2
    //mov   pc, lr

//bool2:                                  @ @bool2
    //mov   r3, r0
    //cmp   r2, #0
    //beq   .LBB1_2
    //mov   r0, #1
    //cmp   r3, #0
    //movne pc, lr
    //cmp   r1, #0
    //movne r0, #0
    //b .LBB1_3
//.LBB1_2:                                @ %if.end
    //mov   r0, #0
//.LBB1_3:                                @ %return
    //mov   pc, lr
share|improve this answer
    
Due to some internal relationship between a, b, and c. !b && c || a && c is proved to be equivalent to (! a && b) || c. I mean a,b,c have certain relationship, which makes the two statement equivalent. I'm sure. It is given. –  LoveRight Sep 26 '13 at 4:11
    
As I have demonstrated it is very simple to test the equality or inequality. Go through the 8 combinations for a, b, c and see the results. –  dwelch Sep 26 '13 at 13:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.