Entwurfsfunktion f (f (n)) == -n

841

Eine Frage, die ich bei meinem letzten Interview bekommen habe:

Entwerfen Sie eine Funktion f, so dass:

f(f(n)) == -n

Wo nist eine 32-Bit- Ganzzahl mit Vorzeichen ? Sie können keine komplexe Zahlenarithmetik verwenden.

Wenn Sie eine solche Funktion nicht für den gesamten Zahlenbereich entwerfen können, entwerfen Sie sie für den größtmöglichen Bereich.

Irgendwelche Ideen?

Gumbo
quelle
2
Für welchen Job war dieses Interview?
Tymtam

Antworten:

377

Wie wäre es mit:

f (n) = Vorzeichen (n) - (-1) n * n

In Python:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

Python befördert Ganzzahlen automatisch zu Longs beliebiger Länge. In anderen Sprachen läuft die größte positive Ganzzahl über, sodass sie für alle Ganzzahlen außer dieser funktioniert.


Damit es für reelle Zahlen funktioniert, müssen Sie das n in (-1) n durch ersetzen { ceiling(n) if n>0; floor(n) if n<0 }.

In C # (funktioniert für jedes Double, außer in Überlaufsituationen):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}
RossFabricant
quelle
10
Für -1 gebrochen, weil -1 * 0 immer noch 0 ist
Joel Coehoorn
3
Nein, ist es nicht. f (-1) = 0. f (0) = 1
1800 INFORMATIONEN
5
Es ist jedoch für 1 gebrochen. f (1) = 0. f (0) = 1
1800 INFORMATION
18
Hmm, Sparzustand mit geraden und ungeraden Zahlen, daran hätte ich denken sollen.
Unbekannt
38
Ich denke, das Wichtigste ist nicht die eigentliche Funktion (es gibt unendlich viele Lösungen), sondern der Prozess, mit dem Sie eine solche Funktion konstruieren können.
pyon
440

Sie haben nicht gesagt, welche Art von Sprache sie erwartet haben ... Hier ist eine statische Lösung (Haskell). Es spielt im Grunde mit den 2 wichtigsten Bits:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

In einer dynamischen Sprache (Python) ist das viel einfacher. Überprüfen Sie einfach, ob das Argument eine Zahl X ist, und geben Sie ein Lambda zurück, das -X zurückgibt:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()
Viraptor
quelle
23
Cool, ich liebe das ... der gleiche Ansatz in JavaScript: var f = function (n) {return (typeof n == 'function')? n (): function () {return -n; }}
Mark Renouf
Es ist wahrscheinlich nur so, dass mein Haskell sehr rostig ist, aber haben Sie das auf (f 0) überprüft? Es sieht so aus, als ob dies das gleiche Ergebnis wie (f 0x80000000) liefern sollte, zumindest wenn es sich um 32-Bit-Ints mit Wraparound-Arithmetik handelt (bei der Negationsoperation). Und das wäre schlecht.
Darius Bacon
11
Würde der durchschnittliche Interviewer überhaupt wissen, was ein Lambda-Konstrukt ist ?
Jeremy Powell
4
Natürlich funktioniert ein solcher Typ-Cheating-Trick auch in Haskell, obwohl er statisch ist : class C a b | a->b where { f :: a->b }; instance C Int (()->Int) where { f=const.negate };; instance C (()->Int) Int where { f=($()) }.
links um den
4
Was? Woher kam die Idee, dass typeof f (n) === 'function' ist, insbesondere wenn n eine Zahl ist und Sie eine zurückgegebene Zahl erwarten? Ich verstehe nicht, wie ein Instanzfall hier zutreffen könnte. Ich spreche Python nicht gut, aber in JS ist das Überprüfen des Arguments für einen Funktionstyp in diesem Fall einfach falsch. Hier gilt nur die numerische Lösung. f ist eine Funktion, f (n) ist eine Zahl.
Harry
284

Hier ist ein Beweis dafür, warum eine solche Funktion nicht für alle Zahlen existieren kann, wenn sie keine zusätzlichen Informationen verwendet (außer 32 Bit int):

Wir müssen f (0) = 0 haben. (Beweis: Angenommen, f (0) = x. Dann ist f (x) = f (f (0)) = -0 = 0. Nun ist -x = f (f (x) )) = f (0) = x, was bedeutet, dass x = 0.)

Weiter für jeden xund y, nehme an f(x) = y. Wir wollen f(y) = -xdann. Und f(f(y)) = -y => f(-x) = -y. Zusammenfassend: wenn f(x) = y, dann f(-x) = -yund f(y) = -xund f(-y) = x.

Wir müssen also alle ganzen Zahlen außer 0 in 4er-Sätze teilen, aber wir haben eine ungerade Anzahl solcher ganzen Zahlen; Nicht nur das, wenn wir die ganze Zahl entfernen, die kein positives Gegenstück hat, haben wir immer noch 2 (mod4) Zahlen.

Wenn wir die 2 verbleibenden Maximalzahlen (nach abs-Wert) entfernen, können wir die Funktion erhalten:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

Eine andere Möglichkeit ist natürlich, 0 nicht einzuhalten und die 2 Zahlen, die wir entfernt haben, als Bonus zu erhalten. (Aber das ist nur dumm, wenn.)

