Hello, I am Laszlo

Even or Odd

04/04/2020

5 minutes

Introduction

One of the typical interview questions is deciding about a number if it is even or odd. The task usually goes by given a integer (or array of integers), return a bool (or array of bools) indicating if the number is odd or even.

A typical solution to the problem is using integer remainder operator:

public bool IntegerRemainder(int i) => i % 2 != 0;

In the rest of this post, I will propose two other solutions and compare their performance to the first one.

Right-Shift Operator

Right-Shift Operator shifts its left hand operand's bit with value of the right hand operand. It discards the low-order bits.

In my case shifting the integer's bits to the right by one means discarding the lowest bit. It divides the number by two and throws away the remainder. After this we can multiply the number by two and compare it with the original. If the original and the calculated values are equal, we have an even number, otherwise an odd.

public bool RightShift(int i) => (i >> 1) * 2 != i;

This solution could work faster to the previous one, as it does not use modulo operation, which is slower, but rather a bit shift and a multiply.

Unsafe-As

The last solution is also using 'bit magic'. It uses the Logical And operator. Calculating a bitwise AND between the given number and one returns one or zero as a result. If the value is one we have an odd number, otherwise an even. Once with the value, we need to interpret is as a bool. Fortunately, C# has and Unsafe As method, which casts a given type to another. As its name suggests it is an unsafe, because it simply reinterprets the bits. The same operation with casting would not be possible. In our case a bool just has the same bit pattern as '1' when it is true, and '0' when it is false.

public bool UnsafeAs(int i){var k = i & 1;return Unsafe.As<int, bool>(ref k);}

This solution does not compare the result to 0 or the original value, it just reinterprets the bits as a bool.

Benchmarks

To the actual performance of the above solutions, I will use BenchmarkDotNet. I prepare two benchmarks:

1. with an array containing the same number at every index

2. an array with random values

Both tests ended up having the same results by the order of magnitude for Mean/Error/StdDev:

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363, Intel Core i5-1035G4 CPU 1.10GHz, 1 CPU, 8 logical and 4 physical cores, .NET Core SDK=3.1.101

DefaultJob : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT

Which means branch prediction does not have an affect on the above operations. To see why, let's dig into the JITTED code:

Explanation

To have a better understanding on these results, we actually need to take a look at the Jitted code. I use WinDBG, to get to the native code of IntegerRemainder method. I ran the following commands:

.loadby sos coreclr
!name2ee BitMagic Benchmarks.IntegerRemainder
!U [address]

Integer Remainder

00007ff8`72a61f1a 4c63c2          movsxd  r8,edx
00007ff8`72a61f1d 428b448010      mov     eax,dword ptr [rax+r8*4+10h]
00007ff8`72a61f22 448bc0          mov     r8d,eax
00007ff8`72a61f25 41c1e81f        shr     r8d,1Fh
00007ff8`72a61f29 4403c0          add     r8d,eax
00007ff8`72a61f2c 4183e0fe        and     r8d,0FFFFFFFEh
00007ff8`72a61f30 412bc0          sub     eax,r8d
00007ff8`72a61f33 0f94c0          sete    al
00007ff8`72a61f36 0fb6c0          movzx   eax,al

In this solution there are quite a log ongoing, one logical shifts, and ADD operation, and AND a substraction and then a test check is the value isn't 0.It is following a similar pattern ar the Right Shift solution, although it gets to the final result in a longer path, as it needs to calculate the actualy remainder.

Right Shift

0007ff8`72a61eba 4c63c2          movsxd  r8,edx
00007ff8`72a61ebd 428b448010      mov     eax,dword ptr [rax+r8*4+10h]
00007ff8`72a61ec2 448bc0          mov     r8d,eax
00007ff8`72a61ec5 41d1f8          sar     r8d,1
00007ff8`72a61ec8 41d1e0          shl     r8d,1
00007ff8`72a61ecb 443bc0          cmp     r8d,eax
00007ff8`72a61ece 0f94c0          sete    al
00007ff8`72a61ed1 0fb6c0          movzx   eax,al

This solution is a lot shorter compared to the remainder one, it has a shift right (sar) and a shift left (for the multiplication). Then it has a comparison to compare with the original value, and it returns the result.

al is the lower 8 bits of EAX register.

Unsafe As

00007ff8`72a61e5a 4c63c2          movsxd  r8,edx
00007ff8`72a61e5d 428b448010      mov     eax,dword ptr [rax+r8*4+10h]
00007ff8`72a61e62 83e001          and     eax,1
00007ff8`72a61e65 89442424        mov     dword ptr [rsp+24h],eax
00007ff8`72a61e69 0fb6442424      movzx   eax,byte ptr [rsp+24h]

This is the shortest solution and it executes faster to all above. Other then the mov operations it has an AND (ecx,1) and a movzx to move the result to the returned register.