Search code examples
language-agnostic

Computing powers of -1


Is there an established idiom for implementing (-1)^n * a?

The obvious choice of pow(-1,n) * a seems wasteful, and (1-2*(n%2)) * a is ugly and not perfectly efficient either (two multiplications and one addition instead of just setting the sign). I think I will go with n%2 ? -a : a for now, but introducing a conditional seems a bit dubious as well.


Solution

  • Making certain assumptions about your programming language, compiler, and CPU...

    To repeat the conventional -- and correct -- wisdom, do not even think about optimizing this sort of thing unless your profiling tool says it is a bottleneck. If so, n % 2 ? -a : a will likely generate very efficient code; namely one AND, one test against zero, one negation, and one conditional move, with the AND+test and negation independent so they can potentially execute simultaneously.

    Another option looks something like this:

    zero_or_minus_one = (n << 31) >> 31;
    return (a ^ zero_or_minus_one) - zero_or_minus_one;
    

    This assumes 32-bit integers, arithmetic right shift, defined behavior on integer overflow, twos-complement representation, etc. It will likely compile into four instructions as well (left shift, right shift, XOR, and subtract), with a dependency between each... But it can be better for certain instruction sets; e.g., if you are vectorizing code using SSE instructions.

    Incidentally, your question will get a lot more views -- and probably more useful answers -- if you tag it with a specific language.