SurDin
quelle
29
Ich kann nicht glauben, dass ich so weit unten lesen musste, um eine gute prozedurale Lösung zu finden, die negative Zahlen verarbeitet, ohne auf globale Variablen oder Tricks zurückzugreifen, die den Code verschleiern. Wenn ich Sie mehr als einmal abstimmen könnte, würde ich.
Kyle Simek
Schöne Beobachtung, dass es in n vorzeichenbehafteten Bits eine ungerade Anzahl von Ganzzahlen ungleich Null gibt .
Andres Jaan Tack
Dies wäre auch meine Antwort, aber hüte dich vor dem Randfall n = -2147483648(Mindestwert); Sie können nicht abs(n)in diesem Fall, und das Ergebnis wird (oder eine Ausnahme) nicht definiert werden.
Kirk Broadhurst
1
@ a1kmm: Entschuldigung, -2³² oben sollte -2³¹ gewesen sein. Wie auch immer, der Fall, in dem f (0) ≠ 0 (und damit f (0) = - 2³¹) ist, ist tatsächlich der einfachere Fall, da wir gezeigt haben, dass diese beiden vom Rest getrennt sind. Der andere Fall, den wir berücksichtigen müssen, ist, dass f (0) = 0 ist, aber f (x) = - 2³¹ für einige x ≤ 0, x ≤ -2³¹. In diesem Fall ist f (-2³¹) = f (f (x)) = - x (Anmerkung -x kann nicht -2³¹ sein, da kein solches x existiert). Weiter sei f (-x) = y. Dann ist f (y) = f (f (-x)) = x. Wieder kann y nicht -2³¹ sein (als f (y) = x, aber f (-2³¹) = - x und x ist nicht 0). Also, -2³¹ = f (x) = f (f (y)) = - y, was unmöglich ist. In der Tat müssen 0 und -2³¹ vom Rest getrennt werden (nicht das Bild von irgendetwas anderem).
ShreevatsaR
1
@will Es gibt keine vorzeichenbehafteten Nullen, wenn es sich (wie ich annehme) um 32-Bit-Ganzzahlen mit Zweierkomplement handelt.
Goffrie
146

Dank Überladung in C ++:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}
Kontrolle
quelle
4
Leider haben die Funktionen, die Sie "f" nennen, aufgrund der Namensverfälschung tatsächlich seltsamere Namen.
Pyon
1
Ich habe an so etwas gedacht, aber als ich in C dachte, wurde das weggeworfen ... gute Arbeit!
Liran Orevi
@Rui Craverio: In .NET 3.5+ würde es nicht funktionieren, da der Autor das Schlüsselwort var als Variablennamen verwendet hat.
Kredns
72
technisch ... das ist nicht das, was die frage verlangt. Sie haben 2 f () -Funktionen definiert, f (int) und f (float), und die Fragen
lauten
2
@elcuco Technisch natürlich, aber logischerweise ist es eine Funktion mit mehreren Überladungen (damit können Sie f (f (42)) machen). Da die Definition nichts über Parameter und Rückgabewert aussagt, kann ich sie kaum als technische Definition akzeptieren.
Marek Toman
135

Oder Sie könnten den Präprozessor missbrauchen:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}
Skizz
quelle
Dann wären Sie also Konrad "Le Chiffre" Rudolph? Ich werde meinen Mantel bekommen. Ja, ich weiß über die ganze "void main" Sache Bescheid, aber ich füge eine "return 0" hinzu. ist nur so viel zusätzlicher Aufwand ;-)
Skizz
25
@Skizz, die Rückgabe von 0 von main ist in c ++ selbst mit dem Rückgabewert int nicht erforderlich. Wenn Sie es also richtig machen, geben Sie tatsächlich ein Zeichen weniger ein!
Dan Olson
10
Skizz missbraucht immer Präprozessor: D
Arnis Lapsa
23
Dies ist nicht eine Funktion ..so dies ist keine gültige Lösung
smerlin
3
@smerlin: Technisch gesehen handelt es sich um eine Inline-Funktion, die eine Inline-Funktion zurückgibt: Die Körper beider werden zur Kompilierungszeit oder kurz zuvor erweitert. Effizienter geht es nicht.
Jon Purdy
103

Dies gilt für alle negativen Zahlen.

    f (n) = abs (n)

Da es eine negative Zahl mehr gibt als positive Zahlen für zwei komplementäre Ganzzahlen, f(n) = abs(n)gilt dies für einen Fall mehr als für eine f(n) = n > 0 ? -n : nLösung, die dieselbe ist wie f(n) = -abs(n). Habe dich um eins ...: D.

AKTUALISIEREN

Nein, es ist nicht mehr für einen Fall gültig, wie ich gerade durch Litbs Kommentar erkannt habe ... abs(Int.Min)wird einfach überlaufen ...

Ich habe auch darüber nachgedacht, Mod 2-Informationen zu verwenden, bin aber zu dem Schluss gekommen, dass es nicht funktioniert ... zu früh. Wenn es richtig gemacht wird, funktioniert es für alle Zahlen, außer Int.Minweil dies überläuft.

AKTUALISIEREN

Ich habe eine Weile damit gespielt und nach einem netten Manipulationstrick gesucht, aber ich konnte keinen schönen Einzeiler finden, während die Mod 2-Lösung in einen passt.

    f (n) = 2n (abs (n)% 2) - n + sgn (n)

In C # wird dies wie folgt:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

Um es für alle Werte arbeitet, müssen Sie ersetzen Math.Abs()mit (n > 0) ? +n : -nund die Berechnung in einem Include - uncheckedBlock. Dann werden Sie sogar Int.Minauf sich selbst abgebildet, wie dies bei ungeprüfter Negation der Fall ist.

AKTUALISIEREN

Inspiriert von einer anderen Antwort werde ich erklären, wie die Funktion funktioniert und wie eine solche Funktion aufgebaut wird.

