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

Im Wesentlichen muss die Funktion den verfügbaren Bereich in Zyklen der Größe 4 unterteilen, wobei -n am entgegengesetzten Ende des Zyklus von n liegt. Allerdings muss 0 Teil eines Zyklus der Größe 1 sein, weil sonst 0->x->0->x != -x . Da 0 allein ist, muss es 3 andere Werte in unserem Bereich (dessen Größe ein Vielfaches von 4 ist) geben, die nicht in einem richtigen Zyklus mit 4 Elementen liegen.

Ich habe diese zusätzlichen seltsamen Werte gewählt, um MIN_INT , MAX_INT und MIN_INT+1 . Außerdem, MIN_INT+1 wird abgebildet auf MAX_INT richtig, bleiben aber dort hängen und können nicht zurück. Ich denke, das ist der beste Kompromiss, denn er hat die schöne Eigenschaft, dass nur die Extremwerte nicht korrekt funktionieren. Außerdem bedeutet es, dass es funktioniert für alle BigInts.

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

Answer 2

Niemand hat gesagt, dass sie staatenlos sein muss.

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

Schummeln, aber nicht so viel wie bei vielen anderen Beispielen. Noch böser wäre es, auf dem Stack nachzusehen, ob die Adresse des Aufrufers &f ist, aber das wäre portabler (wenn auch nicht thread-sicher... die thread-sichere Version würde TLS verwenden). Noch böser:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

Natürlich funktioniert beides nicht so gut für den Fall von MIN_INT32, aber es gibt kaum etwas, was man dagegen tun kann, es sei denn, man darf einen breiteren Typ zurückgeben.

Answer 3

Ich könnte mir vorstellen, das 31. Bit als imaginäres ( i ) wäre ein Ansatz, der die Hälfte der Gesamtreichweite unterstützen würde.

Answer 4

Funktioniert für n= [0 .. 2^31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}

Answer 5

Das Problem besagt "32-Bit-Ganzzahlen mit Vorzeichen", gibt aber nicht an, ob es sich um Zweierkomplement oder Einerkomplement .

Wenn Sie die Einerkomplementierung verwenden, treten alle 2^32 Werte in Zyklen der Länge vier auf - Sie brauchen keinen Sonderfall für Null, und Sie brauchen auch keine Konditionale.

In C:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

Dies funktioniert wie folgt

1. Vertauschen der hohen und niedrigen 16-Bit-Blöcke
2. Invertieren eines der Blöcke

Nach zwei Durchläufen haben wir die bitweise Umkehrung des ursprünglichen Wertes. In der Einerkomplement-Darstellung ist dies gleichbedeutend mit der Negation.

Beispiele:

Pass |        x
-----+-------------------
   0 | 00000001      (+1)
   1 | 0001FFFF (+131071)
   2 | FFFFFFFE      (-1)
   3 | FFFE0000 (-131071)
   4 | 00000001      (+1)

Pass |        x
-----+-------------------
   0 | 00000000      (+0)
   1 | 0000FFFF  (+65535)
   2 | FFFFFFFF      (-0)
   3 | FFFF0000  (-65535)
   4 | 00000000      (+0)