Funkcja projektowania f (f (n)) == -n

Pytanie, które otrzymałem podczas mojej ostatniej rozmowy:

Zaprojektuj funkcję ftaką, aby:

f(f(n)) == -n

Gdzie njest 32-bitowa liczba całkowita ze znakiem ; nie można używać arytmetyki liczb zespolonych.

Jeśli nie możesz zaprojektować takiej funkcji dla całego zakresu liczb, zaprojektuj ją dla największego możliwego zakresu.

Jakieś pomysły?

Co powiesz na:

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

W Pythonie:

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 automatycznie promuje liczby całkowite do dowolnych długości. W innych językach przepełni się największa dodatnia liczba całkowita, więc będzie działać dla wszystkich liczb całkowitych oprócz tej.

Aby działało dla liczb rzeczywistych, musisz zastąpić nw (-1) ⁿ przez { ceiling(n) if n>0; floor(n) if n<0 }.

W języku C # (działa dla każdego podwójnego, z wyjątkiem sytuacji przepełnienia):

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

Nie powiedziałeś, jakiego języka się spodziewają ... Oto rozwiązanie statyczne (Haskell). Zasadniczo zadziera z 2 najbardziej znaczącymi bitami:

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

Jest to o wiele łatwiejsze w dynamicznym języku (Python). Po prostu sprawdź, czy argument jest liczbą X i zwróć lambda, która zwraca -X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

Oto dowód, dlaczego taka funkcja nie może istnieć dla wszystkich liczb, jeśli nie używa dodatkowych informacji (z wyjątkiem 32 bitów int):

Musimy mieć f (0) = 0. (Dowód: Załóżmy, że f (0) = x. Następnie f (x) = f (f (0)) = -0 = 0. Teraz, -x = f (f (x )) = f (0) = x, co oznacza, że ​​x = 0.)

Ponadto, dla każdego xi y, przypuśćmy f(x) = y. Chcemy f(y) = -xwięc. I f(f(y)) = -y => f(-x) = -y… Podsumowując: jeśli f(x) = y, to f(-x) = -y, i f(y) = -x, i f(-y) = x.

Musimy więc podzielić wszystkie liczby całkowite oprócz 0 na zestawy 4, ale mamy nieparzystą liczbę takich liczb całkowitych; nie tylko to, że jeśli usuniemy liczbę całkowitą, która nie ma dodatniego odpowiednika, nadal będziemy mieć 2 (mod4) liczby.

Jeśli usuniemy 2 maksymalne liczby, które pozostały (według wartości abs), możemy uzyskać funkcję:

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

Oczywiście inną opcją jest nieprzestrzeganie 0 i otrzymanie 2 liczb, które usunęliśmy jako bonus. (Ale to tylko głupie, jeśli.)

Dzięki przeciążeniu w 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));
}

Lub możesz nadużyć preprocesora:

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

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

Dotyczy to wszystkich liczb ujemnych.

    f (n) = abs (n)

Ponieważ istnieje jeszcze jedna liczba ujemna niż liczba dodatnia dla dwóch liczb całkowitych uzupełniających, f(n) = abs(n) jest ważna dla jednego przypadku więcej niż f(n) = n > 0 ? -n : nrozwiązanie, które jest takie samo jak f(n) = -abs(n). Mam cię po jednym ...: D

AKTUALIZACJA

Nie, nie dotyczy to więcej niż jednego przypadku, jak właśnie rozpoznałem w komentarzu litba ... abs(Int.Min) po prostu się przepełni ...

Myślałem też o użyciu informacji o modzie 2, ale doszedłem do wniosku, że to nie działa ... na początku. Jeśli zrobisz to poprawnie, zadziała dla wszystkich liczb opróczInt.Min tego, że się przepełni.

AKTUALIZACJA

Bawiłem się nim przez pewien czas, szukając ładnej sztuczki manipulacji, ale nie mogłem znaleźć ładnego jednoliniowego, podczas gdy rozwiązanie mod 2 pasuje do jednego.

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

W języku C # wygląda to następująco:

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

Aby to działa dla wszystkich wartości, trzeba wymienić Math.Abs()z (n > 0) ? +n : -nobejmują obliczenia w uncheckedbloku. Następnie zostajesz nawet Int.Minzmapowany do siebie, tak jak robi to niesprawdzona negacja.

AKTUALIZACJA

Zainspirowany inną odpowiedzią wyjaśnię, jak działa ta funkcja i jak ją zbudować.

