CODEWITHSUNDEEP
cmath
Shakil Ahamed
Shakil Ahamed

Reputation: 577

Optimization: removing branch

I know a little C. I tried to write a program which uses no conditional statement but add odd numbers and multiply even numbers for a given array of integers. It was not very hard to write if odd add n else add 0 part. But, I couldn't work it out for the multiplication part. The solution seems to be multiply with 1 if odd else with n.

So, my question is given an integer, how you can transform it to 1 if it is odd else to the given integer. no conditional is allowed. Or, a better idea if possible. Thanks in advance.

Upvotes: 1

Views: 232

Answers (8)

Ulfalizer
Ulfalizer

Reputation: 4762

Here's another multiplication-less version (that also assumes two's complement). The logic is to & the number with with 11...11 (-1) for even numbers (11...1x where x is don't care would work too... maybe that could be used somehow) and with 00...01 for odd numbers. The problem then boils down to transforming odd and even numbers into those masks.

n&(((n&1) << 1) - 1)

(n&1) << 1 is 0 for even numbers and 2 for odd numbers. Subtracting one gives the desired masks.

(As said, you'd usually be better off doing n % 2 ? n : 1 rather than trying to second-guess the optimizer though. The compiler might generate a branchless conditional move for that if it thinks it's worthwhile.)

Upvotes: 0

Lutz Lehmann
Lutz Lehmann

Reputation: 26040

In other answers it was already pointed out that the indicator for odd and even is i%2 and (i+1)%2.

You can use this to solve the full problem in one line:

result = (i%2)*(number+i)+((i+1)%2)*number*i

You have to care that i is never negative. If that remains possible, then you can normalize the situation by a double mod operation: (2+i%2)%2 and (2+(i+1)%2)%2.

Of course, using the branching this can be made shorter as in

result = (i%2)?(i+number):(i*number)

Upvotes: 0

rici
rici

Reputation: 241911

Without multiplication, assuming 2s complement arithmetic (cast i to unsigned if not):

/* implements odd(i) ? 1 : n */
(((i&1)-1)&(n-1)) + 1
  • i&1 is 1 if i is odd, 0 otherwise, so
  • (i&1)-1 is 0 if i is odd, -1 otherwise.
  • Since the 2s-complement representation of -1 has all bits set to 1:
  • ((i&1)-1)&(n-1) is 0 if i is odd, (n-1) otherwise, so
  • (((i&1)-1)&(n-1))+1 is 1 if i is odd, n otherwise.

Whether that's faster than multiplication depends heavily on architecture; on modern CPUs it's doubtful, but on embedded architectures it would be. It certainly is not faster than a compiler-generated conditional move, and it's hardly easy to read. Still...

Upvotes: 4

user3528438
user3528438

Reputation: 2817

res = (i % 2) ? 1: number;

Conditional execution, or, branch predication is the best shot.

Small branches are not so evil nowadays.

Edit It's branch predication, not branch prediction.

http://en.wikipedia.org/wiki/Branch_predication

Upvotes: 0

blind.wolf
blind.wolf

Reputation: 133

You can check last bit easily. This way, you know that number is odd or even.

last_bit = number & 0x01;
first_number = last_bit;

If last bit is zero, first number is zero. If not (odd), then it's 1.

Then you take last_bit and invert that last bit

last_bit = (last_bit+1) & 0x01;
second_number = last_bit * n;

Now second_number is either n or 0.

result = (first_number + second_number);

Upvotes: 2

Severin Pappadeux
Severin Pappadeux

Reputation: 20130

Ok, asked to provide an answer. Expression

res = (i % 2) + ((i+1) % 2) * number;

will return 1 if i is odd, and given number otherwise

Upvotes: 4

barak manos
barak manos

Reputation: 30146

There you go:

int Get1IfOddValOtherwise(int val)
{
    return (1-(val&1))*(val-1)+1;
}

Upvotes: 1

bolov
bolov

Reputation: 75854

So let me shamelessly rip off the comment of @SeverinPappadeux and change it a little bit so I can claim it as my own:

res = i % 2 + (1 - i % 2) * number;
      ^^^^^    ^^^^^^^^^
odd:    1         0
even:   0         1

Upvotes: 2

Related Questions