Beginnen wir ganz am Anfang. Die Funktion fwird wiederholt auf einen bestimmten Wert angewendet, nwodurch eine Folge von Werten erhalten wird.

    n => f (n) => f (f (n)) => f (f (f (n))) => f (f (f (n ())) => ...

Die Frage verlangt f(f(n)) = -n, dass zwei aufeinanderfolgende Anwendungen fdas Argument negieren. Zwei weitere Anträge von f- insgesamt vier - negieren das Argument erneut und ergeben nerneut.

    n => f (n) => -n => f (f (f (n))) => n => f (n) => ...

Jetzt gibt es einen offensichtlichen Zyklus der Länge vier. Das Ersetzen x = f(n)und Feststellen, dass die erhaltene Gleichung f(f(f(n))) = f(f(x)) = -xgilt, ergibt Folgendes.

    n => x => -n => -x => n => ...

Wir erhalten also einen Zyklus der Länge vier mit zwei Zahlen und den beiden negierten Zahlen. Wenn Sie sich den Zyklus als Rechteck vorstellen, befinden sich negierte Werte an gegenüberliegenden Ecken.

Eine von vielen Lösungen zur Konstruktion eines solchen Zyklus ist die folgende ab n.

 n => negiere und subtrahiere eins
-n - 1 = - (n + 1) => addiere eins
-n => negiere und füge eins hinzu
 n + 1 => subtrahiere eins
 n

Ein konkretes Beispiel ist ein solcher Zyklus +1 => -2 => -1 => +2 => +1. Wir sind fast fertig. Wenn wir feststellen, dass der konstruierte Zyklus eine ungerade positive Zahl enthält, sein gerader Nachfolger und beide Zahlen negieren, können wir die ganzen Zahlen leicht in viele solcher Zyklen unterteilen ( 2^32ist ein Vielfaches von vier) und haben eine Funktion gefunden, die die Bedingungen erfüllt.

Aber wir haben ein Problem mit Null. Der Zyklus muss enthalten, 0 => x => 0da Null für sich selbst negiert wird. Und weil der Zyklus schon sagt 0 => x, folgt er 0 => x => 0 => x. Dies ist nur ein Zyklus der Länge zwei und xwird nach zwei Anwendungen in sich selbst umgewandelt, nicht in -x. Glücklicherweise gibt es einen Fall, der das Problem löst. Wenn Xgleich Null ist, erhalten wir einen Zyklus der Länge Eins, der nur Null enthält, und wir haben dieses Problem gelöst, indem wir daraus geschlossen haben, dass Null ein fester Punkt von ist f.

Erledigt? Fast. Wir haben 2^32Zahlen, Null ist ein fester Punkt, der 2^32 - 1Zahlen hinterlässt , und wir müssen diese Zahl in Zyklen von vier Zahlen aufteilen. Schlecht, das 2^32 - 1ist kein Vielfaches von vier - es bleiben drei Zahlen in keinem Zyklus der Länge vier.

Ich werde den verbleibenden Teil der Lösung anhand des kleineren Satzes von 3-Bit-vorzeichenbehafteten Itegern von -4bis erklären +3. Wir sind mit Null fertig. Wir haben einen vollständigen Zyklus +1 => -2 => -1 => +2 => +1. Nun konstruieren wir den Zyklus ab +3.

    +3 => -4 => -3 => +4 => +3

Das auftretende Problem besteht darin, dass +4es nicht als 3-Bit-Ganzzahl dargestellt werden kann. Wir würden +4durch Negieren -3auf +3- was immer noch eine gültige 3-Bit-Ganzzahl ist - erhalten, aber dann addieren wir eine zu +3(binär 011) ergibt 100binär. Als vorzeichenlose Ganzzahl +4interpretiert ist es, aber wir müssen es als vorzeichenbehaftete Ganzzahl interpretieren -4. Tatsächlich ist also -4für dieses Beispiel oder Int.MinValueim allgemeinen Fall ein zweiter fester Punkt der ganzzahligen arithmetischen Negation - 0 und Int.MinValuewerden auf sich selbst abgebildet. Der Zyklus ist also tatsächlich wie folgt.

    +3 => -4 => -3 => -4 => -3

Es ist ein Zyklus der Länge zwei und +3tritt zusätzlich über in den Zyklus ein -4. Infolgedessen -4wird es nach zwei Funktionsanwendungen korrekt auf sich selbst abgebildet, wird nach zwei Funktionsanwendungen korrekt auf sich selbst +3abgebildet, wird jedoch -3nach zwei Funktionsanwendungen -3fälschlicherweise auf sich selbst abgebildet.

Also haben wir eine Funktion konstruiert, die für alle ganzen Zahlen außer einer funktioniert. Können wir es besser machen? Nein Wir können nicht. Warum? Wir müssen Zyklen der Länge vier konstruieren und können den gesamten ganzzahligen Bereich bis zu vier Werten abdecken. Die übrigen Werte sind die beiden Fixpunkte 0und Int.MinValuedas muss sich selbst zugeordnet werden und zwei beliebige ganze Zahlen xund -xdas muss durch zwei Funktionsanwendungen aufeinander abgebildet werden.

Zur Karte xzu -xund umgekehrt , sie müssen einen Cyclus bilden vier , und sie müssen an gegenüberliegenden Ecken des Zyklus befinden. In der Folge 0und Int.MinValuemüssen auch an gegenüberliegenden Ecken sein. Dadurch werden die beiden Fixpunkte und nach zwei Funktionsanwendungen korrekt zugeordnet xund -xausgetauscht, und es verbleiben zwei fehlerhafte Eingaben. Es ist also nicht möglich, eine Funktion zu konstruieren, die für alle Werte funktioniert, aber wir haben eine, die für alle Werte außer einem funktioniert, und dies ist das Beste, was wir erreichen können.0Int.MinValue

Daniel Brückner
quelle
Erfüllt nicht die Kriterien: abs (abs (n))! = -N
Dan Olson
Sicher, für alle negativen Zahlen, wie er sagte. Das war Teil der Frage: Wenn Sie keine allgemeine finden können, überlegen Sie sich eine, die für ein möglichst breites Spektrum geeignet ist.
Jalf
Diese Antwort ist mindestens so gut wie die Antwort von Marj Synowiec und Rowland Shaw. Sie funktioniert nur für einen anderen Zahlenbereich
1800 INFORMATION
19
Alter, du kannst genauso gut die "UPDATE" loswerden und einfach eine zusammenhängende richtige Antwort schreiben. Das untere 3/4 ("inspiriert von einer anderen Antwort") ist fantastisch.
Andres Jaan Tack
1
Ich mag die abs-Lösung für negative Zahlen sehr. Einfach und leicht verständlich.
Thorbjørn Ravn Andersen
97

Mit komplexen Zahlen können Sie die Aufgabe des Negierens einer Zahl effektiv in zwei Schritte unterteilen:

  • Multiplizieren Sie n mit i und Sie erhalten n * i, das n um 90 ° gegen den Uhrzeigersinn gedreht ist
  • Multipliziere erneut mit i und du erhältst -n

Das Tolle ist, dass Sie keinen speziellen Handhabungscode benötigen. Nur multiplizieren mit i macht den Job.

Sie dürfen jedoch keine komplexen Zahlen verwenden. Sie müssen also irgendwie Ihre eigene imaginäre Achse erstellen und dabei einen Teil Ihres Datenbereichs verwenden. Da Sie genau so viele imaginäre (Zwischen-) Werte wie Anfangswerte benötigen, bleibt nur die Hälfte des Datenbereichs übrig.

Ich habe versucht, dies in der folgenden Abbildung zu visualisieren, unter der Annahme signierter 8-Bit-Daten. Sie müssten dies für 32-Bit-Ganzzahlen skalieren. Der zulässige Bereich für das anfängliche n liegt zwischen -64 und +63. Folgendes bewirkt die Funktion für positives n:

  • Wenn n in 0..63 (Anfangsbereich) liegt, addiert der Funktionsaufruf 64 und ordnet n dem Bereich 64..127 (Zwischenbereich) zu.
  • Wenn n in 64..127 (Zwischenbereich) liegt, subtrahiert die Funktion n von 64 und ordnet n dem Bereich 0 ..- 63 zu

Für negatives n verwendet die Funktion den Zwischenbereich -65 ..- 128.

Alt-Text

geschema
quelle
4
@geschema, mit welchem ​​Tool hast du diese schönen Grafiken erstellt?
Jwfearn
10
Entschuldigung, die Frage sagt ausdrücklich keine komplexen Zahlen.
Rui Craveiro
6
@Liran: Ich habe OmniGraffle (nur Mac) verwendet
geschema
39
+1 Ich denke das ist die beste Antwort. Ich glaube nicht, dass die Leute genug lesen, weil sie alle bemerkt haben, dass die Frage besagt, dass komplexe Zahlen nicht verwendet werden können. Ich habe das Ganze gelesen, und Sie haben die Lösung in komplexen Zahlen beschrieben, um die Voraussetzungen für die nicht komplexe Lösung der gestellten Frage zu schaffen. Sehr schön gemacht.
Jrista
1
@jrista Alle Lösungen verwenden eine zweite Dimension, die alles ist, was 'komplexe Zahlen' wirklich sind (die meisten verwenden ungerade gegen gerade und oben verwenden floatvs int). Der '4-Elemente-Ring', den viele Antworten beschreiben, erfordert 4 Zustände, die als 2 Dimensionen mit jeweils 2 Zuständen dargestellt werden können. Das Problem bei dieser Antwort ist, dass sie zusätzlichen Verarbeitungsspeicherplatz benötigt (funktioniert nur für -64..63, benötigt aber -128..127 Speicherplatz) und keine explizite schriftliche Formel angibt!
Kirk Broadhurst
65

Funktioniert außer int.MaxValue und int.MinValue

    public static int f(int x)
    {

        if (x == 0) return 0;

        if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }

bildlich

Rodrick Chapman
quelle
Ich bin mir nicht sicher, warum dies abgelehnt wurde. Für welche Eingaben schlägt es fehl?
Rodrick Chapman
Warum benutzt du nicht die Signum-Funktion?!?
Comonad
1
Das Bild ist wirklich gut. Senden 0an 0und -2147483648an, -2147483648da diese beiden Zahlen Fixpunkte für den Negationsoperator sind x => -x. Folgen Sie für die restlichen Zahlen den Pfeilen im obigen Bild. Wie aus Surdin Antwort und seine Kommentaren klar ist, gibt es zwei Zahlen, in diesem Fall 2147483647und -2147483647mit keinem anderen Paar zu tauschen links mit.
Jeppe Stig Nielsen
Es sieht aus wie ein Smiley - mit vielen Falten
Anshul
48

Die Frage sagt nichts darüber aus, wie der Eingabetyp und der Rückgabewert der Funktion fsein müssen (zumindest nicht so, wie Sie sie dargestellt haben) ...

... genau das, wenn n dann eine 32-Bit-Ganzzahl ist f(f(n)) = -n

Also, wie wäre es mit so etwas

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

Wenn n eine 32-Bit-Ganzzahl ist, ist die Anweisung f(f(n)) == -nwahr.

Offensichtlich könnte dieser Ansatz erweitert werden, um für einen noch größeren Bereich von Zahlen zu arbeiten ...

Daniel LeCheminant
quelle
2
Hinterhältig. Zeichenbegrenzung.
Joe Phillips
2
Ja, ich habe an einem ähnlichen Ansatz gearbeitet. Du hast mich trotzdem geschlagen. +1 :)
Jalf
1
Sehr schlau! Dies kommt der Verwendung komplexer Zahlen sehr nahe (und ist praktisch dasselbe wie). Dies wäre die offensichtliche und ideale Lösung, wird jedoch ausdrücklich nicht zugelassen. Arbeiten außerhalb des zulässigen Zahlenbereichs.
Kirk Broadhurst
48

