Is Even or Is Not Even

However, when I look closely to the code, I realized something wasn’t right. I can’t find the original post, so this is what I remember. The function is short so I believe I won’t mess anything up.

function isEven(n: number) {
    return (n ^ 1) === (n + 1);
}

In Javascripts, a number can be an integer, decimal, or NaN, or Inf or event BigInt. But let’s assume we only use this for integer.

This piece of code is wrong. If we plug a very “small” negative number in, for example, -9007199249885170 which is greater than Number.MIN_SAFE_INTEGER = -(2^53-1) is a safe integer. We get

const n = -2
isEven(n)
//true

const a = -9007199249885170
isEven(a)
// false

a^1
// 4855823 - WHAT????

We thought we only flipped the last bit (or index 0 bit) of a but somehow everything is messed up. This is so interesting but I think it deserves an other post when I dive deep into Javascripts 54 bits two’s complement integer. But for now, let’s stick with the original problem.

So, normally, we would do n & 1 === 0 to check even number instead.

We can write a simple test to prove our assumption

function realEven(n: number) {
    return (n % 2) === 0;
}
function checkEvenFunction(isEvenFn: (n: number) => boolean) {
    for (let i = Number.MIN_SAFE_INTEGER; i <= Number.MAX_SAFE_INTEGER; i ++) {
        assert.equal(isEvenFn(i), realEven(i), i);
    }
}

function isEvenXor(n: number) {
    return (n ^ 1) === (n + 1);
}

function isEvenAnd(n: number) {
    return (n & 1) === 0;
}

And then call

checkEvenFunction(isEvenXor);

And

checkEvenFunction(isEvenAnd);

😪 I hope you didn’t try this.

Anyway, we have learned how not to check an integer is even in Javascripts. And we’ve done.

Scrolling through comments of the LinkedIn post, there’s a guy who claimed to be a compiler designer. And he said using % or & don’t matter, because compilers are smart enough to optimize it. 🤔 an other “wait a minute” moment.

So he’s saying that I have been writing & the whole time without improving any nanosecond of my Leetcode solutions? IT CAN’T BE!!! But he’s a compiler designer, he ain’t be wrong… Ok, I have to do fact check myself. Can’t let this slip through.

#include <stdio.h>

int main() {
    int a;
    scanf("%d", &a);

    if (a % 2) {
        printf("a is odd\n");
    }
    return 0;
}

This is straight forward check, we need to read a from stdin otherwise compiler would evaluate a % 2 at compile time and eliminate redundant code.

gcc main.c -o main
objdump --disassemble-symbol=main

Let’s checkout the actual assembly code. You can view full assembly code here Online Compiler

// gcc -g -o output.s -masm=intel -fno-verbose-asm -S -fdiagnostics-color=always example.cpp
// ....
        mov     eax, DWORD PTR [rbp-4]
        and     eax, 1
        test    eax, eax
        je      .L2
        mov     edi, OFFSET FLAT:.LC1
        call    puts
.L2:
        mov     eax, 0
        leave
        ret

Without any optimization flag, gcc changes a % 2 to a & 1 .

// clang -O0 ...
// ...
        mov     eax, dword ptr [rbp - 8]
        mov     ecx, 2
        cdq
        idiv    ecx
        cmp     edx, 0
        je      .LBB0_2
        lea     rdi, [rip + .L.str.1]
        mov     al, 0
        call    printf@PLT

No optimization flag -O0 For clang, it still use idiv and get modulo from edx registry. Therefore, without optimization flag, clang keep our code as it is.

// clang -O3
// ...
        test    byte ptr [rsp + 4], 1
        je      .LBB0_2
        lea     rdi, [rip + .Lstr]
        call    puts@PLT

Aggressive optimization flag -O3 Trying optimization flag from -O1 to -O3 give the same result. We see clang use test instruction to compare bits of a with number 1. It is equivalent of a & 1. So we can conclude that clang also optimize modulo check if we ask for optimization.

Note that this only work with if (n % 2) check, not assignment expression like int x = n % 2. Because the result would be assigned to x and negative numbers have negative modulo. Therefore, compiler can’t replace it with & 1 always produce either 0 or 1.

And according to this article from Leetcode, they compile C/C++ with -O2 flag. So my n & 1 manual optimization is wasted 🤣

Now I wonder how V8 optimize this kind of logic with integer number 🤔 . I don’t have d8 built on my computer now, so this has to be delayed a bit.