Wydajne rzutowanie bez podpisu bez zachowania zdefiniowanego przez implementację

Chcę zdefiniować funkcję, która przyjmuje unsigned intjako argument i zwraca intkongruentny modulo UINT_MAX + 1 do argumentu.

Pierwsza próba może wyglądać tak:

int unsigned_to_signed(unsigned n)
{
    return static_cast<int>(n);
}

Jednak, jak wie każdy prawnik zajmujący się językiem, rzutowanie wartości większych niż INT_MAX z unsigned na signed jest zdefiniowane przez implementację.

Chcę to zaimplementować w taki sposób, że (a) opiera się tylko na zachowaniu wymaganym przez specyfikację; i (b) kompiluje się w no-op na dowolnym nowoczesnym komputerze i optymalizującym kompilatorze.

A co do dziwacznych maszyn ... Jeśli nie ma podpisanego modulo int congruent UINT_MAX + 1 do unsigned int, powiedzmy, że chcę zgłosić wyjątek. Jeśli jest więcej niż jeden (nie jestem pewien, czy jest to możliwe), powiedzmy, że chcę największego.

OK, druga próba:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

Nie przejmuję się zbytnio wydajnością, gdy nie jestem na typowym systemie dwójkowym, bo moim skromnym zdaniem jest to mało prawdopodobne. A jeśli mój kod stanie się wąskim gardłem we wszechobecnych systemach wielkości znaków w 2050 roku, cóż, założę się, że ktoś może to rozgryźć i zoptymalizować.

Otóż, ta druga próba jest bliska tego, czego chcę. Chociaż rzutowanie do intjest zdefiniowane w implementacji dla niektórych danych wejściowych, rzutowanie z powrotem do unsignedjest gwarantowane przez standard, aby zachować wartość modulo UINT_MAX + 1. Tak więc warunek sprawdza dokładnie to, czego chcę, i nie skompiluje się do niczego w żadnym systemie, który prawdopodobnie napotkam.

Jednak ... nadal rzutuję do intbez uprzedniego sprawdzenia, czy wywoła zachowanie zdefiniowane w implementacji. W jakimś hipotetycznym systemie w 2050 r. Mógłby zrobić nie wiadomo co. Powiedzmy, że chcę tego uniknąć.

Pytanie: Jak powinna wyglądać moja „trzecia próba”?

Podsumowując, chcę:

• Przesyłanie z int unsigned do int signed int
• Zachowaj wartość mod UINT_MAX + 1
• Wywołaj tylko standardowe zachowanie
• Skompiluj do no-op na typowej maszynie z uzupełnieniem do dwóch z optymalizującym kompilatorem

[Aktualizacja]

Podam przykład, aby pokazać, dlaczego nie jest to trywialne pytanie.

Rozważmy hipotetyczną implementację C ++ z następującymi właściwościami:

• sizeof(int) równa się 4
• sizeof(unsigned) równa się 4
• INT_MAX wynosi 32767
• INT_MINrówna się -2 ³² + 32768
• UINT_MAXrówna się 2 ³² - 1
• Arytmetyka włączona intto modulo 2 ³² (w zakresie INT_MINdo INT_MAX)
• std::numeric_limits<int>::is_modulo jest prawdziwy
• Rzutowanie unsigned nna int zachowuje wartość dla 0 <= n <= 32767 i daje zero w przeciwnym razie

W tej hipotetycznej implementacji istnieje dokładnie jedna intwartość przystająca (mod UINT_MAX + 1) do każdej unsignedwartości. Więc moje pytanie byłoby dobrze zdefiniowane.

Twierdzę, że ta hipotetyczna implementacja C ++ jest w pełni zgodna ze specyfikacjami C ++ 98, C ++ 03 i C ++ 11. Przyznaję, że nie zapamiętałem każdego słowa z nich wszystkich ... Ale wydaje mi się, że uważnie przeczytałem odpowiednie rozdziały. Jeśli więc chcesz, żebym zaakceptował twoją odpowiedź, musisz albo (a) zacytować specyfikację, która wyklucza tę hipotetyczną implementację, albo (b) poprawnie ją obsłużyć.

Rzeczywiście, prawidłowa odpowiedź musi uwzględniać każdą hipotetyczną implementację dozwoloną przez normę. To właśnie z definicji oznacza „powoływanie się tylko na zachowanie narzucone przez normy”.

