What is the fastest way to find if a number is even or odd?

by

It is pretty well known that

static inline int is_odd_A(int x) { return x & 1; }

is more efficient than 

static inline int is_odd_B(int x) { return x % 2; }

But with the optimizer on, will is_odd_B be no different from is_odd_A? No — with gcc-4.2 -O2, we get, (in ARM assembly):

_is_odd_A:
    and r0, r0, #1
    bx  lr

_is_odd_B:
    mov r3, r0, lsr #31
    add r0, r0, r3
    and r0, r0, #1
    rsb r0, r3, r0
    bx  lr

We see that is_odd_B takes 3 more instructions than is_odd_A, the main reason is because

((-1) % 2) == -1
((-1) & 1) ==  1

However, all the following versions will generate the same code as is_odd_A:

#include <stdbool.h>
static inline bool is_odd_D(int x) { return x % 2; }      // note the bool
static inline int  is_odd_E(int x) { return x % 2 != 0; } // note the !=

What does this mean? The optimizer is usually sophisticated enough that, for these simple stuff, the clearest code is enough to guarantee best efficiency.

More Related Contents:

  1. Can x86’s MOV really be “free”? Why can’t I reproduce this at all?
  2. Why does mulss take only 3 cycles on Haswell, different from Agner’s instruction tables? (Unrolling FP loops with multiple accumulators)
  3. Is it possible to tell the branch predictor how likely it is to follow the branch?
  4. C -> sizeof string is always 8
  5. How to check if a pointer is freed already in C?
  6. Size of pid_t, uid_t, gid_t on Linux
  7. Why does the Win32-API have so many custom types?
  8. declaring variables without any data type in c
  9. memory allocation in Stack and Heap
  10. Why does static initialization of flexible array member work?
  11. what is the difference between difftime and ‘-‘?
  12. Casting void pointers
  13. Is it Undefined Behaviour to cast away the constness of a function parameter?
  14. Evaluate Mathematical Function from String [closed]
  15. Yoda Conditions and integer promotion
  16. How do you get the size of array that is passed into the function?
  17. gdb prints wrong values when modifying arguments
  18. How do I insert and delete some characters in the middle of a file?
  19. How to split a string into tokens in C?
  20. Why doesn’t pressing enter return ‘\n’ to getch()?
  21. In C how do I print filename of file that is redirected as input in shell
  22. Detecting mismatched array enum initializers
  23. Signed bit field represetation
  24. What is the effect of second argument in _builtin_prefetch()?
  25. Output single character in C
  26. Multiple assignment in one line
  27. How can I call a function using a function pointer?
  28. How many chars can be in a char array?
  29. How do I lock files using fopen()?
  30. How can floating point calculations be made deterministic?

Leave a Comment