Für Javascript (oder andere dynamisch typisierte Sprachen) kann die Funktion entweder ein int oder ein Objekt akzeptieren und das andere zurückgeben. dh

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

geben

js> f(f(10))  
-10
js> f(f(-10))
10

Alternativ können Sie das Überladen in einer stark typisierten Sprache verwenden, obwohl dies möglicherweise gegen die Regeln verstößt

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}
Cobbal
quelle
Letzteres bedeutet nicht das Erfordernis einer "a" (singulären) Funktion. :)
Drew
Entfernen Sie die zweite Hälfte der Antwort und dies ist eine korrekte Antwort.
jmucchiello
@ Draw deshalb habe ich erwähnt, dass es die Regeln brechen könnte
Cobbal
2
In JavaScript ist eine Funktion ein Objekt und kann daher einen Status beibehalten.
Nosredna
1
IMO: Funktion f (n) {return n.passed? -n.val: {val: n, übergeben: 1}} ist besser lesbar und kürzer.
SamGoody
46

Abhängig von Ihrer Plattform können Sie in einigen Sprachen den Status in der Funktion beibehalten. VB.Net zum Beispiel:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC, C ++ erlaubte dies ebenfalls. Ich vermute, sie suchen nach einer anderen Lösung.

Eine andere Idee ist, dass Sie, da sie das Ergebnis des ersten Aufrufs der Funktion nicht definiert haben, mit ungerade / Gleichmäßigkeit steuern können, ob das Vorzeichen invertiert werden soll:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