Nawiasem mówiąc, pamiętaj, że std::numeric_limits<int>::is_modulojest to całkowicie bezużyteczne z wielu powodów. Po pierwsze, może tak być truenawet wtedy, gdy rzutowania bez znaku do podpisania nie działają dla dużych wartości bez znaku. Po drugie, może to być truenawet w systemach z dopełnieniem lub ze znakiem, jeśli arytmetyka jest po prostu modulo całego zakresu liczb całkowitych. I tak dalej. Jeśli Twoja odpowiedź zależy od is_modulotego, jest błędna.

[Aktualizacja 2]

Odpowiedź hvd nauczyła mnie czegoś: Moja hipotetyczna implementacja liczb całkowitych w C ++ nie jest dozwolona przez współczesne C. Standardy C99 i C11 są bardzo szczegółowe w zakresie reprezentacji liczb całkowitych ze znakiem; w rzeczywistości zezwalają tylko na uzupełnienie do dwóch, uzupełnienie do jedności i wielkość znaku (sekcja 6.2.6.2 akapit (2);).

Ale C ++ to nie C. Jak się okazuje, ten fakt leży w samym sercu mojego pytania.

Oryginalny standard C ++ 98 był oparty na znacznie starszym C89, który mówi (sekcja 3.1.2.5):

Dla każdego typu liczb całkowitych ze znakiem istnieje odpowiedni (ale inny) typ liczby całkowitej bez znaku (oznaczony słowem kluczowym bez znaku), który wykorzystuje tę samą ilość pamięci (w tym informacje o znakach) i ma takie same wymagania dotyczące wyrównania. Zakres nieujemnych wartości typu liczby całkowitej ze znakiem jest podzakresem odpowiedniego typu liczby całkowitej bez znaku, a reprezentacja tej samej wartości w każdym typie jest taka sama.

C89 nie mówi nic o posiadaniu tylko jednego bitu znaku lub dopuszczaniu tylko wielkości uzupełnienia do dwóch / dopełnienia jedynkowego / wielkości znaku.

Standard C ++ 98 przyjął ten język prawie dosłownie (sekcja 3.9.1 akapit (3)):

Dla każdego z typów liczb całkowitych ze znakiem istnieje odpowiedni (ale inny) typ liczby całkowitej bez znaku : " unsigned char", " unsigned short int", " unsigned int" i " unsigned long int", z których każdy zajmuje taką samą ilość pamięci i ma takie same wymagania dotyczące wyrównania (3.9 ) jako odpowiedni typ liczby całkowitej ze znakiem; to znaczy, każdy typ liczby całkowitej ze znakiem ma taką samą reprezentację obiektu, jak odpowiadający mu typ liczby całkowitej bez znaku . Zakres nieujemnych wartości typu liczby całkowitej ze znakiem jest podzakresem odpowiedniego typu liczby całkowitej bez znaku, a reprezentacja wartości każdego odpowiedniego typu ze znakiem / bez znaku powinna być taka sama.

Standard C ++ 03 używa zasadniczo identycznego języka, podobnie jak C ++ 11.

Żadna standardowa specyfikacja C ++ nie ogranicza swoich reprezentacji liczb całkowitych ze znakiem do żadnej specyfikacji języka C, o ile wiem. I nie ma nic nakazującego ani jednego kawałka znaku ani niczego w tym rodzaju. Mówi się tylko, że nieujemne liczby całkowite ze znakiem muszą być podzakresem odpowiadających im liczb całkowitych bez znaku.

Tak więc ponownie twierdzę, że INT_MAX = 32767 z INT_MIN = -2 ³² +32768 jest dozwolone. Jeśli twoja odpowiedź zakłada inaczej, jest nieprawidłowa, chyba że zacytujesz standard C ++, który udowodni, że się mylę.

Rozwinięcie odpowiedzi użytkownika71404:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

Jeśli x >= INT_MIN(pamiętaj o zasadach promocji, INT_MINzostanie przekonwertowany na unsigned), x - INT_MIN <= INT_MAXto nie spowoduje to przepełnienia.

Jeśli nie jest to oczywiste, spójrz na oświadczenie „Jeśli x >= -4u, to x + 4 <= 3” i pamiętaj, że INT_MAXbędzie to co najmniej wartość matematyczna -INT_MIN - 1.

W najpopularniejszych systemach, gdzie !(x <= INT_MAX)implikuje x >= INT_MIN, optymalizator powinien być w stanie (a w moim systemie jest w stanie) usunąć drugie sprawdzenie, określić, czy te dwie returninstrukcje można skompilować do tego samego kodu, i usunąć również pierwsze sprawdzenie. Wygenerowana lista montażu:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

