Is it possible to write a function int f(int x) in C that satisfies f(f(x)) == -x? Without globals and static variables, of course.

Heard from a fellow student at UC Berkeley in 1997.

f(0) must equal 0. If not, then f(0) must equal some non-zero b, so f(b) must equal 0, in which case, f(f(b)) ≠ -b. If f(0) = 0, it follows that f(a) ≠ 0 for any non-zero a. And for non-zero a, f(a) ≠ a.

For non-zero a, let f(a) = b, where b ≠ 0. It follows that f(b) = -a, f(-a) = -b and f(-b) = a. In other words, if f(f(x)) == -x for all x, then the set of non-zero integers gets divided into disjoint cycles of size 4, where each cycle is of the form {a, b, -a, -b}. There are two positive and two negative integers in any such cycle. Any function f that divides non-zero integers into such cycles suffices. There are many such functions if we allow all positive and negative integers in the domain. However, when the domain is k-bit numbers for any k, the total number of numbers that can be represented is even, and one of these numbers is always 0. So the number of positive and negative integers allowed by k-bit representations is never the same! Therefore, we can never divide the non-zero integers among the set of k-bit numbers into disjoint cycles of the form {a, b, -a, -b}. Therefore, no f exists such that f(f(x)) == -x in C for k-bit numbers, for any k.