Zacznijmy od samego początku. Funkcja fjest wielokrotnie stosowana do danej wartościn dając ciąg wartości.

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

Pytanie wymaga f(f(n)) = -n, aby były to dwa kolejne zastosowania fnegacji argumentu. Dwa kolejne zastosowania f- w sumie cztery - negują ponownie ten argumentn ponownie.

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

Teraz jest oczywisty cykl długości czterech. Podstawiając x = f(n)i zauważając, że otrzymane równanie f(f(f(n))) = f(f(x)) = -xzachowuje, otrzymujemy następujące wyniki.

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

Otrzymujemy więc cykl długości cztery z dwiema liczbami i dwie liczby zanegowane. Jeśli wyobrażasz sobie cykl jako prostokąt, zanegowane wartości znajdują się w przeciwległych rogach.

Jednym z wielu rozwiązań pozwalających skonstruować taki cykl jest początek od n.

 n => neguj i odejmij jeden
-n - 1 = - (n + 1) => dodaj jeden
-n => zaneguj i dodaj jeden
 n + 1 => odejmij jeden
 n

Konkretnym przykładem takiego cyklu jest +1 => -2 => -1 => +2 => +1. Prawie skończyliśmy. Zwracając uwagę, że skonstruowany cykl zawiera nieparzystą liczbę dodatnią, jego parzysty następca i obie liczby negują, możemy z łatwością podzielić liczby całkowite na wiele takich cykli ( 2^32jest wielokrotnością czterech) i znaleźliśmy funkcję, która spełnia warunki.

Ale mamy problem ze zerem. Cykl musi zawierać, 0 => x => 0ponieważ zero jest negowane samo w sobie. A ponieważ cykl stwierdza, 0 => xże już następuje 0 => x => 0 => x. Jest to tylko cykl długości dwóch i xzamienia się w siebie po dwóch aplikacjach, a nie w -x. Na szczęście jest jeden przypadek, który rozwiązuje problem. Jeśli Xjest równy zeru, otrzymujemy cykl długości zawierający tylko zero i rozwiązaliśmy ten problem, stwierdzając, że zero jest stałym punktem f.

Gotowy? Prawie. Mamy 2^32liczby, zero to stały punkt pozostawiający 2^32 - 1liczby i musimy podzielić tę liczbę na cykle czterech liczb. Złe, że 2^32 - 1nie jest wielokrotnością czterech - pozostaną trzy liczby nie w żadnym cyklu długości czterech.

Wyjaśnię pozostałą część rozwiązania przy użyciu mniejszego zestawu 3-bitowych liczb całkowitych ze znakiem od -4do +3. Skończyliśmy z zerem. Mamy jeden pełny cykl +1 => -2 => -1 => +2 => +1. Teraz skonstruujmy cykl zaczynając od +3.

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

Powstaje problem polegający na tym, że +4nie jest reprezentowana jako 3-bitowa liczba całkowita. Chcielibyśmy uzyskać +4poprzez zanegowanie -3się +3- co jest jeszcze ważne całkowitą 3 bit - ale potem dodając jeden do +3(binarnie 011) daje 100binarny. Jest interpretowany jako liczba całkowita bez znaku, +4ale musimy interpretować go jako liczbę całkowitą ze znakiem -4. Tak więc w rzeczywistości -4w tym przykładzie lub Int.MinValuew ogólnym przypadku jest drugim stałym punktem całkowitej negacji arytmetycznej - 0 i Int.MinValuesą one odwzorowane na nich samych. Tak więc cykl jest następujący.

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

Jest to cykl długości dwóch i dodatkowo +3wchodzi w cykl poprzez -4. W konsekwencji -4jest poprawnie odwzorowany na siebie po dwóch aplikacjach funkcyjnych, +3jest poprawnie odwzorowany na -3dwóch aplikacjach funkcyjnych, ale -3błędnie jest odwzorowany na sobie po dwóch aplikacjach funkcyjnych.

Stworzyliśmy więc funkcję, która działa dla wszystkich liczb całkowitych oprócz jednej. Czy możemy zrobić lepiej? Nie, nie możemy. Dlaczego? Musimy skonstruować cykle o długości czterech i jesteśmy w stanie objąć cały zakres liczb całkowitych do czterech wartości. Pozostałe wartości są dwa punkty stałe 0i Int.MinValuektóre muszą być przypisane do siebie i dwóch dowolnych liczb całkowitych xi -xktóre muszą być przypisane do siebie przez dwa wnioski funkcyjnych.