Hipotetyczna realizacja twojego pytania:

• INT_MAX wynosi 32767
• INT_MIN równa się -2 ³² + 32768

nie jest możliwe, więc nie wymaga specjalnej uwagi. INT_MINbędzie równa albo -INT_MAXalbo -INT_MAX - 1. Wynika to z reprezentacji typów całkowitych w języku C (6.2.6.2), która wymaga, aby nbity były bitami wartości, jeden bit był bitem znaku i dopuszcza tylko jedną reprezentację pojedynczej pułapki (bez reprezentacji, które są nieważne z powodu bitów wypełniających), mianowicie ten, który w przeciwnym razie reprezentowałby ujemne zero / -INT_MAX - 1. C ++ nie zezwala na żadne reprezentacje liczb całkowitych poza tym, na co pozwala C.

Aktualizacja : kompilator Microsoftu najwyraźniej tego nie zauważax > 10ix >= 11testuje to samo. Generuje żądany kod tylko wtedy, gdyx >= INT_MINzostanie zastąpiony przezx > INT_MIN - 1u, który może wykryć jako negacjęx <= INT_MAX(na tej platformie).

[Informacje od pytającego (Nemo), omawiające naszą dyskusję poniżej]

Teraz uważam, że ta odpowiedź działa we wszystkich przypadkach, ale ze skomplikowanych powodów. Prawdopodobnie nagrodzę to rozwiązanie, ale chcę uchwycić wszystkie krwawe szczegóły na wypadek, gdyby kogoś to obchodziło.

Zacznijmy od C ++ 11, sekcja 18.3.3:

Tabela 31 opisuje nagłówek <climits>.

...

Treści są takie same jak w nagłówku biblioteka standardowa C <limits.h>.

Tutaj „Standard C” oznacza C99, którego specyfikacja poważnie ogranicza reprezentację liczb całkowitych ze znakiem. Są one jak liczby całkowite bez znaku, ale mają jeden bit przeznaczony na „znak” i zero lub więcej bitów na „wypełnienie”. Bity wypełniające nie wpływają na wartość liczby całkowitej, a bit znaku przyczynia się tylko jako uzupełnienie do dwóch, dopełnienie do jedynki lub wielkość znaku.

Ponieważ C ++ 11 dziedziczy <climits>makra z C99, INT_MIN ma wartość -INT_MAX lub -INT_MAX-1, a kod hvd jest gwarantowany. (Zauważ, że ze względu na wypełnienie, INT_MAX może być znacznie mniejszy niż UINT_MAX / 2 ... Ale dzięki temu, jak działają rzutowania podpisane-> niepodpisane, ta odpowiedź radzi sobie dobrze.)

C ++ 03 / C ++ 98 jest trudniejsze. Używa tego samego sformułowania, aby dziedziczyć <climits>po „Standard C”, ale teraz „Standard C” oznacza C89 / C90.

Wszystkie z nich - C ++ 98, C ++ 03, C89 / C90 - mają sformułowanie, które podam w moim pytaniu, ale zawierają również to (C ++ 03 sekcja 3.9.1 akapit 7):

Reprezentacje typów całkowitych powinny definiować wartości przy użyciu czystego binarnego systemu liczbowego. (44) [ Przykład : w niniejszej Normie Międzynarodowej dopuszcza się uzupełnienie do 2, uzupełnienie 1 i reprezentację wielkości ze znakiem dla typów całkowitych.]

Przypis (44) definiuje „czysty binarny system liczbowy”:

Reprezentacja pozycyjna liczb całkowitych, która używa cyfr binarnych 0 i 1, w której wartości reprezentowane przez kolejne bity są addytywne, rozpoczynają się od 1 i są mnożone przez kolejną moc całkującą 2, z wyjątkiem być może bitu o najwyższej pozycji.

Co ciekawe w tym sformułowaniu jest to, że jest ono sprzeczne ze sobą, ponieważ definicja „czystego binarnego systemu numeracji” nie pozwala na przedstawienie znaku / wielkości! Pozwala to wyższemu bitowi mieć, powiedzmy, wartość -2 ^n-1 (uzupełnienie do dwóch) lub - (2 ^n-1 -1) (dopełnienie jedności). Ale nie ma wartości dla wysokiego bitu, który daje znak / wielkość.

W każdym razie moja „hipotetyczna implementacja” nie kwalifikuje się jako „czysto binarna” w ramach tej definicji, więc jest wykluczona.

