Identify odd, even numbers - binary vs. mod

Question

Recently I had to identify whether a number is odd or even for a large number of integers. I thought of an idea to identify a number as odd or even by AND-ing it against 1 and comparing the result to 1

x & 1 == 1 // even or odd 

I have never seen this implementation in practice. The most common way you always see is :

x % 2 == 0

I decided to do some performance check on both methods and the binary method seems slightly faster on my machine.

int size = 60000000;
List<int> numberList = new List<int>();
Random rnd = new Random();

for (int index = 0; index < size; index++)
{
    numberList.Add(rnd.Next(size));
}

DateTime start;
bool even;

// regular mod
start = DateTime.Now;
for (int index = 0; index < size; index++)
{
    even = (numberList[index] % 2 == 0);
}
Console.WriteLine("Regualr mod : {0}", DateTime.Now.Subtract(start).Ticks);

// binary 
start = DateTime.Now;
for (int index = 0; index < size; index++)
{
    even = ((numberList[index] & 1) != 1);
}
Console.WriteLine("Binary operation: {0}", DateTime.Now.Subtract(start).Ticks);

Console.ReadKey();

Has anyone seen the binary method implemented ? Any drawbacks ?

Answer 1

Wouldn't the binary method be faster because the compiler is able to optimize this into a bitshift rather than actually forcing the cpu to perform the division calculation?

Answer 2

For such operations you should prefer the more readable approach (in my opinion the modulo-way) over the one that is thought to be faster.

Moreover, the modulo operation above can be optimized by the compiler into the bitwise-and operation. Therefore, you actually don't need to care.

Note to your example: To get more-precise results consider passing the number of items to be added into the list's constructor. This way you avoid discrepancies introduced by multiple reallocation of the backing array. For 60 million integer items (approc. 240 MB of memory) not preallocating the memory can represent a significant bias.

Answer 3

I agree with the other answers, that you should use the modulo check, because it best conveys intent.

However, for your specific results; try using the even variable. It will make a significant difference, because the compiler might actually optimize away some of the calculations because it knows it won't need to use the value.

Using your program (modified to use Stopwatch), I get 70 ms for regular mod and 88 ms for the binary operation. If I use the even variable, the difference is much smaller (327 vs 316 ms), and the modulos is fastest.

Answer 4

Bitwise and will beat modulo division every day of the week. Division by an arbitrary number takes a lot of clock cycles, whereas bitwise and is an essential primitive op that almost always completes in 1 clock cycle, regardless of your CPU architecture.

What you may be seeing, though, is that the compiler may be replacing x mod 2 with a bit shift or bit mask instruction which will have identical performance to your own bit mask operation.

To confirm that the compiler is playing tricks with your code, compare the performance of x mod 2 with x mod 7 or any other non-base 2 integer. Or obscure the operands from the compiler so that it cannot perform the optimization:

var y = 2;
result = x mod y;

If you see a dramatic difference in execution time with these changes, then that's a pretty strong indicator that the compiler is treating x mod 2 as a special case and not using actual division to find the remainder.

And if you're going to use DateTime to benchmark single-instruction operations, make sure you have a long enough loop that the test runs at least 5 minutes or so to get your true measurement above the noise floor.

Answer 5

For unsigned numbers, many compilers will optimize the 'mod' operator as an 'and' test. For signed numbers, (x % 2) will be 1 if the number is odd and positive; -1 if it's odd and negative; even though both +1 and -1 are non-zero, they may not get recognized as equivalent.

BTW, when using the "and" operator, I would test for !=0 rather than ==1. Compilers may recognize the equivalence, but they may not.

Answer 6

Well, yes, it is a slight optimization. This code snippet:

        uint ix = 3; // uint.Parse(Console.ReadLine());
        bool even = ix % 2 == 0;

generates this machine code in the release build:

            uint ix = 3;
0000003c  mov         dword ptr [ebp-40h],3 
            bool even = ix % 2 == 0;
00000043  mov         eax,dword ptr [ebp-40h] 
00000046  and         eax,1 
00000049  test        eax,eax 
0000004b  sete        al   
0000004e  movzx       eax,al 
00000051  mov         dword ptr [ebp-44h],eax 

Do note that the JIT compiler is smart enough to use the AND processor instruction. It is not doing a division as the % operator would normally perform. Kudos there.

But your custom test generates this code:

        uint ix = uint.Parse(Console.ReadLine());
// Bunch of machine code
        bool even = (ix & 1) == 0;
00000024  test        eax,1 
00000029  sete        al   
0000002c  movzx       eax,al 
0000002f  mov         esi,eax 

I had to alter the assignment statement because the JIT compiler got suddenly smart and evaluated the expression at compile time. The code is very similar but the AND instruction got replaced by a TEST instruction. Saving one instruction in the process. Fairly ironic how it this time chose to not use an AND :)

These are the traps of making assumptions. Your original instinct was right however, it ought to save about half a nanosecond. Very hard to see that back unless this code lives in a very tight loop. It gets drastically different when you change the variable from uint to int, the JIT compiler then generates code that tries to be smart about the sign bit. Unnecessarily.