If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{
\begin{array}{ll}
0 & x=0\\\\
x+1 & x > 0 \mbox{ and odd}\\\\
-(x-1) & x > 0 \mbox{ and even}\\\\
x-1 & x < 0 \mbox{ and odd}\\\\
-x-1 & x < 0 \mbox{ and even}\\\\
\end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

2more comments