Jednak fakt, że wysoki bit jest specjalny, oznacza, że ​​możemy sobie wyobrazić, że wnosi on jakąkolwiek wartość: mała wartość dodatnia, ogromna wartość dodatnia, mała wartość ujemna lub ogromna wartość ujemna. (Jeśli bit znaku może przyczynić się do - (2 ^n-1 -1), dlaczego nie - (2 ^n-1 -2)? Itd.)

Wyobraźmy sobie więc reprezentację liczby całkowitej ze znakiem, która przypisuje zwariowaną wartość do bitu „znaku”.

Mała dodatnia wartość bitu znaku dałaby dodatni zakres dla int(prawdopodobnie tak duży jak unsigned), a kod hvd radzi sobie z tym dobrze.

Ogromna dodatnia wartość bitu znaku spowodowałaby intmaksymalne większe niż unsigned, co jest zabronione.

Ogromna ujemna wartość bitu znaku spowodowałaby intreprezentowanie nieciągłego zakresu wartości, a inne sformułowania w specyfikacji wykluczają to.

Wreszcie, co powiesz na kawałek znaku, który wnosi niewielką ilość ujemną? Czy moglibyśmy mieć 1 w „bicie znaku”, na przykład -37 do wartości int? Zatem INT_MAX będzie (powiedzmy) 2 ³¹ -1, a INT_MIN będzie równe -37?

To spowodowałoby, że niektóre liczby miałyby dwie reprezentacje ... Ale uzupełnienie jedynkowe daje dwie reprezentacje do zera, co jest dozwolone zgodnie z „Przykładem”. Nigdzie specyfikacja nie mówi, że zero jest jedyną liczbą całkowitą, która może mieć dwie reprezentacje. Więc myślę, że ta nowa hipoteza jest dozwolona przez specyfikację.

Rzeczywiście, każda wartość ujemna od -1 do -INT_MAX-1wydaje się być dopuszczalna jako wartość dla „bitu znaku”, ale nic mniejszego (aby zakres nie był ciągły). Innymi słowy, INT_MINmoże to być wszystko od -INT_MAX-1do -1.

A teraz zgadnij co? Do drugiego rzutowania w kodzie hvd, aby uniknąć zachowania zdefiniowanego przez implementację, potrzebujemy po prostu x - (unsigned)INT_MINmniej niż lub równe INT_MAX. Właśnie pokazał INT_MINto co najmniej -INT_MAX-1. Oczywiście xco najwyżej UINT_MAX. Rzutowanie liczby ujemnej na bez znaku jest tym samym, co dodawanie UINT_MAX+1. Złóż to wszystko w całość:

x - (unsigned)INT_MIN <= INT_MAX

wtedy i tylko wtedy gdy

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

To ostatnie właśnie pokazaliśmy, więc nawet w tym przewrotnym przypadku kod faktycznie działa.

To wyczerpuje wszystkie możliwości i kończy to niezwykle akademickie ćwiczenie.

Konkluzja: W C89 / C90 występuje pewne niedostatecznie określone zachowanie dla liczb całkowitych ze znakiem, które zostały odziedziczone przez C ++ 98 / C ++ 03. Zostało to naprawione w C99, a C ++ 11 pośrednio dziedziczy poprawkę poprzez włączenie <limits.h>z C99. Ale nawet C ++ 11 zachowuje wewnętrznie sprzeczne sformułowanie „czysta reprezentacja binarna” ...

Ten kod opiera się tylko na zachowaniu wymaganym przez specyfikację, więc wymaganie (a) jest łatwo spełnione:

int unsigned_to_signed(unsigned n)
{
  int result = INT_MAX;

  if (n > INT_MAX && n < INT_MIN)
    throw runtime_error("no signed int for this number");

  for (unsigned i = INT_MAX; i != n; --i)
    --result;

  return result;
}

Z wymaganiem (b) nie jest tak łatwo. To kompiluje się do no-op z gcc 4.6.3 (-Os, -O2, -O3) i clang 3.0 (-Os, -O, -O2, -O3). Intel 12.1.0 odmawia optymalizacji tego. I nie mam żadnych informacji o Visual C.

Oryginalna odpowiedź rozwiązała problem tylko dla unsigned=> int. A jeśli chcemy rozwiązać ogólny problem „jakiegoś typu bez znaku” na odpowiadający mu typ ze znakiem? Co więcej, oryginalna odpowiedź była doskonała w cytowaniu fragmentów normy i analizowaniu niektórych przypadków narożnych, ale tak naprawdę nie pomogła mi zrozumieć, dlaczego zadziałała, więc ta odpowiedź będzie próbą podania mocnej podstawy koncepcyjnej. Ta odpowiedź pomoże wyjaśnić „dlaczego” i użyć nowoczesnych funkcji C ++, aby spróbować uprościć kod.