Mapować xdo -xi odwrotnie muszą tworzyć cztery cyklu i muszą być umieszczone na przeciwległych rogach tego cyklu. W konsekwencji 0i Int.MinValuemuszą znajdować się również w przeciwległych rogach. To będzie poprawnie map xi -xjednak zamienić dwa punkty stałe 0i Int.MinValuepo dwóch zastosowaniach funkcyjnych i zostawić nas z dwoma wejściami upadających. Dlatego nie jest możliwe zbudowanie funkcji, która działa dla wszystkich wartości, ale mamy taką, która działa dla wszystkich wartości oprócz jednej i jest to najlepsze, co możemy osiągnąć.

Używając liczb zespolonych, możesz skutecznie podzielić zadanie negowania liczby na dwa etapy:

• pomnóż n przez i, a otrzymasz n * i, który jest n obrócony o 90 ° przeciwnie do ruchu wskazówek zegara
• pomnóż ponownie przez i, a otrzymasz -n

Wspaniałą rzeczą jest to, że nie potrzebujesz specjalnego kodu obsługi. Po prostu pomnożenie przez i wykonuje pracę.

Ale nie wolno ci używać liczb zespolonych. Musisz więc jakoś stworzyć własną wyobrażoną oś, wykorzystując część swojego zakresu danych. Ponieważ potrzebujesz dokładnie tyle wyimaginowanych (pośrednich) wartości, co wartości początkowe, pozostaje Ci tylko połowa zakresu danych.

Próbowałem to wyobrazić na poniższym rysunku, zakładając podpisane dane 8-bitowe. Trzeba to skalować dla 32-bitowych liczb całkowitych. Dopuszczalny zakres dla początkowego n wynosi od -64 do +63. Oto, co funkcja robi dla dodatniego n:

• Jeśli n jest w zakresie 0..63 (zakres początkowy), wywołanie funkcji dodaje wartość 64, odwzorowując n na zakres 64..127 (zakres pośredni)
• Jeśli n jest w zakresie 64..127 (zakres pośredni), funkcja odejmuje n od 64, odwzorowując n na zakres 0 ..- 63

Dla ujemnego n funkcja wykorzystuje zakres pośredni -65 ..- 128.

Działa z wyjątkiem int.MaxValue i 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));
    }

Pytanie nie mówi nic o tym, jaki fmusi być typ wejścia i zwracana wartość funkcji (przynajmniej nie tak, jak to przedstawiłeś) ...

... tylko wtedy, gdy n jest 32-bitową liczbą całkowitą f(f(n)) = -n

A co powiesz na coś takiego

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

Jeśli n jest 32-bitową liczbą całkowitą, wówczas instrukcja f(f(n)) == -nbędzie prawdziwa.

Oczywiście to podejście można rozszerzyć na jeszcze szerszy zakres liczb ...

dla javascript (lub innych języków dynamicznie wpisywanych) możesz mieć funkcję akceptującą int lub obiekt i zwracającą drugą. to znaczy

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

dający

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

alternatywnie możesz użyć przeciążenia w silnie typowanym języku, chociaż może to złamać zasady tj

int f(long n) {
    return n;
}

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

W zależności od platformy niektóre języki umożliwiają zachowanie stanu funkcji. VB.Net, na przykład:

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

    Return n * flag
End Function

IIRC, C ++ również na to pozwoliły. Podejrzewam jednak, że szukają innego rozwiązania.

Innym pomysłem jest to, że skoro nie zdefiniowali wyniku pierwszego wywołania funkcji, można użyć nieparzystości / parzystości do kontrolowania, czy odwrócić znak:

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

Dodaj jeden do wielkości wszystkich liczb parzystych, odejmij jeden od wielkości wszystkich liczb nieparzystych. Wynik dwóch wezwań ma taką samą wielkość, ale jedno wywołanie, w którym nawet zamieniamy znak. W niektórych przypadkach to nie zadziała (-1, maks. Lub min. Int), ale działa o wiele lepiej niż cokolwiek innego sugerowanego do tej pory.

Wykorzystywanie wyjątków JavaScript.

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

f(f(0)) => 0

f(f(1)) => -1

Dla wszystkich wartości 32-bitowych (z zastrzeżeniem, że -0 wynosi -2147483648)

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

Zasadniczo musisz sparować każdą pętlę -x => x => -x z pętlą ay => -y => y. Więc sparowałem przeciwne strony split.

np. dla 4-bitowych liczb całkowitych:

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

