[Math] Designfunktion f (f (n)) == -n


Answers

Du hast nicht gesagt, welche Art von Sprache sie erwarteten ... Hier ist eine statische Lösung (Haskell). Es ist im Grunde mit den 2 wichtigsten Bits rum:

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

Es ist viel einfacher in einer dynamischen Sprache (Python). Überprüfen Sie, 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()
Question

Eine Frage, die ich bei meinem letzten Interview bekam:

Entwerfen Sie eine Funktion f , so dass:

f(f(n)) == -n

Wobei n eine 32-Bit- Ganzzahl mit Vorzeichen ist ; Sie können keine komplexe Zahlenarithmetik verwenden.

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

Irgendwelche Ideen?




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

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;
}



Nobody said it had to be stateless.

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

Cheating, but not as much as a lot of the examples. Even more evil would be to peek up the stack to see if your caller's address is &f, but this is going to be more portable (although not thread safe... the thread-safe version would use TLS). Even more evil:

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

Of course, neither of these works too well for the case of MIN_INT32, but there is precious little you can do about that unless you are allowed to return a wider type.




Dies gilt für alle negativen Zahlen.

    f(n) = abs(n)

Weil es eine weitere negative Zahl gibt als positive Zahlen für zwei komplementäre ganze Zahlen, gilt f(n) = abs(n) für einen weiteren Fall als f(n) = n > 0 ? -n : n f(n) = n > 0 ? -n : n Lösung, die dieselbe ist wie f(n) = -abs(n) . Hast du eins ...: D

AKTUALISIEREN

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

Ich dachte darüber nach, auch mod 2-Informationen zu verwenden, kam aber zu dem Schluss, dass es nicht funktioniert ... zu früh. Wenn es richtig gemacht wird, wird es für alle Zahlen außer Int.Min da 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 das Folgende:

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

Damit es für alle Werte funktioniert, müssen Sie Math.Abs() durch (n > 0) ? +n : -n ersetzen (n > 0) ? +n : -n (n > 0) ? +n : -n und schließt die Berechnung in einen unchecked Block ein. Dann bekommst du sogar Int.Min als ungeprüfte Negation zu sich selbst Int.Min .

AKTUALISIEREN

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

Fangen wir gleich am Anfang an. Die Funktion f wird wiederholt auf einen gegebenen Wert n angewendet, der eine Folge von Werten ergibt.

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

Die Frage erfordert f(f(n)) = -n , das heißt, zwei aufeinanderfolgende Anwendungen von f negieren das Argument. Zwei weitere Anwendungen von f - insgesamt vier - negieren das Argument erneut, was wiederum zu n .

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

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

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

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

Eine von vielen Lösungen, um einen solchen Zyklus zu konstruieren, ist das Folgende, beginnend mit n.

 n                 => negate and subtract one
-n - 1 = -(n + 1)  => add one
-n                 => negate and add one
 n + 1             => subtract one
 n

Ein konkretes Beispiel für einen solchen Zyklus ist +1 => -2 => -1 => +2 => +1 . Wir sind fast fertig. Wenn man bedenkt, dass der konstruierte Zyklus eine ungerade positive Zahl, seinen geraden Nachfolger und beide Zahlen enthält, können wir die ganzen Zahlen in viele solcher Zyklen aufteilen ( 2^32 ist ein Vielfaches von vier) und eine Funktion gefunden haben, die die Bedingungen erfüllt.

Aber wir haben ein Problem mit Null. Der Zyklus muss 0 => x => 0 da Null für sich selbst negiert wird. Und weil der Zyklus bereits 0 => x angibt, folgt 0 => x => 0 => x . Dies ist nur ein Zyklus der Länge zwei und x wird nach zwei Anwendungen in sich selbst umgewandelt, nicht in -x . Glücklicherweise gibt es einen Fall, der das Problem löst. Wenn X gleich Null ist, erhalten wir einen Zyklus der Länge eins, der nur Null enthält, und wir haben dieses Problem gelöst, indem wir schließen, dass Null ein fester Punkt von f .

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

Ich werde den verbleibenden Teil der Lösung mit dem kleineren Satz von 3 Bit signierten Itergern von -4 bis +3 erklären. Wir sind mit Null fertig. Wir haben einen vollständigen Zyklus +1 => -2 => -1 => +2 => +1 . Lasst uns nun den Zyklus ab +3 konstruieren.

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

