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

Verwendet Globals...aber so?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}

Answer 2

Niemand hat je gesagt, dass f(x) vom gleichen Typ sein muss.

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]

f(2) => [2]
f(f(2)) => -2

Answer 3

Ich würde die 2 höchstwertigen Bits ändern.

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

Wie Sie sehen, handelt es sich nur um eine Addition, bei der das getragene Stück weggelassen wird.

Wie bin ich zu der Antwort gekommen? Mein erster Gedanke war die Notwendigkeit der Symmetrie. 4 Umdrehungen, um wieder an den Ausgangspunkt zu gelangen. Zuerst dachte ich, das sind 2 Bits Gray-Code. Dann dachte ich, dass eigentlich das Standard-Binärsystem ausreicht.

Answer 4

Hier ist eine Lösung, die von der Anforderung oder Behauptung ausgeht, dass komplexe Zahlen nicht zur Lösung dieses Problems verwendet werden können.

Die Multiplikation mit der Quadratwurzel von -1 ist eine Idee, die nur deshalb zu scheitern scheint, weil -1 keine Quadratwurzel über die ganzen Zahlen hat. Aber wenn man mit einem Programm wie Mathematica herumspielt, erhält man zum Beispiel die Gleichung

(1849436465 2 +1) mod (2 32 -3) = 0.

und das ist fast so gut wie eine Quadratwurzel aus -1. Das Ergebnis der Funktion muss eine ganze Zahl mit Vorzeichen sein. Daher werde ich eine modifizierte Modulo-Operation mods(x,n) verwenden, die die ganze Zahl y zurückgibt, die kongruent zu x modulo n ist und am nächsten an 0 liegt. Nur sehr wenige Programmiersprachen haben eine Modulo-Operation, aber sie kann leicht definiert werden. In Python ist sie z.B. so:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

Unter Verwendung der obigen Gleichung kann das Problem nun wie folgt gelöst werden

def f(x):
    return mods(x*1849436465, 2**32-3)

Dies erfüllt f(f(x)) = -x für alle ganzen Zahlen aus dem Bereich [-2``31``-2, 2``31``-2] . Die Ergebnisse der f(x) liegen ebenfalls in diesem Bereich, aber die Berechnung würde natürlich 64-Bit-Ganzzahlen erfordern.

Answer 5

C# für einen Bereich von 2^32 - 1 Zahlen, alle int32 Zahlen außer (Int32.MinValue)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));

    Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647

Drucke:

2147483647
3
2
1
0
-1
-2
-3
-2147483647