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

Ausnutzung von JavaScript-Ausnahmen.

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

f(f(0)) => 0

f(f(1)) => -1

Answer 2

Für alle 32-Bit-Werte (mit dem Vorbehalt, dass -0 gleich -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);
}

Im Grunde müssen Sie jede -x => x => -x-Schleife mit einer y => -y => y-Schleife verbinden. Ich habe also die gegenüberliegenden Seiten der Schleife split .

z.B. 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

Answer 3

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

Answer 4

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 geprüft, alle möglichen 32bit Integer übergeben, Fehler bei -2147483647 (Unterlauf).

Answer 5

Verwendet Globals...aber so?

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