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

Eine weitere betrügerische Lösung in C++ ist das Überladen von Operatoren.

struct func {
    int n;
    func operator()(int k) { n = -k; return *this; }
    int operator()(const func &inst) { return inst.n; }
} f;

Answer 2

Objektiv-C

Dies funktioniert für alle Zahlen außer "-1".

Wenn Sie von der Verwendung von int zu verwenden NSInt dann können Sie die Werte -1 auf NULL und sie dann beim zweiten Mal in +1 umwandeln, aber ich glaube, dass NSInt betrügt, was der Fragesteller beabsichtigt.

---

f(n):

-(int)f:(int)n {
    if (abs(n)==1) {
        n = -1;
    } else {
        if (abs(n)%2) {//o
            if (n>0) {//+
                n--;
                n*=+1;
            } else if (n<0) {//-
                n++;
                n*=+1;
            }
        } else {//e
            if (n>0) {//+
                n++;
                n*=-1;
            } else if (n<0) {//-
                n--;
                n*=-1;
            }
        }
    }
    return n;
}

Natürlich könnte man das alles auf eine Zeile kürzen, aber dann können andere Leute vielleicht nicht mehr mitlesen...

Wie auch immer, ich habe die BOOLEAN-Logik im Zustand der Zahl gespeichert, die entweder ungerade oder gerade ist.

Answer 3

F

let f n =
    match n with
    | n when n % 2 = 0 -> -n + System.Math.Sign n
    | _ -> n - System.Math.Sign -n

wobei n derart, dass System.Int32.MinValue < n < System.Int32.MaxValue .

Answer 4

Ich habe Golf gespielt diese Antwort von Rodrick Chapman .

Ohne Zweige: 74 Zeichen

int f(int i){return(-((i&1)<<1)|1)*i-(-((i>>>31)<<1)|1)*(((i|-i)>>31)&1);}

Mit Zweigen, im Java-Stil: 58 Zeichen

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

Mit Zweigen, C-Stil: 52 Zeichen

int f(int i){return i?(((i&1)?-i:i)+(i>0?-1:1)):0;}

---

Nach einem kurzen, aber aussagekräftigen Benchmark stellt sich heraus, dass die verzweigte Version auf meinem Rechner 33 % schneller ist. (Zufälliger Datensatz von positiven und negativen Zahlen, genügend Wiederholungen und verhindert, dass der Compiler den Code optimiert, mit Warmup). Das ist angesichts der Anzahl der Operationen in der unverzweigten Version und der möglichen guten Verzweigungsvorhersage aufgrund der Tatsache, dass die Funktion zweimal aufgerufen wird, nicht so überraschend: f(f(i)) . Wenn ich die Benchmark zu messen ändere: f(i) ist die verzweigte Version nur 28 % schneller. Ich denke, das beweist, dass die Verzweigungsvorhersage im ersten Fall tatsächlich etwas gebracht hat. Ein weiterer Beweis: Beim Testen mit f(f(f(f(i)))) stellt sich heraus, dass die verzweigte Version 42 % schneller ist.

Answer 5

Lösung im Wolfram-Sprache :

f[f[n_]] := -n

Anwendung:

In[2]:= f[f[10]]                                                                                                                                                                                                                                                                              
Out[2]= -10
In[3]:= f[10]                                                                                                                                                                                                                                                                                 
Out[3]= f[10]

Da die Frage nichts über den Wert von f(n) aussagt, bleibt f[n] unbewertet.