Even or Odd

https://www.codewars.com/kata/53da3dbb4a5168369a0000fe/train/javascript

Instructions

Create a function that takes an integer as an argument and returns "Even" for even numbers or "Odd" for odd numbers.

Explanation

This is a simple problem that can be solved with a simple if statement. If the number is divisible by 2, then it is even, otherwise it is odd.

But I want to show you a more advanced solution using bitwise operators.

First, here is the most simple solution:

1
function evenOrOdd(number) {
2
  return number % 2 ? "Odd" : "Even";
3
}

And here is the bitwise solution:

1
function evenOrOdd(number) {
2
  return number & 1 ? "Odd" : "Even";
This is a bitwise AND operation. Let's supose that the number is 5. In binary, 5 is 101. When we do a bitwise AND with 1, we get 101 & 001 = 001. The last bit is 1, so the number is odd.
3
}

Benchmark

Run several times the benchmark and you will see that the bitwise solution is generally faster than the modulo solution.

Let's see x86-64 clang assembly code

I'm removing the constant overhead of returning a string and just focusing on the operation that determines if the number is even or odd.

So, let's create an isEven function in C for each solution and see the assembly code generated by the compiler.

The assembly code generated by the compiler for the bitwise AND solution is:

1
isEven:
2
    push rbp
3
    mov rbp, rsp
4
    mov dword ptr [rbp - 4], edi
5
    mov eax, dword ptr [rbp - 4]
6
    and eax, 1
Previous lines moves the integer that the `isEven` function receives to the necessary register. But THIS line is the bitwise AND operation and the only one that is necessary to determine if the number is even or odd.
7
    pop rbp
8
    ret

Now let's see the assembly code generated by the compiler for the modulo solution:

1
isEven:
2
    push    rbp
3
    mov     rbp, rsp
4
    mov     dword ptr [rbp - 4], edi
5
    mov     eax, dword ptr [rbp - 4]
At this point, the code is the same as the previous one.
6
    mov     ecx, 2
This line moves the number 2 to the register. Modulo operation is a division operation, so we need to divide the number by 2.
7
    cdq
Because we are working with 32-bit registers, we need to extend the sign of the number to the 64-bit register.
8
    idiv    ecx
This is the division operation. The result is stored in the `eax` register and the remainder is stored in the `edx` register.
9
    mov     eax, edx
This line moves the result of the division to the `edx` register (our integer parameter). The result is the remainder of the division (0 if the number is even).
10
    pop     rbp
11
    ret

As you can see, the modulo solution needs more instructions to determine if the number is even or odd. This is why the bitwise AND solution will be faster in every case.

You can try by yourself in https://godbolt.org.

Running the benchmark in C

Using hyperfine I tested the performance of both solutions in C. Here are the results:

1
hyperfine './modulo' './bit-op' --warmup 10 -N
2
Benchmark 1: ./modulo
3
  Time (mean ± σ):      24.8 ms ±   0.6 ms    [User: 24.0 ms, System: 0.5 ms]
4
  Range (min … max):    23.3 ms …  28.2 ms    117 runs
5

6
Benchmark 2: ./bit-op
7
  Time (mean ± σ):      22.9 ms ±   0.4 ms    [User: 22.2 ms, System: 0.4 ms]
8
  Range (min … max):    21.8 ms …  24.0 ms    131 runs
9

10
Summary
11
  ./bit-op ran
12
    1.09 ± 0.03 times faster than ./modulo