Addiere eins zur Größe aller geraden Zahlen, subtrahiere eins von der Größe aller ungeraden Zahlen. Das Ergebnis von zwei Anrufen hat die gleiche Größe, aber bei dem einen Anruf, bei dem es sich sogar um einen Austausch handelt, tauschen wir das Vorzeichen aus. Es gibt einige Fälle, in denen dies nicht funktioniert (-1, max oder min int), aber es funktioniert viel besser als alles andere, was bisher vorgeschlagen wurde.

Joel Coehoorn
quelle
1
Ich glaube, dass es für MAX_INT funktioniert, da das immer seltsam ist. Es funktioniert nicht für MIN_INT und -1.
Airsource Ltd
9
Es ist keine Funktion, wenn es Nebenwirkungen hat.
Nr.
12
Das mag in der Mathematik zutreffen, ist aber in der Programmierung irrelevant. Die Frage ist also, ob sie nach einer mathematischen Lösung oder einer Programmierlösung suchen. Aber da es für einen Programmierjob ist ...
Ryan Lundy
+1 Ich wollte eins mit in C posten, wobei "static int x" ein FIFO mit Negation der Ausgabe implementiert. Aber das ist nah genug.
Phkahler
2
@nos: Ja, es ist einfach nicht referenziell transparent.
Clark Gaebel
26

Ausnutzen von JavaScript-Ausnahmen.

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}

f(f(0)) => 0

f(f(1)) => -1

Anurag
quelle
Ich bezweifle, dass Ausnahmen wie diese schon einmal verwendet wurden ... :)
NoBugs
+1 Out of the Box Denken. Cool! Aber im Produktionscode würde ich typeof verwenden, nur um sicher zu gehen.
21

Für alle 32-Bit-Werte (mit der Einschränkung, dass -0 -2147483648 ist)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

Grundsätzlich müssen Sie jede -x => x => -x-Schleife mit einer ay => -y => y-Schleife koppeln. Also habe ich die gegenüberliegenden Seiten des gepaart split.

zB Für 4-Bit-Ganzzahlen:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
Eclipse
quelle
21

Eine C ++ - Version, die wahrscheinlich die Regeln etwas verbiegt, aber für alle numerischen Typen (Floats, Ints, Doubles) und sogar Klassentypen funktioniert, die das unäre Minus überladen:

template <class T>
struct f_result
{
  T value;
};

template <class T>
f_result <T> f (T n)
{
  f_result <T> result = {n};
  return result;
}

template <class T>
T f (f_result <T> n)
{
  return -n.value;
}

void main (void)
{
  int n = 45;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
  float p = 3.14f;
  cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}
Skizz
quelle
Gute Idee. Alternativ könnten Sie wahrscheinlich die Struktur verlieren und stattdessen eine Funktion einen Zeiger zurückgeben lassen, die andere Funktion dereferenzieren und negieren.
Imbue
20

x86 asm (AT & T-Stil):

; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
    testl   %edi, %edi
    je  .zero

    movl    %edi, %eax
    movl    $1, %ecx
    movl    %edi, %edx
    andl    $1, %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edx
    subl    %edx, %eax
    imull   %ecx, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    imull   %ecx, %eax
.zero:
    xorl    %eax, %eax
    ret

Code überprüft, alle möglichen 32-Bit-Ganzzahlen übergeben, Fehler mit -2147483647 (Unterlauf).

LiraNuna
quelle
19

Verwendet Globals ... aber so?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}
teeks99
quelle
3
Ich bin mir nicht sicher, ob dies die Absicht des Fragestellers war, aber +1 für "Denken über den Tellerrand hinaus".
Liran Orevi
5
Anstatt bedingt "done = true" zu sagen, sollten Sie immer "done =! Doed" sagen. Auf diese Weise kann Ihre Funktion mehrmals verwendet werden.
Chris Lutz
@Chris, da die Einstellung "done" auf "true" innerhalb eines if (! Doed) -Blocks liegt, entspricht dies "done =! Doed", aber! Doed muss nicht berechnet (oder vom Compiler optimiert werden, wenn es intelligent genug ist). .
nsayer
1
Mein erster Gedanke war auch, dies mit einer globalen Variablen zu lösen, obwohl es sich für diese spezielle Frage wie Betrug anfühlte. Ich würde jedoch argumentieren, dass eine globale variable Lösung angesichts der Spezifikationen in der Frage die beste Lösung ist. Die Verwendung eines Global macht es sehr einfach zu verstehen, was passiert. Ich würde zustimmen, dass ein erledigt! = Fertig besser wäre. Verschieben Sie das einfach außerhalb der if-Klausel.
Alderath
3
Technisch gesehen ist alles, was den Zustand beibehält, keine Funktion, sondern eine Zustandsmaschine. Per Definition gibt eine Funktion immer den gleichen Ausgang für den gleichen Eingang.
Ted Hopp
19

