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

Obwohl in der Frage gesagt wurde, dass n ein 32-Bit-Int sein muss, wurde nicht gesagt, dass der Parameter oder der Rückgabetyp ein 32-Bit-Int sein muss. Dies sollte in Java kompilierbar sein - in C könnte man das != 0 weglassen.

private final long MAGIC_BIT=1<<38;
long f(long n) {
    return n & MAGIC_BIT != 0 ? -(n & !MAGIC_BIT) : n | MAGIC_BIT;
}

bearbeiten:

Das ist eigentlich eine sehr gute Frage für ein Vorstellungsgespräch. Die besten Fragen sind die, die schwer oder gar nicht zu beantworten sind, weil sie die Leute zwingen, darüber nachzudenken, und man kann sie beobachten und darauf achten:

• Geben sie einfach auf?
• Sagen sie, es sei dumm?
• Versuchen sie einzigartige Ansätze?
• Kommunizieren sie mit Ihnen, während sie an dem Problem arbeiten?
• Fordern sie eine weitere Verfeinerung der Anforderungen?

usw.

Beantworten Sie niemals nur Verhaltensfragen, es sei denn, Sie haben eine SEHR GUTE Antwort. Seien Sie immer freundlich und versuchen Sie, den Fragesteller einzubeziehen. Lassen Sie sich nicht frustrieren und geben Sie nicht vorzeitig auf! Wenn Sie wirklich nicht weiterkommen, versuchen Sie etwas völlig Illegales, das funktionieren könnte, und Sie erhalten fast die volle Punktzahl.

Answer 2

Wie wäre es damit?

int nasty(int input)
{
    return input + INT_MAX/2;
}

Answer 3

1. Konvertieren von n in die Darstellung von Vorzeichen und Größenordnung;
2. Fügen Sie 1/4 eines Bereichs hinzu;

3. Zurück konvertieren.

   #define STYPE int
   STYPE sign_bit = (unsigned STYPE) 1 << ( sizeof ( STYPE ) * 8  - 1 );
   STYPE f ( STYPE f )
   {
       unsigned STYPE smf = f > 0 ? f : -f | sign_bit;
       smf += sign_bit >> 1;
       return smf & sign_bit ? -( smf & ~sign_bit ) : smf;
   }

Answer 4

Anhand der in der Frage angegebenen Informationen können Sie

1. Umwandlung von 2-Komplement- in Vorzeichen-Bit-Darstellung
2. Wenn das letzte Bit gesetzt ist, werden das Vorzeichenbit und das letzte Bit umgedreht; andernfalls wird nur das letzte Bit umgedreht.
3. Zurück zu 2-Komplement konvertieren.

Sie gehen also grundsätzlich von ungerade -> gerade -> ungerade oder gerade -> ungerade -> gerade und ändern das Vorzeichen nur bei geraden Zahlen. Die einzige Zahl, bei der das nicht funktioniert, ist -2^31

Code:

function f(x) {
  var neg = x < 0;
  x = Math.abs(x) ^ 1;
  if (x & 1) {
    neg = !neg;
  }
  return neg ? -x : x;
}

Answer 5

f(n) { return -1 * abs(n) }

Wie kann ich damit Überlaufprobleme umgehen? Oder verstehe ich den Sinn nicht?