Bestimmung der Funktion f(f(n)) == -n

Question

Eine Frage, die mir bei meinem letzten Vorstellungsgespräch gestellt wurde:

Eine Funktion entwerfen f , so dass:

f(f(n)) == -n

Wo n ist ein 32-Bit vorzeichenbehaftete Ganzzahl Sie können nicht mit komplexen Zahlen arithmetisch rechnen.

Wenn Sie eine solche Funktion nicht für den gesamten Zahlenbereich entwickeln können, entwickeln Sie sie für den größtmöglichen Bereich.

Irgendwelche Ideen?

Answer 1

Dies funktioniert für den Bereich von -1073741823 bis 1073741822:

int F(int n)
{
    if(n < 0)
    {
        if(n > -1073741824)
            n = -1073741824 + n;
        else n = -(n + 1073741824);
    }
    else
    {
        if(n < 1073741823)
            n = 1073741823 + n;
        else n = -(n - 1073741823);
    }
    return n;
}

Es funktioniert, indem der verfügbare Bereich eines 32-Bit-Int mit Vorzeichen genommen und durch zwei geteilt wird. Die erste Iteration der Funktion platziert n außerhalb dieses Bereichs. Bei der zweiten Iteration wird geprüft, ob der Wert außerhalb des Bereichs liegt - wenn ja, wird er wieder in den Bereich gesetzt, aber negativ.

Auf diese Weise wird ein zusätzliches "Bit" an Informationen über den Wert n gespeichert.

Answer 2

void f(int x)
{
     Console.WriteLine(string.Format("f(f({0})) == -{0}",x));
}

Tut mir leid, Leute... es war zu verlockend ;)

Answer 3

C++ Lösung;

long long f(int n){return static_cast <long long> (n);}
int f(long long n){return -static_cast <int> (n);}

int n = 777;
assert(f(f(n)) == -n);

Answer 4

Eine weitere betrügerische Lösung. Wir verwenden eine Sprache, die das Überladen von Operatoren erlaubt. Dann lassen wir f(x) etwas zurückgeben, das überladen ist == immer true zurückgeben. Dies scheint mit der Problembeschreibung vereinbar zu sein, widerspricht aber offensichtlich dem Sinn des Rätsels.

Beispiel Ruby:

class Cheat
  def ==(n)
     true
  end
end

def f(n)
  Cheat.new
end

Das ergibt:

>> f(f(1)) == -1
=> true

aber auch (nicht allzu überraschend)

>> f(f(1)) == "hello world"
=> true

Answer 5

int f(const int n)  {
    static int last_n;

    if (n == 0)
        return 0;
    else if (n == last_n)
        return -n;
    else
    {
        last_n = n;
        return n;
    }
}

Hackerisch, aber korrekt.