Diese Perl-Lösung funktioniert für Ganzzahlen, Gleitkommazahlen und Zeichenfolgen .

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}

Probieren Sie einige Testdaten aus.

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';

Ausgabe:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar
FMc
quelle
Aber es hält es nicht int. Sie speichern im Wesentlichen globale Variablendaten im int "n" selbst ... außer es ist kein int, sonst könnten Sie das nicht tun. Wenn zum Beispiel nein String wäre, den ich machen könnte, wird 548 zu "First_Time_548" und dann, wenn er das nächste Mal die Funktion durchläuft ... if (Präfix == First_Time_ ") ersetzen Sie" First_Time_ "durch" - "
Albert Renshaw
@ AlbertRenshaw Ich bin mir nicht sicher, woher du diese Ideen hast. (1) Hier sind definitiv keine globalen Variablen beteiligt. (2) Wenn Sie der Funktion ein int geben, erhalten Sie ein int zurück - oder einen Verweis auf ein int, wenn Sie die Funktion ungerade oft aufrufen. (3) Vielleicht am grundlegendsten ist dies Perl . Für alle praktischen Zwecke sind Ints und Strings vollständig austauschbar. Zeichenfolgen, die wie Zahlen aussehen, funktionieren in den meisten Kontexten perfekt als Zahlen, und Zahlen werden bei Bedarf gerne Zeichenfolgen.
FMc
Tut mir leid, ich weiß nicht viel Perl. Es schien, als würden Sie ein globales Array verwenden, haha
Albert Renshaw,
18

Niemand hat jemals gesagt, dass f (x) der gleiche Typ sein muss.

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2
Wählen Sie Z.
quelle
16

Ich versuche eigentlich nicht, eine Lösung für das Problem selbst zu finden, habe aber einige Kommentare, da die Frage besagt, dass dieses Problem Teil eines (Job-?) Interviews war:

  • Ich würde zuerst fragen: "Warum sollte eine solche Funktion benötigt werden? Was ist das größere Problem, zu dem dies gehört?" anstatt zu versuchen, das tatsächlich gestellte Problem vor Ort zu lösen. Dies zeigt, wie ich denke und wie ich solche Probleme angehe. Wer weiß? Dies könnte sogar der eigentliche Grund sein, warum die Frage überhaupt in einem Interview gestellt wird. Wenn die Antwort lautet: "Macht nichts, nehmen Sie an, dass es benötigt wird, und zeigen Sie mir, wie Sie diese Funktion gestalten würden." Ich würde dann weiter machen.
  • Dann würde ich den C # -Testfallcode schreiben, den ich verwenden würde (die offensichtliche: Schleife von int.MinValuebis int.MaxValue, und für jeden nAufruf in diesem Bereich f(f(n))und Überprüfung des Ergebnisses -n) und sagen, dass ich dann Test Driven Development verwenden würde, um zu einer solchen Funktion zu gelangen.
  • Nur wenn der Interviewer weiterhin nach mir fragt, um das gestellte Problem zu lösen, würde ich tatsächlich versuchen, während des Interviews selbst Pseudocode zu kritzeln, um zu versuchen, eine Antwort zu finden. Ich glaube jedoch nicht wirklich, dass ich springen würde, um den Job anzunehmen, wenn der Interviewer einen Hinweis darauf geben würde, wie das Unternehmen ist ...

Oh, diese Antwort geht davon aus, dass das Interview für eine C # -Programmierposition war. Wäre natürlich eine dumme Antwort, wenn das Interview für eine mathematische Position wäre. ;-);

peSHIr
quelle
7
Sie haben Glück, dass sie nach 32 int gefragt haben, wenn es 64 Bit war, wird das Interview nie fortgesetzt, nachdem Sie die Tests durchgeführt haben ;-)
alex2k8
In der Tat, wenn ich überhaupt zu einem Punkt kommen würde, um diesen Test tatsächlich zu schreiben und ihn während eines Interviews auszuführen. ;-) Mein Punkt: Ich würde versuchen, in einem Interview überhaupt nicht an diesen Punkt zu gelangen. Programmieren ist meiner Meinung nach eher eine "Denkweise" als "wie schreibt er Codezeilen".
PeSHIr
7
Befolgen Sie diesen Rat nicht in einem tatsächlichen Interview. Der Interviewer erwartet, dass Sie die Frage tatsächlich beantworten. Das Hinterfragen der Relevanz der Frage bringt Ihnen nichts, kann aber den Interviewer ärgern. Das Entwerfen eines trivialen Tests bringt Sie der Antwort keinen Schritt näher und kann im Interview nicht ausgeführt werden. Wenn Sie zusätzliche Informationen (32 Bit) erhalten, versuchen Sie herauszufinden, wie dies nützlich sein kann.
Stefan Haustein
Ein Interviewer, der sich ärgert, wenn ich nach weiteren Informationen frage (und möglicherweise die Relevanz seiner Frage im Prozess in Frage stelle), ist kein Interviewer, für den ich unbedingt arbeiten möchte. Also werde ich in Interviews immer wieder solche Fragen stellen. Wenn sie es nicht mögen, werde ich wahrscheinlich das Interview beenden, um nicht länger unsere Zeit zu verschwenden. Ich mag die Einstellung "Ich habe nur Befehle befolgt" nicht. Machst du..?
PeSHIr
16

Ich würde Sie die 2 wichtigsten Bits ändern.

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

Wie Sie sehen können, ist es nur eine Ergänzung, bei der das getragene Bit weggelassen wird.

