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.

This answer to a related question supplies the relevant analysis.
Assuming that a "signed 32-bit integer" means that you are considering the domain and range of $f$ to be the integers in the interval $[-2^{31}, 2^{31})$, a simple counting argument shows that the largest domain on which the identity $f(f(x))=-x$ can hold must be missing at least three points.
(aside: $-2^{31}$ must be excluded, because it is outside of the domain of unary negation. The interesting part is that we must exclude two other points too)
The sample function from that answer can be used:
$$ f(x) = \begin{cases} 0 & x == 0
\\ x+1 & x>0 \wedge \text{$x$ is odd}
\\ 1-x & x>0 \wedge \text{$x$ is even}
\\ x-1 & x<0 \wedge \text{$x$ is odd}
\\ -1-x & x<0 \wedge \text{$x$ is even}
\end{cases} $$
which has the desired property on $[-2^{31} + 2, 2^{31} - 2]$.
I won't discuss implementing a solution with bit twiddling: such a topic is beyond the scope of this forum.

EDIT: if we instead want the domain of $f$ to be the entire interval, we can make the identity hold for one more point. If we take a function $f$ given as above, and let the three points that are excluded be $a$, $-a$, and $2^{-31}$, then we can extend $f$ by setting


*

*$f(a) = 2^{-31}$

*$f(2^{-31}) = -a$

*$f(-a) = $ anything


and thus with this extension, $f(f(a)) = -a$ as well.
