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

return x ^ ((x%2) ? 1 : -INT_MAX);

Answer 2

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

Answer 3

Als Mathematiker möchte ich meine Sichtweise zu diesem interessanten Problem darlegen. Ich glaube, ich habe die effizienteste Lösung.

Wenn ich mich richtig erinnere, negiert man eine vorzeichenbehaftete 32-Bit-Ganzzahl, indem man einfach das erste Bit umdreht. Zum Beispiel, wenn n = 1001 1101 1110 1011 1110 0000 1110 1010, dann -n = 0001 1101 1110 1011 1110 0000 1110 1010.

Wie definiert man also eine Funktion f, die eine 32-Bit-Ganzzahl mit Vorzeichen annimmt und eine andere 32-Bit-Ganzzahl mit Vorzeichen zurückgibt, mit der Eigenschaft, dass die zweimalige Annahme von f dasselbe ist wie das Umdrehen des ersten Bits?

Lassen Sie mich die Frage neu formulieren, ohne arithmetische Konzepte wie ganze Zahlen zu erwähnen.

Wie definiert man eine Funktion f, die eine Folge von Nullen und Einsen der Länge 32 annimmt und eine Folge von Nullen und Einsen der gleichen Länge zurückgibt, mit der Eigenschaft, dass die zweimalige Ausführung von f dasselbe ist wie das Umdrehen des ersten Bits?

Beobachtung: Wenn Sie die obige Frage für den 32-Bit-Fall beantworten können, dann können Sie sie auch für den 64-Bit-Fall, den 100-Bit-Fall, usw. beantworten. Man wendet f einfach auf die ersten 32 Bit an.

Wenn Sie nun die Frage für den 2-Bit-Fall beantworten können, Voila!

Und ja, es stellt sich heraus, dass es ausreicht, die ersten 2 Bits zu ändern.

Hier ist der Pseudocode

1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.

Bemerkung: Der Schritt 2 und der Schritt 3 können zusammen als (a,b) --> (-b, a) zusammengefasst werden. Kommt Ihnen das bekannt vor? Das sollte Sie an die 90-Grad-Drehung der Ebene und die Multiplikation mit der Quadratwurzel von -1 erinnern.

Wenn ich nur den Pseudocode ohne das lange Vorspiel präsentieren würde, würde es wie ein Kaninchen aus dem Hut erscheinen, ich wollte erklären, wie ich zu der Lösung gekommen bin.

Answer 4

In PHP

function f($n) {
    if(is_int($n)) {
        return (string)$n;
    }
    else {
        return (int)$n * (-1);
    }
}

Ich bin sicher, Sie können den Sinn dieser Methode für andere Sprachen verstehen. Ich habe explizit zurück auf int gecastet, um es für Leute, die keine schwach typisierten Sprachen verwenden, klarer zu machen. In manchen Sprachen müssen Sie die Funktion überladen.

Das Schöne an dieser Lösung ist, dass sie unabhängig davon funktioniert, ob Sie mit einer Zeichenkette oder einer ganzen Zahl beginnen, und dass sie bei der Rückgabe von f(n) keine sichtbaren Änderungen vornimmt.

Meiner Meinung nach fragt der Interviewer: "Weiß der Bewerber, wie man Daten markiert, um sie später zu bearbeiten?" und "Weiß der Bewerber, wie man Daten markiert, ohne sie zu verändern?" Sie können dies mit Doubles, Zeichenketten oder jedem anderen Datentyp tun, den Sie zuordnen möchten.

Answer 5

Das ist ganz einfach!

Jede Zahl wird in 4er-Zyklen auf eine andere abgebildet, wenn die erforderliche Bedingung erfüllt ist.

Beispiel:

Die Regeln lauten:

• 0 0

• ±2³¹ ±2³¹

• ungerade gerade, gerade -ungerade:

  forall k, 0 < k < 2³: (2k-1) (2k) (-2k+1) (-2k) (2k-1)

Die einzigen nicht übereinstimmenden Werte sind ±(2³¹-1), da es nur zwei gibt. Es muss zwei geben, die nicht zusammenpassen denn es gibt nur ein Vielfaches von vier der Zahlen in einem Zweierkomplement-System wobei 0 und ±2³¹ bereits reserviert sind.

In einem Einerkomplement-System gibt es +0 und -0. Das war's:

forall k, 0 < k < 2³: (+2k) (+2k+1) (-2k) (-2k-1) (+2k)