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?

Aldin

That's a good beginner's C question. +1 from me. – Fandango

Isn't bitwise-XOR more faster than bitwise-AND? Is it not possible with XOR operation? – Aldin

@aks: If you are using a full function compiler, that back end almost certainly knows those tricks better than you do. Write for clarity and legibility and leave the bit fiddle, cycle optimization to the pro. Really. And if you're not happy with the results, profile, then examine the hot spots in detail. – Lancinate

@dmckee: Anyway I'd like to see a solution using only a single XOR statement. I don't think that's possible... – Tybalt

Make sure you've read this before microoptimization: linux-kongress.org/2009/slides/… – Threw

No it's not possible to model AND using only XOR. You can't mask out bits with XOR - you can only pass them through unchanged or toggle them. – Roice

Duplicate of How do I check if an integer is even or odd? – Ileneileo

Answer 1

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.

Convenience

even better, specify the argument as unsigned. – Feinberg

@Potatoswatter: x%2U or x&1U. :-) – Rangel

what if you input 1, it says odd – Homovec

x & 1 will give wrong answers on one's complement systems. For fully-portable code that can compile efficiently on the normal 2's complement systems we care about, you need to use either unsigned or x % 2 != 0 – Libbey

Answer 2

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.

Tybalt

The compiler has likely removed the test completely as the are both probably constant. Recall that gcc without options is equivalent to gcc -O2 which is a non-trivial level of speed optimization. Check the generated assembly to be sure.. – Lancinate

Isn't bitwise-XOR more faster than bitwise-AND? Is it not possible with XOR operation? – Aldin

@dmckee: I don't know why you think level 2 was the default. The man page clearly says "-O0 Do not optimize. This is the default.". But I checked the assembly code anyway and it was not removed from the code (that's why it takes 7 seconds for each test to run). – Tybalt

@aks: I tested bitwise XOR and it's at the very same speed as AND/modulo (BTW these two produce the same code on x86, namely an "and" instruction). Anyway could you tell me how to determine odd/even with only an XOR statement? – Tybalt

InRe optimization levels: Mea Cupla. – Lancinate

@aks: Bitwise XOR is only usable if the number is either 0 or 1; it doesn't discard the high bits. It's also not faster (on x86); and reg, 1 or test reg,1 can macro-fuse with a JCC instruction, XOR can't. (x86_64 - Assembly - loop conditions and out of order). The thing you need to avoid is number % 2 == 1 for odd instead of != 0, which takes extra instructions to make sure it's false for numbers like -3. – Libbey

Answer 3

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

Spicule

This fails on a machine using one's complement. – Notify

Also, and this is a general comment to all the answers to date, the question did not specify the number was an integer. You can't do bitwise operations on floats (at least, not without some type-casting hackery). – Introspect

@Skizz: Define even or oddness for a non-integer. – Lancinate

@dmckee: float i=2.0f; // an even number! but i & 1 doesn't work. – Introspect

@Introspect you can define it for 2.0 because it has an integer expression. So, the right thing to do is convert to int and handle the result as discussed. – Lancinate

Answer 4

bool is_odd = number & 1;

Blindage

thats fast, but wont compile unless there's a typedef somewhere – Mohsen

This fails on a machine using one's complement. – Notify

@Jason: You're right of course, this implementation implies two's complement logic. I'm not aware of any contemporary one's complement hardware, however. If you know of any, please comment. – Blindage

As shown in other answers "% 2" is the "right" answer since it will compile to "& 1" on most hardware anyway, and it shows the correct intention of the code. "& 1" is from the days before more intelligent compiler optimizations. – Isotherm

@Jason, you can create a function to check if the machine is ones or twos compliment. But im too lazy to thing now – Nate

@Jason: it succeeds on a machine using ones complement if you change the 1 to 1U. – Rangel

In C11, #include <stdbool.h> will define bool as _Bool. – Libbey

Answer 5

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

Isogloss

Checking the least significant bit would be faster than the modulus operator. However, I bet most compilers would turn "mod 2" into "and 1" – Gennygeno

@bramp: they can't if i is signed. – Rangel

@R: are you sure? For example, the twos complement of 127 is "01111111", and -127 is "10000001", both have the least significant bit set. – Gennygeno

Answer 6

Check to see if the last bit is 1.

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

Stableboy

See the comment of Tom, same applies here. This won't compile in C. – Tybalt

Right... changed to int. (FWIW, some build environments #define or typedef bool to int). – Stableboy

Answer 7

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.

Disini

I would perform a prime factorization on n, then check whether it has any factors if 2. :p – Convenience

what about: int is_odd(int n) { return cos(M_PI * n) < 0.0; } – Grampositive

A good compiler should output the same assembler as with {return n & 1;} :) – Rositaroskes

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.

Notify

@unwind: I'm pretty sure there is, and has been for more than 10 years (since C99) – Rositaroskes

Answer 9

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

Howes

Zero is an even number. This also fails on a machine using one's complement. – Notify

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.

Sloe

== has higher precedence than &, therefore x & 0x01 == 0 will evaluate into x & (0x01 == 0) which is equivalent to x & 0 which means 0 so your if branch will never be executed. – Convenience

Plus you should check if the compiler really outputs different machine code for the two. My bet is that it should output the same, especially with optimizations turned on. – Rositaroskes

Compilers know this optimization; as long as you use x%2 != 0 or x%2 == 0 (rather than x%2 == 1 which is false for negative x), you'll get an AND or TEST or similar instruction that just checks the low bit. godbolt.org/z/djnfz5ben. Before changing your source to hand-hold the compiler, check the asm to see if it's really that dumb. If it isn't using a bitwise test, then enable optimization or use a better compiler in preference to mangling your source. (And if you do use a bitwise AND, write it correctly for operator precedence as @Convenience pointed out. – Libbey

Answer 11

Check the least significant bit:

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

Teneshatenesmus

Out of curiosity: Why 0x01 instead of simply 1? – G

It's habit. I'm used to always using hexadecimal representation when doing bitwise operations :) – Teneshatenesmus

With an even number, LSB is always 0 and with an odd number, LSB is always 1. – Ruthenian

Answer 12

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.

Memling

If you have an ASCII string of decimal digits you haven't yet converted to an int, yes, that's correct, you can just check the lowest binary bit of the last ASCII digit without taking time to convert to an integer. Like odd = str[n-1] & 1 for string str with length n. Or if you have a pointer to the end from looping until you found a non-digit, *ptr & 1 – Libbey

@PeterCordes yes, this is true! great addition to this thread. I just went off the OP which states the input is a number. – Memling

Right, and in C (like almost all computer languages), number normally means integer, like an int or unsigned long. In that case, it's in binary, not base 10. (In C, n <<=1 1 multiplies by 2, not 10, and the C standard guarantees that int is a binary integer type.) As the other answers show, that means you only need to check if the low bit is 1, because in base 2 the low digit can only be 0 or 1. – Libbey

Computing the low decimal digit of a number would require a modulo operation like n % 10U, which is significantly more expensive (still cheap, but nowhere near as cheap as a single AND on a 2's complement machine), and then you'd have to do more work to check for one of 5 possibilities. Or take % 2 of that, discarding the part of the remainder tied to 5, the other factor of 10, so you might as well have just taken % 10U in the first place. If that's what you were suggesting, this answer is not efficient. – Libbey

If you're talking about a human reading source code that contains a numeric literal written in decimal, note the tags: [micro-optimization] and [c], not [math] or definitions of terminology. – Libbey