C# .Net: Fastest Way to check if a Number is Odd Or Even

C# .Net: Fastest Way to check if a Number is Odd Or Even

This will benchmark many techniques to determine in C# .Net: Fastest way to check if a number is odd or even.

There’s an amazing number of applications that do some sort of check if a number is odd or even. One of the most popular uses is to display results in alternating colors depending on whether it’s an odd or even row.

 

Probably the most popular way to do this is to use the modulus operator and code like the following:

If (rowNum % 2 == 0)
    Print even row color info
Else
    Print odd row color info

But it’s a well known fact modulus is one of the slowest mathematical operators. Another common technique is to use the bitwise ampersand & operator because bitwise operations, generally speaking, are faaaaaaaaaaaast.

So that’s when this curious consultant started wondering in C# .Net: what is the fastest way to check if a number is odd or even? Is it the bitwise operand? Modulus? Using C#’s built in library function System.Math.DivRem (how many C# programmers even know about this?)? Or perhaps another, less common place, way?

 

The Set Up:

I wrote a C# Console application to test numerous techniques.

The code is written in Visual Studio 2013 targeting .Net Framework version 4.5 x64. The source code is available at the end of this blog so you can benchmark it on your own system if you wish.

In a nutshell, here are the methods:

#

Technique

Code Snippet

T1

Modulus %

for (int x = 0; x < NumberOfNumbers; x++)
{
        if (x % 2 == 0)
               total += 1; //even number
        else
               total -= 1; //odd number
}

T2

Bitwise Ampersand &

for (int x = 0; x < NumberOfNumbers; x++)
{
        if ((x & 1) == 0)
               total += 1; //even number
        else
               total -= 1; //odd number
}

T3

System.Math.DivRem

for (int x = 0; x < NumberOfNumbers; x++)
{
        System.Math.DivRem((long)x, (long)2, out outvalue);
        if ( outvalue == 0)
               total += 1; //even number
        else
               total -= 1; //odd number
}

T4

((x/2) * 2) == x

for (int x = 0; x < NumberOfNumbers; x++)
{
        if (((x / 2) * 2) == x)
               total += 1; //even number
        else
               total -= 1; //odd number
}

T5

((x >> 1) << 1) == x

for (int x = 0; x < NumberOfNumbers; x++)
{
        if (((x >> 1) << 1) == x)
               total += 1; //even number
        else
               total -= 1; //odd number
}

T6

While loop countdown

for (int x = 0; x < NumberOfNumbers; x++)
{
        index = NumberOfNumbers;
        while (index > 1)
               index -= 2;
        if (index == 0)
               total += 1; //even number
        else
               total -= 1; //odd number
}

T7

Last digit check

for (int x = 0; x < NumberOfNumbers; x++)
{
        tempstr = x.ToString();
        index = tempstr.Length - 1;
        //this assumes base 10
        if (tempstr[index] == '0' || tempstr[index] == '2' || tempstr[index] == '4' || tempstr[index] == '6' || tempstr[index] == '8')
               total += 1; //even number
        else
               total -= 1; //odd number
}

 

The code assumes all numbers are positive integers.

The exe file was installed and run on an Alienware M17X R3 running Windows 7 64-bit with 16 GB memory on an i7-2820QM processor.

The test was run for each technique over the following number of numbers:

  • 2,147,483,647
  • 214,748,364
  • 2,147,482
  • 21,474

Below 21,474, the difference in results were negligible. Well, at least on my machine. :-)

 

Ready! Set! Go!

Before starting, my hypothesis was that I expected the bitwise ampersand & technique to be the fastest.

Let’s see what happened on my machine over multiple runs.

All times are indicated in minutes:seconds.milliseconds format. Lower numbers indicate faster performance.

Winner marked in green; second place marked in yellow.

BENCHMARK RUN #1

@ 2,147,483,647

@ 214,748,364

@ 2,147,482

@ 21,474

T1: Modulus %

00:04.3742502

00.4230242

00:00.0040002

00.00

T2: Bitwise Ampersand &

00:04.8952800

00.4930282

00:00.0050003

00.00

T3: System.Math.DivRem

00:41.7713892

04.1292362

00:00.0400023

00.00

T4: ((x/2) * 2) == x

00:04.8892797

00.4880279

00:00.0040002

00.00