Odpowiedź C ++ 20

Problem znacznie się uprościł dzięki P0907: Podpisane liczby całkowite to dopełnienie do dwóch i ostateczne sformułowanie P1236, które zostało wybrane w standardzie C ++ 20. Teraz odpowiedź jest tak prosta, jak to tylko możliwe:

template<std::unsigned_integral T>
constexpr auto cast_to_signed_integer(T const value) {
    return static_cast<std::make_signed_t<T>>(value);
}

Otóż ​​to. ZAstatic_cast(Lub C-style cast) jest gwarantowana wreszcie zrobić coś, czego potrzeba na to pytanie, i rzecz wielu programistów, że to zawsze było.

Odpowiedź w C ++ 17

W C ++ 17 sprawy są znacznie bardziej skomplikowane. Mamy do czynienia z trzema możliwymi reprezentacjami liczb całkowitych (uzupełnieniem do dwóch, uzupełnieniem do jedynki i wielkością znaku). Nawet w przypadku, gdy wiemy, że musi to być uzupełnienie do dwóch, ponieważ sprawdziliśmy zakres możliwych wartości, konwersja wartości spoza zakresu liczby całkowitej ze znakiem na tę liczbę całkowitą ze znakiem nadal daje nam wynik zdefiniowany w implementacji. Musimy używać sztuczek, które widzieliśmy w innych odpowiedziach.

Po pierwsze, oto kod, który pokazuje, jak ogólnie rozwiązać problem:

template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
constexpr auto cast_to_signed_integer(T const value) {
    using result = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<T>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<result>(value);
    } else {
        using promoted_unsigned = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
        using promoted_signed = std::make_signed_t<promoted_unsigned>;
        constexpr auto shift_by_window = [](auto x) {
            // static_cast to avoid conversion warning
            return x - static_cast<decltype(x)>(result_limits::max()) - 1;
        };
        return static_cast<result>(
            shift_by_window( // shift values from common range to negative range
                static_cast<promoted_signed>(
                    shift_by_window( // shift large values into common range
                        static_cast<promoted_unsigned>(value) // cast to avoid promotion to int
                    )
                )
            )
        );
    }
}

Ma to kilka rzutów więcej niż akceptowana odpowiedź, a to ma na celu zapewnienie, że nie ma żadnych podpisanych / niepodpisanych ostrzeżeń o niezgodności z twojego kompilatora i poprawnie obsługuje reguły promocji liczb całkowitych.

Najpierw mamy specjalny przypadek dla systemów, które nie są dopełnieniem do dwóch (i dlatego musimy obsłużyć maksymalną możliwą wartość, szczególnie, ponieważ nie ma ona nic do zmapowania). Następnie dochodzimy do prawdziwego algorytmu.

Drugi warunek najwyższego poziomu jest prosty: wiemy, że wartość jest mniejsza lub równa wartości maksymalnej, więc pasuje do typu wyniku. Trzeci warunek jest nieco bardziej skomplikowany, nawet w przypadku komentarzy, więc niektóre przykłady prawdopodobnie pomogłyby zrozumieć, dlaczego każde stwierdzenie jest konieczne.

Podstawa koncepcyjna: oś liczbowa

Po pierwsze, co to za windowkoncepcja? Rozważ następującą oś liczbową:

   |   signed   |
<.........................>
          |  unsigned  |

Okazuje się, że dla liczb całkowitych z dopełnieniem do dwóch można podzielić podzbiór osi liczbowej, do której można dotrzeć za pomocą dowolnego typu, na trzy równe kategorie:

- => signed only
= => both
+ => unsigned only

<..-------=======+++++++..>

Można to łatwo udowodnić, rozważając reprezentację. Liczba całkowita bez znaku zaczyna się od 0i wykorzystuje wszystkie bity do zwiększenia wartości w potęgach 2. Liczba całkowita ze znakiem jest dokładnie taka sama dla wszystkich bitów z wyjątkiem bitu znaku, którego wartość jest warta -(2^position)zamiast 2^position. Oznacza to, że dla wszystkich n - 1bitów reprezentują te same wartości. Następnie liczby całkowite bez znaku mają jeszcze jeden normalny bit, który podwaja całkowitą liczbę wartości (innymi słowy, jest tyle samo wartości z ustawionym bitem, co bez niego). Ta sama logika obowiązuje dla liczb całkowitych ze znakiem, z wyjątkiem tego, że wszystkie wartości z tym ustawionym bitem są ujemne.

