micro optimization: x&1 vs. x%2

Question

In terms of speed, which is fastest and why ?

x&1 //checks last bit

or

x%2 // performs modulo operation

Probably neither. Or both. Depends on how optimistic you're feeling. — chris, Jun 04 '14 at 19:48
Depends on the CPU architecture, as well as the compiler at hand. For example, if you're using a fixed-point processor, then every division or modulo operation is substituted with a function-call (a function which is usually provided along with the SW package for the given processor). That would essentially yield a much worse performance than one might expect from an arithmetic operation such as `%`. But in many cases, a good compiler would know how to opt-out operations such as `%2` (i.e., substitute it for `&1`). — barak manos, Jun 04 '14 at 19:52
@BlackBear Nonsense. If it's optimized, both will be reduced to a canonical form (presumably the variant that the compiler writer knows to be fastest). If it's not optimized, there is not a single ALU which can't do binary-and at the best possible throughput and latency -- it's such an utterly trivial operation, you can't do anything *faster* even if you could magically make the modulo operation free. All assuming the two forms are equivalent (I'm not sure what C mandates for negative `x`). — , Jun 04 '14 at 19:52
What is `x`? Without knowing exactly what `x` is the question makes little sense. — AnT stands with Russia, Jun 04 '14 at 19:54
@delnan if you have an ALU which can do AND operations but is unable to do modulo operations then AND is obviously faster. — BlackBear, Jun 05 '14 at 14:26
@BlackBear Yeah, that's part of my point. Which one is faster is *not* dependent on the processor because AND is *always* faster (or equal). — , Jun 05 '14 at 14:28

score 2 · Answer 1 · answered Jun 04 '14 at 19:49

Under the as-if rule, if the two results have the same effect, a compiler is free to substitute one with another.

Only insofar as they give different results can one be said to be more optimal than the other.

In this case, negative numbers (may?) return a negative result under x%2, and x&1 may be undefined for many integer values (or at least implementation defined).

However if they are well defined (based on 2s complement representation of signed integers say), and you then evaluate an if condition on them, then they once again become equivalent, in which case the compiler is free to replace one with the other, and neither is faster than the other.

micro optimization: x&1 vs. x%2

1 Answers1