Wersja C ++, prawdopodobnie nieco zginająca reguły, ale działa dla wszystkich typów liczbowych (liczba zmiennoprzecinkowa, liczba całkowita, liczba podwójna), a nawet typów klas, które przeciążają jednoargumentowy minus:

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

x86 asm (styl AT&T):

; 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

Kod sprawdzony, wszystkie możliwe 32-bitowe liczby całkowite przeszły, błąd -2147483647 (niedopełnienie).

Używa globali ... ale tak?

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

To rozwiązanie Perla działa na liczbach całkowitych, zmiennoprzecinkowych i ciągach .

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

Wypróbuj niektóre dane testowe.

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

Wynik:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar

Nikt nigdy nie powiedział, że f (x) musi być tego samego typu.

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


f(2) => [2]
f(f(2)) => -2

Właściwie nie próbuję rozwiązać samego problemu, ale mam kilka komentarzy, ponieważ pytanie mówi, że ten problem został postawiony w ramach wywiadu (pracy?):

• Najpierw zapytam: „Dlaczego taka funkcja byłaby potrzebna? Jaki jest większy problem?” zamiast próbować rozwiązać rzeczywisty problem na miejscu. To pokazuje, jak myślę i jak sobie radzę z takimi problemami. Kto wie? To może być nawet faktyczny powód, dla którego pytanie zadaje się w wywiadzie. Jeśli odpowiedź brzmi: „Nieważne, załóż, że jest potrzebna i pokaż mi, jak zaprojektowałbyś tę funkcję”. W takim razie kontynuowałbym to.
• Następnie napisałbym kod przypadku testowego C #, którego użyłbym (oczywiste: zapętlenie od int.MinValuedo int.MaxValue, i dla każdego nw tym zakresie wywołanie f(f(n))i sprawdzenie wyniku to-n ), mówiąc, że użyję Test Driven Development, aby dostać się do takiej funkcji.
• Tylko jeśli osoba przeprowadzająca rozmowę nadal prosi mnie o rozwiązanie postawionego problemu, zacznę pisać kod pseudokodowy podczas samego wywiadu, aby uzyskać odpowiedź. Jednak tak naprawdę nie sądzę, że skoczyłbym do pracy, jeśli osoba przeprowadzająca rozmowę kwalifikacyjną byłaby jakimkolwiek wskaźnikiem tego, jaka jest firma ...

Och, ta odpowiedź zakłada, że ​​wywiad dotyczył stanowiska związanego z programowaniem w języku C #. Byłoby oczywiście głupią odpowiedzią, gdyby wywiad dotyczył stanowiska matematycznego. ;-)

Chciałbym zmienić 2 najbardziej znaczące bity.

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

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

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

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

Jak widać, to tylko dodatek, pomijając przeniesiony kawałek.

Jak dotarłem do odpowiedzi? Moją pierwszą myślą była potrzeba symetrii. 4 obroty, by wrócić tam, gdzie zacząłem. Na początku myślałem, że to 2-bitowy kod Graya. Pomyślałem wtedy, że wystarczy standardowy plik binarny.

Oto rozwiązanie inspirowane wymogiem lub twierdzeniem, że nie można użyć liczb zespolonych do rozwiązania tego problemu.

Pomnożenie przez pierwiastek kwadratowy z -1 jest pomysłem, który wydaje się zawodzić, ponieważ -1 nie ma pierwiastka kwadratowego nad liczbami całkowitymi. Ale zabawa z programem takim jak matematyka daje na przykład równanie

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

i jest to prawie tak dobre, jak posiadanie pierwiastka kwadratowego z -1. Wynikiem funkcji musi być liczba całkowita ze znakiem. Dlatego zamierzam użyć zmodyfikowanych modów operacji modulo (x, n), które zwracają liczbę całkowitą y przystającą do x modulo n, która jest najbliższa 0. Tylko kilka języków programowania ma operację modulo, ale można ją łatwo zdefiniować . Np. W python jest to:

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

Korzystając z powyższego równania, problem można teraz rozwiązać jako

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

Spełnia to f(f(x)) = -xwszystkie liczby całkowite w zakresie . Wyniki są również w tym zakresie, ale oczywiście obliczenia wymagałyby 64-bitowych liczb całkowitych.[-231-2, 231-2]f(x)

C # dla zakresu 2 ^ 32-1 liczb, wszystkie liczby int32 oprócz (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

drukuje:

2147483647
3
2
1
0
-1
-2
-3
-2147483647