Pozostałe dwie poprawne reprezentacje liczb całkowitych, uzupełnienie jedności i wielkość znaku, mają wszystkie te same wartości, co liczby całkowite uzupełnienia do dwóch, z wyjątkiem jednej: wartości najbardziej ujemnej. C ++ definiuje wszystko, co dotyczy typów całkowitych, z wyjątkiem reinterpret_cast(i C ++ 20 std::bit_cast), pod względem zakresu reprezentowanych wartości, a nie pod względem reprezentacji bitowej. Oznacza to, że nasza analiza będzie się utrzymywać dla każdej z tych trzech reprezentacji, o ile nigdy nie spróbujemy stworzyć reprezentacji pułapki. Wartość bez znaku, która byłaby mapowana na tę brakującą wartość, jest raczej niefortunna: ta, która znajduje się w środku wartości bez znaku. Na szczęście nasz pierwszy warunek sprawdza (w czasie kompilacji), czy taka reprezentacja istnieje, a następnie obsługuje ją specjalnie za pomocą sprawdzenia w czasie wykonywania.

Pierwszy warunek obsługuje przypadek, w którym jesteśmy w =sekcji, co oznacza, że ​​znajdujemy się w nakładającym się regionie, w którym wartości w jednym mogą być reprezentowane w drugim bez zmian. shift_by_windowFunkcja w kodzie porusza wszystkie wartości ze względu na wielkość każdego z tych segmentów (mamy odjąć wartość max odejmujemy 1, aby uniknąć problemów arytmetycznych overflow). Jeśli jesteśmy poza tym regionem (jesteśmy w regionie), to znowu mamy unikalne mapowanie.+ regionie), musimy przeskoczyć w dół o jeden rozmiar okna. To stawia nas w nakładającym się zakresie, co oznacza, że ​​możemy bezpiecznie przekonwertować z niepodpisanego na podpisany, ponieważ nie ma zmiany wartości. Jednak nie skończyliśmy jeszcze, ponieważ zamapowaliśmy dwie wartości bez znaku na każdą wartość ze znakiem. Dlatego musimy przejść do następnego okna (-

Czy to daje nam wynik zgodny z modą UINT_MAX + 1, zgodnie z żądaniem w pytaniu? UINT_MAX + 1jest równoważne z 2^n, gdzie njest liczbą bitów w reprezentacji wartości. Wartość, której używamy dla rozmiaru naszego okna, jest równa 2^(n - 1)(ostatni indeks w sekwencji wartości jest o jeden mniejszy niż rozmiar). Odejmujemy tę wartość dwukrotnie, co oznacza, że ​​odejmujemy, 2 * 2^(n - 1)która jest równa 2^n. Dodawanie i odejmowanie nie xjest opcją w modzie arytmetycznym x, więc nie wpłynęliśmy na oryginalny mod wartości 2^n.

Prawidłowa obsługa promocji w postaci liczb całkowitych

Ponieważ jest to funkcja rodzajowy i nie tylko inta unsigned, musimy również zajmować się integralnych zasad promocji. Istnieją dwa potencjalnie interesujące przypadki: jeden, w którym shortjest mniejszy niż inti drugi, w którym shortjest tego samego rozmiaru co int.

Przykład: shortmniejszy niżint

Jeśli shortjest mniejsze niż int(powszechne na nowoczesnych platformach), to wiemy również, że unsigned shortmoże zmieścić się w an int, co oznacza, że ​​wszelkie operacje na nim faktycznie wystąpią w int, więc jawnie rzutujemy na typ promowany, aby tego uniknąć. Nasze końcowe stwierdzenie jest dość abstrakcyjne i staje się łatwiejsze do zrozumienia, jeśli zastąpimy je prawdziwymi wartościami. W naszym pierwszym interesującym przypadku, bez utraty ogólności, rozważmy 16-bitowy shorti 17-bitowy int(który jest nadal dozwolony w nowych zasadach i oznaczałby tylko, że co najmniej jeden z tych dwóch typów liczb całkowitych ma pewne bity wypełniające ):

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int17_t>(
            shift_by_window(
                static_cast<uint17_t>(value)
            )
        )
    )
);

