Efficient ways to calculate (-1)^n in C++

Question

I would like to know which are the most efficient methods to calculate (-1)^n in terms of bit operations and code length.

The following examples assume integer n:

int a=(n%2==0?1:-1);
int b=(n&1?-1:1);

I don't care about the ease of understanding the code.

Viewing the generated assembly or doing a benchmark would be a good start if you really care about this for performance. — chris, May 30 '16 at 23:49
In terms of code length `int a=(n%2?-1:1);` is better than `int a=(n%2==0?1:-1);` — Jerry Jeremiah, May 30 '16 at 23:50
A) Show me the benchmark that shows this is a bottleneck B) Show me the assembly that shows the compiler didnt optimize those to the same thing already — Borgleader, May 30 '16 at 23:51
_"I don't care about the ease of understanding the code."_ LOL, Assembly masters chime in. Is that actually considered useful for future research? — πάντα ῥεῖ, May 30 '16 at 23:53
`(-1)^n` is rarely used on its own. For instance, if you're calculating it as part of a convergent series, you're better off calculating two subsequent terms in each iteration. More context is needed to answer this X/Y question. — , May 30 '16 at 23:56
@Borgleader: well, I would hope those two particular statements wouldn't optimize to the same thing, side the second is a constant "-1" (the condition should be `n&1` to detect oddness. ;-) — Nick Matteo, May 30 '16 at 23:57
There are going to be datasets with different best algorithms. Without a description of the data, there is no "best". — Yakk - Adam Nevraumont, May 30 '16 at 23:58
@Kundor I assumed it was a typo on OPs part, otherwise it makes no sense to ask which two pieces of unrelated code is the fastest :) — Borgleader, May 31 '16 at 00:00

Maxim Egorushkin · Answer 1 · 2016-05-31T00:38:33.540

With gcc 6.1 both produce the same assembly:

int f(int n) {
  return n % 2 ? -1 : 1;
}

int g(int n) {
  return n & 1 ? -1 : 1;
}

Assembly:

f(int):
        movl    %edi, %eax
        andl    $1, %eax
        negl    %eax
        orl     $1, %eax
        ret
g(int):
        movl    %edi, %eax
        andl    $1, %eax
        negl    %eax
        orl     $1, %eax
        ret

Which is equivalent to function:

int h(int n) {
  return -(n & 1) | 1;
}

Interestingly, gcc compilers 4.4.7 to 5.3 compile into longer assembly, the same for these versions.

Efficient ways to calculate (-1)^n in C++

1 Answers1