Zasadniczo funkcja musi podzielić dostępny zakres na cykle wielkości 4, przy czym -n na przeciwległym końcu cyklu n. Jednak 0 musi być częścią cyklu o rozmiarze 1, ponieważ w przeciwnym razie0->x->0->x != -x . Ponieważ 0 jest sam, muszą być 3 inne wartości w naszym zakresie (których rozmiar jest wielokrotnością 4), które nie są w prawidłowym cyklu z 4 elementami.

Wybrałem te dodatkowe wartości dziwne być MIN_INT, MAX_INTi MIN_INT+1. Co więcej, MIN_INT+1odwzoruje MAX_INTpoprawnie, ale utknie tam i nie odwróci mapy. Myślę, że jest to najlepszy kompromis, ponieważ ma tę fajną właściwość, że ekstremalne wartości nie działają poprawnie. Oznacza to również, że będzie działać dla wszystkich BigInts.

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)

Nikt nie powiedział, że to musi być bezpaństwowiec.

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

Oszukiwanie, ale nie tak wiele przykładów. Jeszcze większym złem byłoby zerknięcie na stos, aby sprawdzić, czy adres dzwoniącego to & f, ale będzie on bardziej przenośny (chociaż nie jest bezpieczny dla wątków ... wersja dla wątków używa TLS). Jeszcze więcej zła:

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

Oczywiście żadne z tych nie działa zbyt dobrze w przypadku MIN_INT32, ale niewiele można na to poradzić, chyba że pozwolimy ci zwrócić szerszy typ.

Mogę sobie wyobrazić, że użycie 31-go bitu jako fikcyjnego ( i ) bitu byłoby podejściem, które obsługiwałoby połowę całkowitego zakresu.

działa dla 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
}

Problem mówi „32-bitowe liczby całkowite ze znakiem”, ale nie określa, czy są one dopełniane do dwóch, czy do jednego .

Jeśli użyjesz jedynego uzupełnienia, wówczas wszystkie wartości 2 ^ 32 występują w cyklach o długości czwartej - nie potrzebujesz specjalnego przypadku dla zera, a także nie potrzebujesz warunków warunkowych.

W C:

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

Działa to przez

1. Wymiana wysokich i niskich 16-bitowych bloków
2. Odwracanie jednego z bloków

Po dwóch przejściach mamy bitową odwrotność oryginalnej wartości. Które w reprezentacji jednego dopełniacza jest równoważne negacji.

Przykłady:

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)

:RE

boolean inner = true;

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

return x ^ ((x%2) ? 1 : -INT_MAX);

Chciałbym podzielić się moim poglądem na ten interesujący problem jako matematyk. Myślę, że mam najbardziej wydajne rozwiązanie.

Jeśli dobrze pamiętam, negujesz 32-bitową liczbę całkowitą ze znakiem, po prostu odwracając pierwszy bit. Na przykład, jeśli n = 1001 1101 1110 1011 1110 0000 1110 1010, to -n = 0001 1101 1110 1011 1110 0000 1110 1010.

Jak więc zdefiniować funkcję f, która pobiera 32-bitową liczbę całkowitą ze znakiem i zwraca kolejną 32-bitową liczbę całkowitą ze znakiem, że dwukrotne pobranie f jest tym samym, co odwrócenie pierwszego bitu?

Pozwól, że sformułuję to pytanie, nie wspominając o pojęciach arytmetycznych, takich jak liczby całkowite.

Jak zdefiniujemy funkcję f, która pobiera sekwencję zer i jedynek o długości 32 i zwraca sekwencję zer i jedynek o tej samej długości, z właściwością, że pobranie f dwa razy jest takie samo jak przerzucenie pierwszego bitu?

Uwaga: Jeśli możesz odpowiedzieć na powyższe pytanie w przypadku 32 bitów, możesz także odpowiedzieć w przypadku 64 bitów, 100 bitów itp. Po prostu zastosuj f do pierwszego 32 bitów.

Teraz, jeśli możesz odpowiedzieć na pytanie w przypadku 2 bitów, Voila!

I tak, okazuje się, że wystarczy zmienić pierwsze 2 bity.

Oto pseudo-kod

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.

Uwaga: Krok 2 i krok 3 razem można zapisać na lato jako (a, b) -> (-b, a). Wygląda znajomo? To powinno przypominać o obróceniu płaszczyzny o 90 stopni i pomnożeniu przez pierwiastek kwadratowy z -1.

Gdybym sam przedstawił pseudo-kod bez długiego preludium, wyglądałoby to jak królik z kapelusza, chciałem wyjaśnić, skąd mam rozwiązanie.