Rozwiązywanie możliwie największej 16-bitowej wartości bez znaku

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return int16_t(
    shift_by_window(
        int17_t(
            shift_by_window(
                uint17_t(65535)
            )
        )
    )
);

Upraszcza do

return int16_t(
    int17_t(
        uint17_t(65535) - uint17_t(32767) - 1
    ) -
    int17_t(32767) -
    1
);

Upraszcza do

return int16_t(
    int17_t(uint17_t(32767)) -
    int17_t(32767) -
    1
);

Upraszcza do

return int16_t(
    int17_t(32767) -
    int17_t(32767) -
    1
);

Upraszcza do

return int16_t(-1);

Włożyliśmy jak najwięcej niepodpisanych i wracamy -1, sukces!

Przykład: shorttaki sam rozmiar jakint

Jeśli shortma taki sam rozmiar jak int(rzadkie na nowoczesnych platformach), zasady integralnej promocji są nieco inne. W tym przypadku shortpromuje do inti unsigned shortpromuje do unsigned. Na szczęście jawnie przypisujemy każdy wynik do typu, dla którego chcemy wykonać obliczenia, więc nie otrzymujemy żadnych problematycznych promocji. Bez utraty ogólności rozważmy 16-bitowe shorti 16-bitowe int:

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int16_t>(
            shift_by_window(
                static_cast<uint16_t>(value)
            )
        )
    )
);

Rozwiązywanie możliwie największej 16-bitowej wartości bez znaku

auto x = int16_t(
    uint16_t(65535) - uint16_t(32767) - 1
);
return int16_t(
    x - int16_t(32767) - 1
);

Upraszcza do

return int16_t(
    int16_t(32767) - int16_t(32767) - 1
);

Upraszcza do

return int16_t(-1);

Włożyliśmy jak najwięcej niepodpisanych i wracamy -1, sukces!

Co zrobić, jeśli po prostu dbają o inta unsignedi nie dbają o ostrzeżeniach, jak oryginalne pytanie?

constexpr int cast_to_signed_integer(unsigned const value) {
    using result_limits = std::numeric_limits<int>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<unsigned>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<int>(value);
    } else {
        constexpr int window = result_limits::min();
        return static_cast<int>(value + window) + window;
    }
}

Zobacz to na żywo

https://godbolt.org/z/74hY81

Tutaj widzimy, że clang, gcc i icc nie generują żadnego kodu dla casti cast_to_signed_integer_basicat -O2oraz -O3, a MSVC nie generuje żadnego kodu w /O2, więc rozwiązanie jest optymalne.

Możesz wyraźnie powiedzieć kompilatorowi, co chcesz zrobić:

int unsigned_to_signed(unsigned n) {
  if (n > INT_MAX) {
    if (n <= UINT_MAX + INT_MIN) {
      throw "no result";
    }
    return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1);
  } else {
    return static_cast<int>(n);
  }
}

Kompiluje się z gcc 4.7.2for x86_64-linux( g++ -O -S test.cpp) do

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

Jeśli xto nasz wkład ...

Jeśli x > INT_MAXchcemy znaleźć stałą ktakie, że 0< x - k*INT_MAX< INT_MAX.

To jest łatwe - unsigned int k = x / INT_MAX;. Wtedy pozwolićunsigned int x2 = x - k*INT_MAX;

Możemy teraz rzucać x2się intbezpiecznie. Pozwolićint x3 = static_cast<int>(x2);

Teraz chcemy odjąć coś takiego jak UINT_MAX - k * INT_MAX + 1od x3, jeśli k > 0.

Teraz, w systemie dopełnienia 2s, o ile x > INT_MAXdziała to tak:

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

Zauważ, że UINT_MAX+1w C ++ gwarantowane jest zero, konwersja na int była noopem i odjęliśmy k*INT_MAXją , a następnie dodaliśmy z powrotem na „tę samą wartość”. Zatem akceptowalny optymalizator powinien być w stanie wymazać wszystkie te błazeństwa!

To pozostawia problem, x > INT_MAXczy nie. Cóż, tworzymy 2 gałęzie, jedną z x > INT_MAXi jedną bez. Ten bez wykonuje rzutowanie typu strait, które kompilator optymalizuje do noop. Ten z ... robi noop po zakończeniu działania optymalizatora. Inteligentny optymalizator zdaje sobie sprawę, że obie gałęzie prowadzą do tego samego i porzuca gałąź.

Problemy: jeśli UINT_MAXjest naprawdę duży w stosunku do INT_MAX, powyższe może nie działać. Zakładam to w k*INT_MAX <= UINT_MAX+1sposób dorozumiany.

