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

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

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.

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.

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

bool is_odd = number & 1;

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

Check to see if the last bit is 1.

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

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.

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

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.

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.

Check the least significant bit:

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

Can't you just look at the last digit and check if its even or odd if the input is in base 10?

{1, 3, 5, 7, 9} is odd

{0, 2, 4, 6, 8} is even

Additional info: The OP states that a number is a given, so I went with that when constructing this answer. This also requires the number to be in base 10. This answer is mathematically correct by definition of even/odd in base 10. Depending on the use case, you have a mathematically consistent result just by checking the last digit.

Note: If your input is already an int, just check the low bit of that. This answer is only useful for numbers represented as a sequence of digits. You could convert int->string to do this, but that would be much slower than n % 2 == 0.

Checking the last digit does work for a string of digits in any even base, not just 10. For bases lower than 10, like base 8 (octal), 9 and 8 aren't possible digits, but the low digit being odd or even still determines whether the whole number is.

For bases higher than 10, there will be extra possibilities, but you don't want to search a list anyway, just check if the digit as an integer is odd or even using the normal i % 2 == 0 or !=0 check.

For ASCII hex using 'a' .. 'f' to represent digits values 10 through 15, the low bit of ASCII code does not represent odd or even, because 'a' == 0x61 (odd) but represents 10 aka 0xa (even). So you'd have to convert the hex digit to an integer, or do some bit-hack on the ASCII code to flip the low bit according to some other bit or condition.