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

Question

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

Answer 1

int i=5;
if ( i%2 == 0 )
{
   // Even
} else {
   // Odd
}

Answer 2

if (x & 1) is true then it's odd, otherwise it's even.

Answer 3

If it's an integer, probably by just checking the least significant bit. Zero would be counted as even though.

Answer 4

bool is_odd = number & 1;

Answer 5

Check to see if the last bit is 1.

int is_odd(int num) {
  return num & 1;
}

Answer 6

Check the least significant bit:

if (number & 0x01) {
  // It's odd
} else {
  // It's even
}

Answer 7

Usual way to do it:

int number = ...;
if(number % 2) { odd }
else { even }

Alternative:

int number = ...;
if(number & 1) { odd }
else { even }

Tested on GCC 3.3.1 and 4.3.2, both have about the same speed (without compiler optimization) as both result in the and instruction (compiled on x86) - I know that using the div instruction for modulo would be much slower, thus I didn't test it at all.

Answer 8

Your question is not completely specified. Regardless, the answer is dependent on your compiler and the architecture of your machine. For example, are you on a machine using one's complement or two's complement signed number representations?

I write my code to be correct first, clear second, concise third and fast last. Therefore, I would code this routine as follows:

/* returns 0 if odd, 1 if even */
/* can use bool in C99 */
int IsEven(int n) {
    return n % 2 == 0;
}

This method is correct, it more clearly expresses the intent than testing the LSB, it's concise and, believe it or not, it is blazing fast. If and only if profiling told me that this method were a bottleneck in my application would I consider deviating from it.

Answer 9

int is_odd(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return !is_odd(n - 1);
}

Oh wait, you said fastest way, not funniest. My bad ;)

Above function only works for positive numbers of course.

Answer 10

The portable way is to use the modulus operator %:

if (x % 2 == 0) // number is even

If you know that you're only ever going to run on two's complement architectures, you can use a bitwise and:

if (x & 0x01 == 0) // number is even

Using the modulus operator can result in slower code relative to the bitwise and; however, I'd stick with it unless all of the following are true:

1. You are failing to meet a hard performance requirement;
2. You are executing x % 2 a lot (say in a tight loop that's being executed thousands of times);
3. Profiling indicates that usage of the mod operator is the bottleneck;
4. Profiling also indicates that using the bitwise-and relieves the bottleneck and allows you to meet the performance requirement.

Answer 11

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.