Prawdopodobnie moglibyśmy zaatakować to za pomocą niektórych wyliczeń, takich jak:

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

które, jak sądzę, dają wynik 2 i 1 w systemie dopełnienia 2s (czy mamy gwarancję, że ta matematyka zadziała? To trudne ...) i wykonuj logikę opartą na tych, które łatwo optymalizują się w systemach dopełniających innych niż 2 ...

To również otwiera przypadek wyjątku. Jest to możliwe tylko wtedy, gdy UINT_MAX jest znacznie większy niż (INT_MIN-INT_MAX), więc możesz umieścić swój kod wyjątku w bloku if zadając w jakiś sposób dokładnie to pytanie i nie spowolni cię to w tradycyjnym systemie.

Nie jestem do końca pewien, jak skonstruować te stałe czasu kompilacji, aby poprawnie sobie z tym poradzić.

std::numeric_limits<int>::is_modulojest stałą czasową kompilacji. więc możesz go użyć do specjalizacji w zakresie szablonów. problem rozwiązany, przynajmniej jeśli kompilator działa razem z wstawianiem.

#include <limits>
#include <stdexcept>
#include <string>

#ifdef TESTING_SF
    bool const testing_sf = true;
#else
    bool const testing_sf = false;
#endif

// C++ "extensions"
namespace cppx {
    using std::runtime_error;
    using std::string;

    inline bool hopefully( bool const c ) { return c; }
    inline bool throw_x( string const& s ) { throw runtime_error( s ); }

}  // namespace cppx

// C++ "portability perversions"
namespace cppp {
    using cppx::hopefully;
    using cppx::throw_x;
    using std::numeric_limits;

    namespace detail {
        template< bool isTwosComplement >
        int signed_from( unsigned const n )
        {
            if( n <= unsigned( numeric_limits<int>::max() ) )
            {
                return static_cast<int>( n );
            }

            unsigned const u_max = unsigned( -1 );
            unsigned const u_half = u_max/2 + 1;

            if( n == u_half )
            {
                throw_x( "signed_from: unsupported value (negative max)" );
            }

            int const i_quarter = static_cast<int>( u_half/2 );
            int const int_n1 = static_cast<int>( n - u_half );
            int const int_n2 = int_n1 - i_quarter;
            int const int_n3 = int_n2 - i_quarter;

            hopefully( n == static_cast<unsigned>( int_n3 ) )
                || throw_x( "signed_from: range error" );

            return int_n3;
        }

        template<>
        inline int signed_from<true>( unsigned const n )
        {
            return static_cast<int>( n );
        }
    }    // namespace detail

    inline int signed_from( unsigned const n )
    {
        bool const is_modulo = numeric_limits< int >::is_modulo;
        return detail::signed_from< is_modulo && !testing_sf >( n );
    }
}    // namespace cppp

#include <iostream>
using namespace std;
int main()
{
    int const x = cppp::signed_from( -42u );
    wcout << x << endl;
}

Myślę, że typ int ma co najmniej dwa bajty, więc INT_MIN i INT_MAX mogą się zmieniać na różnych platformach.

Podstawowe typy

≤climits≥ nagłówek

Moje pieniądze są na używaniu memcpy. Każdy przyzwoity kompilator wie, jak go zoptymalizować:

#include <stdio.h>
#include <memory.h>
#include <limits.h>

static inline int unsigned_to_signed(unsigned n)
{
    int result;
    memcpy( &result, &n, sizeof(result));
    return result;
}

int main(int argc, const char * argv[])
{
    unsigned int x = UINT_MAX - 1;
    int xx = unsigned_to_signed(x);
    return xx;
}

Dla mnie (Xcode 8.3.2, Apple LLVM 8.1, -O3), który daje:

_main:                                  ## @main
Lfunc_begin0:
    .loc    1 21 0                  ## /Users/Someone/main.c:21:0
    .cfi_startproc
## BB#0:
    pushq    %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    ##DEBUG_VALUE: main:argc <- %EDI
    ##DEBUG_VALUE: main:argv <- %RSI
Ltmp3:
    ##DEBUG_VALUE: main:x <- 2147483646
    ##DEBUG_VALUE: main:xx <- 2147483646
    .loc    1 24 5 prologue_end     ## /Users/Someone/main.c:24:5
    movl    $-2, %eax
    popq    %rbp
    retq
Ltmp4:
Lfunc_end0:
    .cfi_endproc