My Silly IsEven Function

Recently, this tweet by Kat Maddox aka @ctrlshifti has been making the rounds on Twitter. The replies quickly turned into a competition to write the most cursed IsEven function possible. I decided to join in on the fun and after some experimentation, I came up with the following function written in C.

int is_even(int n) {
    while (n >> 1) n *= n;
    return !n;
}

At first glance, this function looks like it wouldn't even terminate for most inputs, let alone return the correct result.

Explanation

Let's consider what happens when we square a number of the shape $2^{k+1} a + b$ with $a\in\mathbb{Z}$, $k\in\mathbb{N}$, and $b\in{0, 1}$. Note that every number $n\in\mathbb{Z}$ can be represented in this form, with $k=0$, $a=\lfloor n/2 \rfloor$, and $b=n \mod 2$.

$$ (2^{k+1} a + b)^2 = 2^{2(k+1)} a^2 + 2^{k+2} a b + b^2 = 2^{k+2}(2^{k} a^2 + a b) + b = 2^{k+2} a' + b $$

As we can see, we get a number of the same shape as the input, but $k$ increased by $1$. Most notably, the last bit of the number $b$ stays the same. If we repeat this operation, we can see that the first component of the number $a$ will continue to shift to the right, while $b$ remains unchanged.

This is also what happens to n in the while loop of our function, except the type int can only store integers with a finite number of bits. If the result of the multiplication is larger than the maximum value of int, the higher bits will "fall off" the left side of the integer. So after a couple of iterations, the first component is going to disappear entirely, leaving only the last bit behind.

When this happens, the loop condition n >> 1 will be false and the loop will terminate. Finally, we negate the result of the loop and return it.