Wie bin ich zur Antwort gekommen? Mein erster Gedanke war nur ein Bedürfnis nach Symmetrie. 4 Umdrehungen, um dorthin zurückzukehren, wo ich angefangen habe. Zuerst dachte ich, das ist 2-Bit-Gray-Code. Dann dachte ich eigentlich, Standard Binär ist genug.

Eipipuz
quelle
Das Problem bei diesem Ansatz ist, dass er nicht mit negativen Zahlen mit zwei Komplimenten funktioniert (was jede moderne CPU verwendet). Deshalb habe ich meine identische Antwort gelöscht.
Tamas Czinege
Die Frage gab 32-Bit-Ganzzahlen mit Vorzeichen an. Diese Lösung funktioniert nicht für Zwei-Komplement- oder Ein-Komplement-Darstellungen der 32-Bit-Ganzzahlen mit Vorzeichen. Es funktioniert nur für Vorzeichen- und Größenrepräsentationen, die in modernen Computern (außer Gleitkommazahlen) sehr selten sind.
Jeffrey L Whitledge
1
@ DrJokepu - Wow, nach sechs Monaten - Fluch!
Jeffrey L Whitledge
Müssen Sie die Zahlen nicht einfach in eine Vorzeichen- und Größenrepräsentation innerhalb der Funktion konvertieren, die Transformation durchführen und dann wieder in die native Ganzzahldarstellung konvertieren, bevor Sie sie zurückgeben?
Bill Michell
Ich mag es, dass Sie im Grunde komplexe Zahlen implementiert haben, indem Sie ein imaginäres Bit eingeführt haben :)
jabirali
16

Hier ist eine Lösung, die von der Anforderung inspiriert ist oder behauptet, dass komplexe Zahlen nicht zur Lösung dieses Problems verwendet werden können.

Das Multiplizieren mit der Quadratwurzel von -1 ist eine Idee, die nur zu scheitern scheint, weil -1 keine Quadratwurzel über den ganzen Zahlen hat. Aber mit einem Programm wie mathematica herumzuspielen gibt zum Beispiel die Gleichung

(1849436465 2 + 1) mod (2 32 -3) = 0.

und das ist fast so gut wie eine Quadratwurzel von -1. Das Ergebnis der Funktion muss eine vorzeichenbehaftete Ganzzahl sein. Daher werde ich eine modifizierte Modulo-Operation mods (x, n) verwenden, die die Ganzzahl y kongruent zu x modulo n zurückgibt, die am nächsten bei 0 liegt. Nur sehr wenige Programmiersprachen haben eine erfolgreiche Modulo-Operation, aber sie kann leicht definiert werden . ZB in Python ist es:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

Mit der obigen Gleichung kann das Problem nun wie folgt gelöst werden

def f(x):
    return mods(x*1849436465, 2**32-3)

Dies ist f(f(x)) = -xfür alle ganzen Zahlen im Bereich ausreichend . Die Ergebnisse von liegen ebenfalls in diesem Bereich, aber für die Berechnung wären natürlich 64-Bit-Ganzzahlen erforderlich.[-231-2, 231-2]f(x)

Accipitridae
quelle
13

C # für einen Bereich von 2 ^ 32 - 1 Zahlen, alle int32 Zahlen außer (Int32.MinValue)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));

    Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647

Drucke:

2147483647
3
2
1
0
-1
-2
-3
-2147483647
Pop Catalin
quelle
Dies funktioniert auch nicht für f (0), das ist 1073741824. f (1073741824) = 0. f (f (1073741824)) = 1073741824
Dinah
Sie können im Allgemeinen beweisen, dass für einen Ganzzahltyp mit zwei Komplementen beliebiger Bitgröße die Funktion für mindestens zwei Eingabewerte nicht funktionieren muss .
lockerer
12

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. 0 muss jedoch Teil eines Zyklus der Größe 1 sein, da sonst 0->x->0->x != -x. Da 0 alleine ist, müssen 3 andere Werte in unserem Bereich (deren Größe ein Vielfaches von 4 ist) nicht in einem richtigen Zyklus mit 4 Elementen vorhanden sein.

Ich habe mich für diese zusätzlichen seltsame Werte zu sein MIN_INT, MAX_INTund MIN_INT+1. Darüber hinaus MIN_INT+1wird zu MAX_INTordnen, aber dort stecken bleiben und nicht zurück zuordnen. Ich denke, dies ist der beste Kompromiss, da er die nette Eigenschaft hat, dass nur die Extremwerte nicht richtig funktionieren. Es bedeutet auch, dass es für alle BigInts funktionieren würde.

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)
Strilanc
quelle
12

Niemand sagte, es müsse staatenlos sein.

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

Betrug, aber nicht so viel wie viele Beispiele. Noch schlimmer wäre es, den Stapel zu durchsuchen, um zu sehen, ob die Adresse Ihres Anrufers & f ist, aber dies wird portabler (obwohl nicht threadsicher ... die thread-sichere Version würde TLS verwenden). Noch böser:

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

Natürlich funktioniert keines von beiden für den Fall von MIN_INT32 zu gut, aber es gibt wenig, was Sie dagegen tun können, es sei denn, Sie dürfen einen breiteren Typ zurückgeben.

Christopher Smith
quelle
Sie können es 'aktualisieren', um nach der Adresse zu fragen (ja, Sie müssen es durch ref \ als Zeiger erhalten) - in C zum Beispiel: int f (int & n) {static int * addr = & n; if (addr == & n) {return -n; } return n; }
IUnknownPointer
11

Ich könnte mir vorstellen, dass die Verwendung des 31. Bits als imaginäres ( i ) Bit ein Ansatz wäre, der die Hälfte des gesamten Bereichs unterstützt.

llamaoo7
quelle
Dies wäre komplexer, aber nicht effektiver als die derzeit beste Antwort
1800 INFORMATION
1
@ 1800 INFORMATION: Andererseits ist die Domäne [-2 ^ 30 + 1, 2 ^ 30-1] zusammenhängend, was aus mathematischer Sicht ansprechender ist.
Jochen Walter
10

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
}
MartinStettner
quelle
10

