A function such that $f(f(n)) = -n$? This question from somebody's job interview made me puzzled:
Design a function f, such that:
$f(f(n)) = -n$ ,
where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.
Do you have any idea how to tackle it?
EDIT: I removed "Real number" from the title, since it just confused readers, but it was meant just to stress that complex numbers are not allowed.

First you should identify that your sequences have the following pattern (using the arrow to indicate successive applications of f):
$$\begin{align}
0 \rightarrow f(0) \rightarrow 0 \\
1 \rightarrow f(1) \rightarrow -1 \rightarrow f(-1) \rightarrow 1 \\
2 \rightarrow f(2) \rightarrow -2 \rightarrow f(-2) \rightarrow 2 \\
3 \rightarrow f(3) \rightarrow -3 \rightarrow f(-3) \rightarrow 3 \\
4 \rightarrow f(4) \rightarrow -4 \rightarrow f(-4) \rightarrow 4 \\
\vdots \\
2^{31} \rightarrow f(2^{31}) \rightarrow -2^{31}=2^{31} \\
\end{align}$$
Ignore the special case of $0$ and $2^{31}$ for the moment.
Suppose we choose $f(x) = y$, knowing that $y \not \in \{0, 2^{31}, x, -x\}$.  Then we know $f(f(x)) = -x = f(y)$, and likewise $f(-x) = -y$, and $f(-y) =x$.  So this one choice uniquely determines the four values of $f(x), f(-x), f(y),$ and $f(-y)$:
$$\begin{align}
x \rightarrow y \rightarrow -x \rightarrow -y \rightarrow x \\
y \rightarrow -x \rightarrow -y \rightarrow x \rightarrow y \\
\end{align}$$
For the special cases, we can choose $f(0) = 0 {\huge {\land}} f(2^{31}) = 2^{31}$ or we can choose $f(0) = 2^{31} {\huge {\land}} f(2^{31}) = 0$.
For $w$ bits, the 2 special cases give us 2 choices, and any pairing of the remaining rows (cycles) give us the remaining characterization of $f$.  
...but how many remaining cycles are there?
Well their starting value ranges from $1$ to $2^{w  - 1} - 1$, or there is an odd total number of cycles.  Since there is an odd number of cycles, it is actually impossible to construct $f$ because you must leave one cycle out of the pairings.  So there will always be one pair $\{x, -x\}$ that will not satisfy the constraints on $f$.
