Hm, good thought. You could just do

    printf("%d is %s\n", n, last_binary_bit(n) == 0 ? "even" : "odd");

and the rest is trivial:

    int last_binary_bit(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 0;
        ...
    }

Come to think of it, with a little fancy math you could divide and conquer:

    int last_binary_bit(int n) {
        // Handle the easy cases.
        if (n == 0) return 0;
        if (n == 1) return 1;
        // Number may be large. Divide and conquer. It doesn't matter where we split it,
        // so use a randomized algorithm because those are fast.
        for (;;) {
            int r = random();
            if (r < n) {
                // Smaller numbers are easier.
                int smaller1 = r;
                int smaller2 = n - 4;
                int bit1 = last_binary_bit(smaller1);
                int bit2 = last_binary_bit(smaller2);
                // Fancy math: even + even is even, even + odd is odd, etc.
                if (bit1 == 0 && bit2 == 0) return 0;
                if (bit1 == 0 && bit2 == 1) return 1;
                if (bit1 == 1 && bit2 == 0) return 1;
                if (bit1 == 1 && bit2 == 1) return 0;
            }
        }
    }