Avoid IF ELSE Branching

Question

I was looking at branching, and I wanted to avoid branching in a loop, which basically was doing this

for(z=0; z<8; z++){
   if(0xff&&(array[z])!=0 ){
       break;
   }
 }

so my plan was actually to replace it with the following :

for(z=0; z<8; z++){
     (0xff&&(array[z])==0 ) ? continue :  break;
}

but well, this does not work, and I understand why, but would like to know if there is another way of doing this, in a similar way.

Thanks

Your "plan" IS using branching; its just using a different syntax to say it. — Scott Hunter, Feb 26 '14 at 16:11
Apart from the reasons this doesn't work as is, the conditional operator is a branch too, so you wouldn't have achieved your goal anyway. — , Feb 26 '14 at 16:11
What are you trying to achieve? Why do you want to avoid branching in the loop? (Additional note: `0xff && array[z] != 0` is equivalent to `array[z] != 0`) — James Greenhalgh, Feb 26 '14 at 16:13
Actually, just `for (z = 0; z < 8 && (0xff & array[z]) == 0; z++)`. — mike.dld, Feb 26 '14 at 16:18

score 2 · Answer 1 · answered Feb 26 '14 at 16:12

2

You could include the break condition with the termination condition (i.e. z<8) of the for statement. But you can't avoid branching; this is just a different way to express it.

answered Feb 26 '14 at 16:12

Scott Hunter

48,888
12
60
101

score 0 · Answer 2 · answered Feb 26 '14 at 16:13

0

Using a ? is still a branch, it's just another way of writing if. As you only have 8 indicies, you can unroll your loop.

inline int getZ() { if (array[0] & 0xff) return 0; if (array[1] & 0xff) return 1; ... and so on }

As a side note, you want to use the & bitwise operator, not the boolean && operator, otherwise your expression will always be true.

answered Feb 26 '14 at 16:13

Zebra North

11,412
7
37
49

I'd leave the loop unrolling to the compiler until I encounter evidence that (1) the compiler doesn't unroll and (2) it makes a difference. – Feb 26 '14 at 16:15
@delnan Neither of us can know that, but at least it gives the questioner an option to try. If he's working on a small microcontroller for example this could make a very big difference. – Zebra North Feb 26 '14 at 16:22
OP can't even get their code to compile, much less run correctly. That should take priority, don't you think? ;-) I'm not generally opposed to teaching optimization tricks, but I can think of dozens of thinks that probably benefit OP more than this (including other micro optimizations that are less likely to be pointless because the compiler already did them). – Feb 26 '14 at 16:26

score 0 · Answer 3 · answered Feb 26 '14 at 16:15

How about:

int bits = 0;
for(z=0; z<8; z++) bits |= array[z];
if ((bits & 0xff) != 0) printf("Found it!\n");

The above has only one extra if, rather than one-per-loop-iteration. If your goal is to make the code's execution faster, it might help or it might not. (My guess is it won't make a lot of difference if you're running on a modern CPU)

score 0 · Answer 4 · answered Feb 26 '14 at 16:17

0

int z = 0;
while(z<8 && (0xff&&array[z]==0)) z++;

NOTE: maybe you meant to mask array[z] with 0xff? (i.e. using the bit-wise & operator?)

answered Feb 26 '14 at 16:17

Gianluca Ghettini

11,129
19
93
159

yes I did, my mistake :) – Anoracx Feb 26 '14 at 16:31

HelloWorld123456789 · Answer 5 · 2014-02-26T16:40:05.663

0

Your negation of the expression is wrong.

0xff&&(array[z])!=0 is true when 0xff is true (which is always true) and (array[z])!=0 is true.

So 0xff&&(array[z])!=0 evaluates to (array[z])!=0 which on negation gives (array[z]==0)

So you need to modify (0xff&&(array[z])==0 ) ? continue : break; to (array[z]==0) ? continue : break;

edited Feb 26 '14 at 16:40

answered Feb 26 '14 at 16:24

HelloWorld123456789

5,299
3
23
33

You're not wrong, but this work can be cut down by either dropping the pointless conjunction w/ TRUE or fix the erroneous use of `&&` in place of `&`. – Feb 26 '14 at 16:28
What do you mean by _fixing the erroneous use of && in place of &_? – HelloWorld123456789 Feb 26 '14 at 16:33
The condition should involve `0xff & array[z]`, not `0xff && array[z]`. The latter makes no sense, and OP [has stated that the former was intended](http://stackoverflow.com/questions/22046899/avoid-if-else-branching/22047240?noredirect=1#comment33428001_22047089). – Feb 26 '14 at 16:35
Right. It didn't come to my mind that `0xff&&(array[z])!=0` can be mistakenly written as `(0xff & array[z]) != 0`. Edited! – HelloWorld123456789 Feb 26 '14 at 16:40

Avoid IF ELSE Branching

5 Answers5