Seems like a poorly chosen example, since you could simply "lookup" the last bit of the integer to see if it is even or odd, which should be instant for any integer?