T5: ((x >> 1) << 1 == x

00:04.8272761

00.4780273

00:00.0050003

00.00

T6: While loop countdown

- too long -

- too long -

11:36.4118325

00.0690040

T7: Last digit check

03:43.5797880

21.3872233

00:00.1960112

00.0020001

 

BENCHMARK RUN #2

@ 2,147,483,647

@ 214,748,364

@ 2,147,482

@ 21,474

T1: Modulus %

00:04.4822564

00.4570261

00:00.0040002

00.00

T2: Bitwise Ampersand &

00:04.6942685

00.4920282

00:00.0050003

00.00

T3: System.Math.DivRem

00:41.8413932

04.2132410

00:00.0420024

00.0010000

T4: ((x/2) * 2) == x

00:05.1572950

00.4590262

00:00.0050003

00.00

T5: ((x >> 1) << 1 == x

00:04.8022747

00.4940283

00:00.0050003

00.00

T6: While loop countdown

- too long -

- too long -

11:41.7941403

00.0710041

T7: Last digit check

03:48.7550840

21.8652506

00:00.1980114

00.0020001

 

BENCHMARK RUN #3

@ 2,147,483,647

@ 214,748,364

@ 2,147,482

@ 21,474

T1: Modulus %

00:04.4072521

00.4270245

00:00.0050003

00.00

T2: Bitwise Ampersand &

00:04.9182813

00.4580262

00:00.0040002

00.00

T3: System.Math.DivRem

00:42.1004080

04.1962400

00:00.0420024

00.0010001

T4: ((x/2) * 2) == x

00:05.1442942

00.5140294

00:00.0050003

00.00

T5: ((x >> 1) << 1 == x

00:04.8032748

00.4980285

00:00.0050003

00.00

T6: While loop countdown

- too long -

- too long -

11:36.9518633

00.0700040

T7: Last digit check

03:46.1859370

21.7162421

00:00.1990114

00.0020001

 

Who would have expected?

The modulus operator, much to my surprise, performed the fastest. There was only one instance where it came second, and not by much. I was fully expecting the bitwise operation to surpass it, and am not really curious as to why the bitwise and operator is slower.

For second place, there appears to be no dominating technique. T4 using the ((x/2) * 2) == x technique performed just as well as T2 and T5 with their bitwise operations all the way up to 2 billion runs.

 

Should these results change your coding methods?

On my system, unless someone spots a flaw in my test code, and unless you have to check more than 2,147,482 numbers in one go, it really makes no significant performance difference which method is used for anywhere up to a few thousand conversions. Personally I’ll keep using the modulus operator because let’s face it: it’s easy to read, maintain, and understand what the coder is trying to do. It also performed the fastest on my machine.

Should you need to do a few hundred million checks, definitely keep using the modulus operator. After seeing my results, I don’t know why someone would use anything else unless you want to put in the code used for T5 with all its bit shifting to make it look like you’re doing some heavy-duty coding.

Obviously results may vary, and you should test on your system before micro-optimizing this functionality in your C# .Net application.

Hence why I’m giving you the code below. :-)

 

The Code:

 
using System;

namespace TestApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime end;
            DateTime start = DateTime.Now;

            Console.WriteLine("### Overall Start Time: " + start.ToLongTimeString());
            Console.WriteLine();

            TestFastestWayToDetermineOddOrEvenNumbers((int.MaxValue));  
            TestFastestWayToDetermineOddOrEvenNumbers((int.MaxValue / 10)); 
            TestFastestWayToDetermineOddOrEvenNumbers((int.MaxValue / 1000) - 1);   
            TestFastestWayToDetermineOddOrEvenNumbers((int.MaxValue / 100000)); 
            end = DateTime.Now;

            Console.WriteLine();
            Console.WriteLine("### Overall End Time: " + end.ToLongTimeString());
            Console.WriteLine("### Overall Run Time: " + (end - start));

            Console.WriteLine();
            Console.WriteLine("Hit Enter to Exit");
            Console.ReadLine();

        }

        //what is the fastest way to determine if a number is odd or even?
        static void TestFastestWayToDetermineOddOrEvenNumbers(int NumberOfNumbers)
        {
            Console.WriteLine("######## " + System.Reflection.MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("Number of numbers: " + NumberOfNumbers.ToString("#,##0"));
            Console.WriteLine();

            TimeSpan ts; 
            long total = 0;
            long outvalue = 0;
            int index = 0;
            string tempstr;
            DateTime end = DateTime.Now;
            DateTime start = DateTime.Now;

            total = 0;
            Console.WriteLine("Starting T1: Modulus % ");
            start = DateTime.Now;
            for (int x = 0; x < NumberOfNumbers; x++)
            {
                if (x % 2 == 0)
                    total += 2; //even number
                else
                    total -= 1; //odd number
            }
            end = DateTime.Now;
            ts = end - start;
            Console.WriteLine("Finished at: " + end.ToLongTimeString());
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
            Console.WriteLine();
            Console.WriteLine("###########################################################");
            Console.WriteLine();

            total = 0;
            Console.WriteLine("Starting T2: Bitwise & ");
            start = DateTime.Now;
            for (int x = 0; x < NumberOfNumbers; x++)
            {
                if ((x & 1) == 0)
                    total += 2; //even number
                else
                    total -= 1; //odd number
            }
            end = DateTime.Now;
            ts = end - start;
            Console.WriteLine("Finished at: " + end.ToLongTimeString());
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
            Console.WriteLine();
            Console.WriteLine("###########################################################");
            Console.WriteLine();

            total = 0;
            Console.WriteLine("Starting T3: System.Math.DivRem ");
            start = DateTime.Now;
            for (int x = 0; x < NumberOfNumbers; x++)
            {
                System.Math.DivRem((long)x, (long)2, out outvalue);
                if ( outvalue == 0)
                    total += 2; //even number
                else
                    total -= 1; //odd number
            }
            end = DateTime.Now;
            ts = end - start;
            Console.WriteLine("Finished at: " + end.ToLongTimeString());
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
            Console.WriteLine();
            Console.WriteLine("###########################################################");
            Console.WriteLine();

            total = 0;
            Console.WriteLine("Starting T4: ((x/2) * 2) == x ");
            start = DateTime.Now;
            for (int x = 0; x < NumberOfNumbers; x++)
            {
                if (((x / 2) * 2) == x)
                    total += 2; //even number
                else
                    total -= 1; //odd number
            }
            end = DateTime.Now;
            ts = end - start;
            Console.WriteLine("Finished at: " + end.ToLongTimeString());
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
            Console.WriteLine();
            Console.WriteLine("###########################################################");
            Console.WriteLine();

            total = 0;
            Console.WriteLine("Starting T5: ((x >> 1) << 1) == x ");
            start = DateTime.Now;
            for (int x = 0; x < NumberOfNumbers; x++)
            {
                if (((x >> 1) << 1) == x)
                    total += 2; //even number
                else
                    total -= 1; //odd number
            }
            end = DateTime.Now;
            ts = end - start;
            Console.WriteLine("Finished at: " + end.ToLongTimeString());
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
            Console.WriteLine();
            Console.WriteLine("###########################################################");
            Console.WriteLine();

            if (NumberOfNumbers <= (Int32.MaxValue / 1000))
            {   //takes way tooooooo looooooong if NumberOfNumbers is greater than (Int32.MaxValue / 1000)
                total = 0;
                Console.WriteLine("Starting T6: while-loop ");
                start = DateTime.Now;
                for (int x = 0; x < NumberOfNumbers; x++)
                {
                    index = NumberOfNumbers;
                    while (index > 1)
                        index -= 2;
                    if (index == 0)
                        total += 2;    //even number
                    else
                        total -= 1;    //odd number
                }
                end = DateTime.Now;
                ts = end - start;
                Console.WriteLine("Finished at: " + end.ToLongTimeString());
                Console.WriteLine("Time: " + (end - start));
                Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
                Console.WriteLine();
                Console.WriteLine("###########################################################");
                Console.WriteLine();
            }
            total = 0;
            Console.WriteLine("Starting T7: last digit check ");
            start = DateTime.Now;
            for (int x = 0; x < NumberOfNumbers; x++)
            {
                tempstr = x.ToString();
                index = tempstr.Length - 1;
                //this assumes base 10
                if (tempstr[index] == '0' || tempstr[index] == '2' || tempstr[index] == '4' || tempstr[index] == '6' || tempstr[index] == '8')
                    total += 2; //even number
                else
                    total -= 1; //odd number
            }
            end = DateTime.Now;
            ts = end - start;
            Console.WriteLine("Finished at: " + end.ToLongTimeString());
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine("Total: " + total.ToString("#,##0") + Environment.NewLine);
            Console.WriteLine();
            Console.WriteLine("###########################################################");
            Console.WriteLine();

        }
    }

}
  • Frederick Phathands

    The reason the modulo version is faster is because it’s not actually doing modulo. This is one of the most common compiler transformations around (because most people test for even/odd this way) and it actually heavily optimized (usually to the bitwise and, ironically enough).

  • http://www.jt-soft.com/ Paulo Santos

    Your time taken was very usefull for knowing wich method is the fastest. But i do parallel processing with threads since 2006 in all my applications. So i do not care about wich is the fastest method/operator. For the guys that need to do complex calculations your test code is very usefull. This way they can test performance. One fact in parallel processing is, if one single iteration can be done even a milisecond faster, the global number of threads can do a lot more per run time.

    • FireMystdl

      Thanks for your feedback Paulo. Generally speaking, you are right about parallel processing. However, there are scenarios where parallel processing is *slower* than non-parallel processing. Here’s just one example: iterating over an array of 100, or even 1,000 elements and doing some simple calculations as opposed to 1,000,000. Because of the time necessary to allocate/deallocate the resources to manage all the threads, plus allocating/de-allocating the threads themselves, the single-threaded model is more efficient.

  • jervicecj

    good

  • http://www.ninjacode.com.br/Blog/ Thiago

    Very Interesting.

    I have a sample using C# here -> http://www.ninjacode.com.br/Blog/2013/07/17/c-determine-number-odd/