The Ubuntu Incident

Problem

You want to test if a number is even.

Solution

Well, the well-known solution is to test the value of n modulo 2. If it’s zero, then the number is even, otherwise it’s odd. But how fast is it?

Here is a Pascal snippet:

procedure Main();
var
  i: Integer;
  total: Integer = 0;
begin
  for i := 0 to MaxInt-1 do
    begin
      if i mod 2 = 0 then
        total += 1;
    end;

  WriteLn(total);
end;

Compile and run:

$ fpc -O3 main.pas
$ time ./main
1073741824
./main  16,61s user 0,00s system 99% cpu 16,634 total

16 seconds! That’s a lot… Let’s try an alternative approach. Let’s do bitwise operations. You can use the bitwise AND operator and check the least significant bit of the integer. If the least significant bit is 0, the number is even; if it’s 1, the number is odd.

procedure Main();
var
  i: Integer;
  total: Integer = 0;
begin
  for i := 0 to MaxInt-1 do
    begin
      if (i and 1) = 0 then      // <- HERE
        total += 1;
    end;

  WriteLn(total);
end;

$ fpc -O3 main.pas
$ time ./main
1073741824
./main  1,19s user 0,00s system 99% cpu 1,189 total

Much better :) But what about C? Let’s try it:

int main()
{
    int total = 0;

    for (int i = 0; i < 2147483647; ++i)
    {
        if (i % 2 == 0)                     // version 1
        // if ((i & 1) == 0)                // version 2
        {
            ++total;
        }
    }

    printf("%d\n", total);

    return 0;
}

$ gcc -O3 main.c
$ time ./a.out
1073741824
./a.out  0,26s user 0,00s system 99% cpu 0,264 total

I tried both versions (modulo 2 and bitwise AND) and got the same result. I think the optimizer recognizes modulo 2 and converts it to bitwise AND.