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

int f( int n ){
    return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}

Answer 2

Hier ist ein kurze Python-Antwort :

def f(n):
  m = -n if n % 2 == 0 else n
  return m + sign(n)

Allgemeiner Fall

Mit einer leichten Änderung der obigen Formulierung kann der Fall behandelt werden, dass wir k Selbstaufrufe, um die Eingabe zu negieren - zum Beispiel, wenn k = 3 würde dies bedeuten g(g(g(n))) = -n :

def g(n):
  if n % k: return n + sign(n)
  return -n + (k - 1) * sign(n)

Dies funktioniert, indem man 0 an Ort und Stelle lässt und Zyklen der Länge 2 * k erzeugt, so dass innerhalb eines Zyklus n und -n den Abstand k haben. Konkret sieht jeder Zyklus so aus:

N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)

oder, um das Verständnis zu erleichtern, sind hier Beispielzyklen mit k = 3 :

1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6

Dieser Satz von Zyklen maximiert die Bereiche von Eingaben, die mit jedem Maschinentyp funktionieren, der um Null herum zentriert ist, wie z. B. die Typen int32 mit Vorzeichen oder int64 mit Vorzeichen.

Analyse der kompatiblen Bereiche

Die Karte x -> f(x) müssen in der Tat Zyklen der Länge 2 * k , wobei x = 0 ist ein Spezialfall eines Zyklus der Länge 1, da -0 = 0. Das Problem für allgemeine k ist dann und nur dann lösbar, wenn der Bereich der Eingabe - 1 (zum Ausgleich von 0) ein Vielfaches von 2 * k ist und der positive und der negative Bereich einander entgegengesetzt sind.

Bei vorzeichenbehafteten Ganzzahlendarstellungen gibt es immer eine kleinste negative Zahl ohne positives Gegenstück im Bereich, so dass das Problem für den gesamten Bereich unlösbar wird. Zum Beispiel, eine signed char hat den Bereich [-128, 127], also ist es unmöglich, dass f(f(-128)) = 128 innerhalb des angegebenen Bereichs.

Answer 3

Eine bizarre und nur wenig clevere Lösung in Scala mit impliziten Konvertierungen:

sealed trait IntWrapper {
  val n: Int
}

case class First(n: Int) extends IntWrapper
case class Second(n: Int) extends IntWrapper
case class Last(n: Int) extends IntWrapper

implicit def int2wrapper(n: Int) = First(n)
implicit def wrapper2int(w: IntWrapper) = w.n

def f(n: IntWrapper) = n match {
  case First(x) => Second(x)
  case Second(x) => Last(-x)
}

Ich glaube aber nicht, dass das die richtige Idee ist.

Answer 4

Golf spielen in coffeescript:

f = (n)-> -n[0] or [n]

Answer 5

Lua:

function f(n)
    if type(n) == "number" then
        return (-number) .. ""
    else
        return number + 0
    end
end