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

Javascript

function f(n)  { 
        return typeof n === "number" ? 
        function() {return -n} : 
        n();
}

Answer 2

Ausgehend von den Fragen, die die Interviewer von Microsoft/Google normalerweise in ihren Interviews stellen, glaube ich, dass der Fragesteller eine innovative, leichtgewichtige, einfache Lösung meint, die bitweise Operationen verwendet, und nicht diese komplizierten Antworten auf hohem Niveau.

Inspiriert durch die Antwort von @eipipuz habe ich diese C++-Funktion geschrieben (aber nicht ausgeführt):

int32_t f(int32_t n){
    int32_t temp = n & 00111111111111111111111111111111;
    x = n >> 30;
    x++;
    x = x << 30;
    return x | temp;
}

Er speichert die beiden äußersten linken Bits von n in x addiert 1 zu x und ersetzt es dann als die beiden äußersten linken Bits von n wieder.

Wenn wir weiterlaufen f(n) mit einem anderen f(n) als Parameter n werden die beiden linken Bits wie folgt gedreht:

00 --> 01 --> 10 --> 11 --> 00 ...

Beachten Sie, dass sich die 30 Bits ganz rechts nicht ändern. Beispiele für 8-Bit-Ganzzahlen:

Beispiel 1:

• > f(00001111) = 01001111
• > f(01001111) = 10001111 [dies ist das Negativ des ursprünglichen Wertes, 00001111]

Beispiel 2:

• > f(11101010) = 00101010
• > f(00101010) = 01101010 [dies ist das Negativ des ursprünglichen Wertes, 11101010]

Answer 3

Unter awk Da kaum Informationen weitergegeben werden, muss man auf Methoden zurückgreifen, die es erlauben, Zustandsinformationen als Teil der Funktionsrückgabe zu übergeben, ohne die Verwendbarkeit dessen, was weitergegeben wird, zu gefährden:

jot - -5 5 | mawk 'function _(__,___) { 

     return (__~(___=" ")) \
      \
      ? substr("",sub("^[ ]?[+- ]*",\
        substr(" -",__~__,index("_"___,___)-\
              (__~"[-]")),__))\
            (__~"[-]"?"":___)__\
      : (+__<-__?___:(___)___)__ 

  } BEGIN { CONVFMT=OFMT="%.17g" 
  } { 
      print "orig",           +(__=$(__<__))<-__?__:" "__,
            "f(n)....",        _(__),_(_(__)),_(_(_(__))),
                         _(_(_(_(__)))), _(_(_(_(_(__))))) 

  }' |gcat -n | lgp3 5 

 1  orig -5 f(n)....  -5   5  -5   5  -5
 2  orig -4 f(n)....  -4   4  -4   4  -4
 3  orig -3 f(n)....  -3   3  -3   3  -3
 4  orig -2 f(n)....  -2   2  -2   2  -2
 5  orig -1 f(n)....  -1   1  -1   1  -1

 6  orig  0 f(n)....   0  -0   0  -0   0
 7  orig  1 f(n)....   1  -1   1  -1   1
 8  orig  2 f(n)....   2  -2   2  -2   2
 9  orig  3 f(n)....   3  -3   3  -3   3
10  orig  4 f(n)....   4  -4   4  -4   4

11  orig  5 f(n)....   5  -5   5  -5   5

Die Grenze ist also, dass nur Ganzzahlen oder Fließkommazahlen, die bereits in einem String-Format vorliegen, ohne Risiko verwendet werden können, da ein zusätzliches ASCII-Leerzeichen \040 wird als Statusinformation vorangestellt

Diese Methode hat den Vorteil, dass

1. es ist bereit, Ihnen eine "Negativ-Null" zu liefern,

2. für ganze Zahlen kleiner als 2^53 in absoluten Zahlen, einfach ein Pluszeichen hinzufügen,

   d.h. +f(f(_))

   zum Funktionsaufruf selbst würde eine implizite Typ-Casting für Sie durchgeführt, und der resultierende Wert wird wieder numerisch sein

   für Big Integer, einfach substr() ohne führende Leerzeichen

3. mit großen Zahlen umgehen, ohne den Verlust von Präzision, die durch die Umwandlung in einen doppelt präzisen Float entsteht

`

    1   orig -99999999999999999999999999999999 
        f(n).... 
             -99999999999999999999999999999999   
              99999999999999999999999999999999
             -99999999999999999999999999999999   
              99999999999999999999999999999999  
             -99999999999999999999999999999999

 2  orig      -1239999999999999999999999999999 
    f(n)....  -1239999999999999999999999999999                   
               1239999999999999999999999999999
              -1239999999999999999999999999999
               1239999999999999999999999999999
              -1239999999999999999999999999999`

Answer 4

Ich dachte, die größtmögliche Reichweite auf eine modulare arithmetische Lösung hinwies. In einigen modularen Basen M gibt es eine Zahl, die, wenn sie quadriert wird, kongruent zu M-1 ist (was kongruent zu -1 ist). Zum Beispiel, wenn M=13, 5*5=25, 25 mod 13=12 (= -1)
Wie auch immer, hier ist etwas Python-Code für M=2**32-3.

def f(x):
    m=2**32-3;
    halfm=m//2;
    i_mod_m=1849436465
    if abs( x ) >halfm:
        raise "too big"
    if x<0:
        x+=m
    x=(i_mod_m*x) % m
    if (x>halfm):
        x-=m
    return x;

Beachten Sie, dass es 3 Werte gibt, für die es nicht funktioniert: 2 ** 31-1, -(2 ** 31-1) und -(2 ** 31)

Answer 5

int f(int x){
    if (x < 0)
        return x;
    return ~x+1; //two's complement
}