Das Problem, das auftritt, ist, dass +4 nicht als 3-Bit-Ganzzahl darstellbar ist. Wir würden +4 indem wir -3 bis +3 negieren - was immer noch eine gültige 3-Bit-Ganzzahl ist - aber dann, wenn wir eins zu +3 (binär 011 ) addieren, ergibt dies 100 Binärwerte. Interpretiert als vorzeichenlose Ganzzahl ist es +4 aber wir müssen es als vorzeichenbehaftete Ganzzahl -4 interpretieren. Also eigentlich -4 für dieses Beispiel oder Int.MinValue im allgemeinen Fall ein zweiter Fixpunkt der ganzzahligen arithmetischen Negation - 0 und Int.MinValue sind auf sich selbst abgebildet. Also ist der Zyklus eigentlich wie folgt.

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

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

Also haben wir eine Funktion konstruiert, die für alle Ganzzahlen außer eins 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 ganzen ganzzahligen Bereich bis zu vier Werten abdecken. Die verbleibenden Werte sind die beiden Fixpunkte 0 und Int.MinValue , die auf sie selbst abgebildet werden müssen, und zwei beliebige Ganzzahlen x und -x , die durch zwei Funktionsanwendungen miteinander Int.MinValue müssen.

Um x nach -x und umgekehrt abzubilden, müssen sie einen vierfachen Zyklus bilden und sie müssen sich an gegenüberliegenden Ecken dieses Zyklus befinden. Int.MinValue müssen 0 und Int.MinValue auch an gegenüberliegenden Ecken liegen. Dies wird korrekt x und -x Int.MinValue aber die zwei Fixpunkte 0 und Int.MinValue nach zwei Funktionsanwendungen Int.MinValue und uns mit zwei Int.MinValue Eingaben Int.MinValue . Es ist also nicht möglich, eine Funktion zu erstellen, die für alle Werte funktioniert, aber wir haben eine Funktion, die für alle Werte außer einem funktioniert, und das ist das Beste, was wir erreichen können.




Verwendet Globals ... aber so?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}



C# for a range of 2^32 - 1 numbers, all int32 numbers except (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



Ausnutzen von JavaScript-Ausnahmen.

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

f(f(0)) => 0

f(f(1)) => -1




I would you change the 2 most significant bits.

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

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

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

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

As you can see, it's just an addition, leaving out the carried bit.

How did I got to the answer? My first thought was just a need for symmetry. 4 turns to get back where I started. At first I thought, that's 2bits Gray code. Then I thought actually standard binary is enough.




Niemand hat je 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



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));
    }




works for 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
}



Dank Überladen 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));
}



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önnten Sie das Überladen in einer stark typisierten Sprache verwenden, obwohl dies die Regeln sprengen könnte

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}



I'd like to share my point of view on this interesting problem as a mathematician. I think I have the most efficient solution.

If I remember correctly, you negate a signed 32-bit integer by just flipping the first bit. For example, if n = 1001 1101 1110 1011 1110 0000 1110 1010, then -n = 0001 1101 1110 1011 1110 0000 1110 1010.

So how do we define a function f that takes a signed 32-bit integer and returns another signed 32-bit integer with the property that taking f twice is the same as flipping the first bit?

Let me rephrase the question without mentioning arithmetic concepts like integers.

How do we define a function f that takes a sequence of zeros and ones of length 32 and returns a sequence of zeros and ones of the same length, with the property that taking f twice is the same as flipping the first bit?

Observation: If you can answer the above question for 32 bit case, then you can also answer for 64 bit case, 100 bit case, etc. You just apply f to the first 32 bit.

Now if you can answer the question for 2 bit case, Voila!

And yes it turns out that changing the first 2 bits is enough.

Here's the pseudo-code

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.

Remark: The step 2 and the step 3 together can be summerised as (a,b) --> (-b, a). Looks familiar? That should remind you of the 90 degree rotation of the plane and the multiplication by the squar root of -1.

If I just presented the pseudo-code alone without the long prelude, it would seem like a rabbit out of the hat, I wanted to explain how I got the solution.




: D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}