Das Problem gibt "32-Bit-Ganzzahlen mit Vorzeichen" an, gibt jedoch nicht an, ob es sich um Zweierkomplement oder Einkomplement handelt .

Wenn Sie Einsen-Komplement verwenden, treten alle 2 ^ 32-Werte in Zyklen der Länge vier auf - Sie benötigen keinen Sonderfall für Null und Sie benötigen auch keine Bedingungen.

In C:

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

Das funktioniert von

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

Nach zwei Durchgängen haben wir die bitweise Umkehrung des ursprünglichen Wertes. Was in der Ein-Komplement-Darstellung der Negation entspricht.

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)
finnw
quelle
1
Was ist mit der Bytereihenfolge über verschiedene Architekturen hinweg?
Steven
1
Die gesamte Arithmetik ist 32-Bit. Ich manipuliere keine einzelnen Bytes, daher wirkt sich die Bytereihenfolge nicht darauf aus.
Finnw
Das klingt ziemlich nah. Sie können davon ausgehen, dass die Eingabe 2-Komplement ist. Sie konvertieren also in die Vorzeichenbitdarstellung. Abhängig vom letzten Bit drehen Sie nun das erste und das letzte Bit oder nur das letzte Bit um. Grundsätzlich negieren Sie nur gerade Zahlen und wechseln die ganze Zeit gerade / ungerade. So kehren Sie nach 2 Anrufen von ungerade zu ungerade und gerade zu gerade zurück. Am Ende konvertieren Sie zurück zu 2-Komplement. Habe den Code dafür irgendwo unten gepostet.
Stefan Haustein
9

: D.

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}
Drew
quelle
5
Könnte Ihnen auch eine Diskussion darüber bringen, warum globale Variablen schlecht sind, wenn sie Sie nicht genau dort aus dem Interview werfen!
Palswim
9
return x ^ ((x%2) ? 1 : -INT_MAX);
Mike Meehan
quelle
7

Ich möchte meinen Standpunkt zu diesem interessanten Problem als Mathematiker teilen. Ich denke, ich habe die effizienteste Lösung.

Wenn ich mich richtig erinnere, negieren Sie eine vorzeichenbehaftete 32-Bit-Ganzzahl, indem Sie nur das erste Bit umdrehen. Wenn beispielsweise n = 1001 1101 1110 1011 1110 0000 1110 1010 ist, dann ist -n = 0001 1101 1110 1011 1110 0000 1110 1010.

Wie definieren wir also eine Funktion f, die eine vorzeichenbehaftete 32-Bit-Ganzzahl verwendet und eine weitere vorzeichenbehaftete 32-Bit-Ganzzahl mit der Eigenschaft zurückgibt, dass die zweimalige Verwendung von f dasselbe ist wie das Umdrehen des ersten Bits?

Lassen Sie mich die Frage umformulieren, ohne arithmetische Konzepte wie ganze Zahlen zu erwähnen.

Wie definieren wir eine Funktion f, die eine Folge von Nullen und Einsen der Länge 32 annimmt und eine Folge von Nullen und Einsen derselben Länge zurückgibt, mit der Eigenschaft, dass das zweimalige Nehmen von f gleich dem Umdrehen des ersten Bits ist?

Beobachtung: Wenn Sie die obige Frage für 32-Bit-Fälle beantworten können, können Sie auch für 64-Bit-Fälle, 100-Bit-Fälle usw. antworten. Sie wenden f einfach auf die ersten 32-Bit-Fälle an.

Wenn Sie nun die Frage für einen 2-Bit-Fall beantworten können, Voila!

Und ja, es stellt sich heraus, dass das Ändern der ersten 2 Bits ausreicht.

Hier ist der Pseudocode

1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.

Anmerkung: Schritt 2 und Schritt 3 zusammen können als (a, b) -> (-b, a) zusammengefasst werden. Kommt mir bekannt vor? Das sollte Sie an die 90-Grad-Drehung der Ebene und die Multiplikation mit der Quadratwurzel von -1 erinnern.

Wenn ich nur den Pseudocode alleine ohne das lange Vorspiel präsentieren würde, würde es wie ein Kaninchen aus dem Hut scheinen, ich wollte erklären, wie ich zu der Lösung kam.

Yoo
quelle
6
Ja, das ist ein interessantes Problem. Sie kennen Ihre Mathematik. Dies ist jedoch ein Informatikproblem. Sie müssen also Computer studieren. Die Darstellung der Vorzeichengröße ist zulässig, kam jedoch vor etwa 60 Jahren aus der Mode. 2er-Komplement ist am beliebtesten.
Windows-Programmierer
5
Hier ist, was Ihre Funktion mit den beiden Bits macht, wenn sie zweimal angewendet wird: (a, b) -> (-b, a) -> (-a, -b). Aber wir versuchen, zu (-a, b) zu gelangen, nicht zu (-a, -b).
Buti-Oxa
@ Buti-Oxa, du hast recht. Die Zwei-Bit-Operation sollte wie folgt aussehen: 00 -> 01 -> 10 -> 11 -> 00. Aber dann geht mein Algorithmus von einer Darstellung der Vorzeichengröße aus, die jetzt unpopulär ist, wie der Windows-Programmierer sagte, und ich denke, mein Algorithmus ist von geringem Nutzen .
Yoo
Kann er die Schritte also nicht einfach zweimal statt einmal ausführen?
Nosredna
4
buti-oxa ist völlig richtig: Die Funktion dreht nicht einmal das erste Bit nach zwei Aufrufen, sondern die ersten beiden Bits. Das Umdrehen aller Bits ist näher an dem, was das 2er-Komplement bewirkt, aber es ist nicht genau richtig.
Redtuna