A function in C such that F(F(x)) = -x?

Question

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.

Source : Gurmeet Puzzles

Answer 1

One solution is to define the function F as a quarter rotation of the argument in the Argand plane (in either direction in your particular case). To do this we need to model a complex number in a single int.

We are free to regard x as split into two halves. One half is the real part, the other half the imaginary part.

In the following analysis I am then free to adopt the notation x = y + iz (where i * i = -1), and y and z are both 1/2-sized ints.

Your function F models a multiplication by i, which is little more than an exchange of the two halves of the int.

F(F(x)) = F(F(y + iz)) = F(iy + iiz) = iiy + iiiz = -(y + iz) = -x.

The fact that F(x) gives you a seemingly unrelated value to x is of little consequence: the subsequent application of F will yield the sign reversal on the original number.

Answer 2

Funnily enough, for the typical N-bit two's complement signed integers, the answer is no, there is no such function that works for all representable integers.

The issue boils down to zero being a special number, and there not being an even number of representable positive, and negative, values.

Let me explain. The requirement for the mapping is

f(f(x)) = -x

which, due to symmetries, means that

f(f(f(f(x)))) = x

In other words, we have integer cycles of length 4. Consider the cycles for small integers:

-4:  f(-4) = F_-4,  f(F_-4) = 4,  f(4) = F₄,  f(F₄) = -4
-3:  f(-3) = F_-3,  f(F_-3) = 3,  f(3) = F₃,  f(F₃) = -3
-2:  f(-2) = F_-2,  f(F_-2) = 2,  f(2) = F₂,  f(F₂) = -2
-1:  f(-1) = F_-1,  f(F_-1) = 1,  f(1) = F₁,  f(F₁) = -1
0:  f(0) = 0
1:  f(1) = F₁,  f(F₁) = -1,  f(-1) = F_-1,  f(F_-1) = 1
2:  f(2) = F₂,  f(F₂) = -2,  f(-2) = F_-2,  f(F_-2) = 2
3:  f(3) = F₃,  f(F₃) = -3,  f(-3) = F_-3,  f(F_-3) = 3
4:  f(4) = F₄,  f(F₄) = -4,  f(-4) = F_-4,  f(F_-4) = 4

Note the symmetries; each of the f(-4), f(-3), .., f(3), f(4) is listed twice in the above table.

Because the cycle length must be 4, F_i ≠ i or -i, and this means full cycles require an even number of negative representable integers, and an even number of positive representable integers.

If signed integer overflow were well defined, for example INT_MIN - 1 == INT_MAX && INT_MAX + 1 == INT_MIN, then we only need an even number of total nonzero representable integers. Unfortunately, for typical N-bit two's complement signed integers, there are 2^N-1 nonzero representable integers -- an odd number.

(If we could distinguish between +0 and -0, then we would require odd and even number of negative and positive representations (or even and odd, respectively).)

---

If we only consider some limited range of integers representable by the int type used, say -L to +L inclusive, where L > 1, INT_MIN < -L and L < INT_MAX, and we use exactly one zero, there is a trivial solution.

(Note that the function might work outside that interval, too, depending on the overflow rules and internal representation, but the above range is guaranteed to work, regardless of the implementation details or limits on the architecture. This is very portable code, in other words.)

For illustration, consider this table:

f(-4) = +3
f(-3) = -4
f(-2) = +1
f(-1) = -2
f(0) = 0
f(1) = +2
f(2) = -1
f(3) = +4
f(4) = -3

(The cycles resulting from above are -4 ⇒ +3 ⇒ +4 ⇒ -3 ⇒ -4, and -2 ⇒ +1 ⇒ +2 ⇒ -1 ⇒ -2, with zero always mapping to zero. In essence, the sign and whether the number is odd or not, determine the "quadrant" (place in the cycle) the value lies in. Every second step, the sign changes.)

We treat positive and negative values differently, and odd and even values differently, and zero always maps to zero. For positive integers x, we can use (x & 1) to check if x is odd, regardless of what the internal representation of x is.

So, here is my suggestion that implements the above table:

int f(const int x)
{
    if (x < 0) {
        if ((-x) & 1)
            return -1 + x;
        else
            return -1 - x;
    } else
    if (x > 0) {
        if (x & 1)
            return 1 + x;
        else
            return 1 - x;
    } else
        return 0;
}

Note that because x is only negated, and incremented or decremented by one, the specified range -L to +L inclusive is guaranteed to work (given L > 1, INT_MIN < -L, and L < INT_MAX; i.e. -L-1 and L+1 being representable).

Questions?

Answer 3

Implementing the solution suggested by @Bathsheba.

The following code is assuming 32 bit int and that the casting of unsigned to signed is defined as the reverse of casting signed to unsigned:

int F(int x) {
    unisgned real, im, ux = (unsigned) x;

    // Split into real and imaginary part
    real = ux >> 16;  // Real part is upper 16 bits
    im = ux & 0xFFFF; // Imaginary part is lower 16 bits

    ux = real | (-im) << 16;  // Multiply by i 

    return (int) ux;  // return the result
}

Note: The last cast is implementation defined if ux is to large to be a signed int value.