Chcę zdefiniować funkcję, która przyjmuje unsigned int
jako argument i zwraca int
kongruentny 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 int
jest zdefiniowane w implementacji dla niektórych danych wejściowych, rzutowanie z powrotem do unsigned
jest 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 int
bez 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ę 4sizeof(unsigned)
równa się 4INT_MAX
wynosi 32767INT_MIN
równa się -2 32 + 32768UINT_MAX
równa się 2 32 - 1- Arytmetyka włączona
int
to modulo 2 32 (w zakresieINT_MIN
doINT_MAX
) std::numeric_limits<int>::is_modulo
jest prawdziwy- Rzutowanie unsigned
n
na int zachowuje wartość dla 0 <= n <= 32767 i daje zero w przeciwnym razie
W tej hipotetycznej implementacji istnieje dokładnie jedna int
wartość przystająca (mod UINT_MAX + 1) do każdej unsigned
wartoś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_modulo
jest to całkowicie bezużyteczne z wielu powodów. Po pierwsze, może tak być true
nawet wtedy, gdy rzutowania bez znaku do podpisania nie działają dla dużych wartości bez znaku. Po drugie, może to być true
nawet 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_modulo
tego, 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 32 +32768 jest dozwolone. Jeśli twoja odpowiedź zakłada inaczej, jest nieprawidłowa, chyba że zacytujesz standard C ++, który udowodni, że się mylę.
int
potrzeba co najmniej 33 bitów, aby ją przedstawić. Wiem, że to tylko przypis, więc możesz argumentować, że jest on nienormatywny, ale myślę, że przypis 49 w C ++ 11 ma być prawdziwy (ponieważ jest to definicja terminu użytego w standardzie) i nie jest sprzeczny wszystko, co zostało wyraźnie określone w tekście normatywnym. Zatem wszystkie wartości ujemne muszą być reprezentowane przez wzorzec bitowy, w którym ustawiony jest najwyższy bit, a zatem nie można ich upchać2^32 - 32768
w 32 bitach. Nie chodzi o to, że twój argument opiera się w jakikolwiek sposób na rozmiarzeint
.Odpowiedzi:
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_MIN
zostanie przekonwertowany naunsigned
),x - INT_MIN <= INT_MAX
to nie spowoduje to przepełnienia.Jeśli nie jest to oczywiste, spójrz na oświadczenie „Jeśli
x >= -4u
, tox + 4 <= 3
” i pamiętaj, żeINT_MAX
będzie to co najmniej wartość matematyczna -INT_MIN - 1.W najpopularniejszych systemach, gdzie
!(x <= INT_MAX)
implikujex >= INT_MIN
, optymalizator powinien być w stanie (a w moim systemie jest w stanie) usunąć drugie sprawdzenie, określić, czy te dwiereturn
instrukcje 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:
nie jest możliwe, więc nie wymaga specjalnej uwagi.
INT_MIN
będzie równa albo-INT_MAX
albo-INT_MAX - 1
. Wynika to z reprezentacji typów całkowitych w języku C (6.2.6.2), która wymaga, abyn
bity 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ża
x > 10
ix >= 11
testuje to samo. Generuje żądany kod tylko wtedy, gdyx >= INT_MIN
zostanie 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:
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):
Przypis (44) definiuje „czysty binarny system liczbowy”:
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 jakunsigned
), a kod hvd radzi sobie z tym dobrze.Ogromna dodatnia wartość bitu znaku spowodowałaby
int
maksymalne większe niżunsigned
, co jest zabronione.Ogromna ujemna wartość bitu znaku spowodowałaby
int
reprezentowanie 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 31 -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-1
wydaje się być dopuszczalna jako wartość dla „bitu znaku”, ale nic mniejszego (aby zakres nie był ciągły). Innymi słowy,INT_MIN
może to być wszystko od-INT_MAX-1
do -1.A teraz zgadnij co? Do drugiego rzutowania w kodzie hvd, aby uniknąć zachowania zdefiniowanego przez implementację, potrzebujemy po prostu
x - (unsigned)INT_MIN
mniej niż lub równeINT_MAX
. Właśnie pokazałINT_MIN
to co najmniej-INT_MAX-1
. Oczywiściex
co najwyżejUINT_MAX
. Rzutowanie liczby ujemnej na bez znaku jest tym samym, co dodawanieUINT_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” ...źródło
<limits.h>
są zdefiniowane w standardzie C ++ jako mające takie samo znaczenie jak w standardzie C, więc wszystkie wymagania C dlaINT_MIN
iINT_MAX
są dziedziczone w C ++. Masz rację, że C ++ 03 odnosi się do C90, a C90 jest niejasne, jeśli chodzi o dozwolone reprezentacje liczb całkowitych, ale zmiana C99 (odziedziczona przynajmniej<limits.h>
przez C ++ 11, miejmy nadzieję, że również w prostszy sposób) ogranicza ją do te trzy były jednym, który skodyfikował istniejącą praktykę: nie było innych wdrożeń.INT_MIN
itd. Jest dziedziczone po C. Ale to nie znaczy, że wartości są. (Rzeczywiście, jak mogliby oni, skoro każda implementacja jest inna?) Twoje wnioskowanie, któreINT_MIN
jest w granicach 1 od,-INT_MAX
zależy od sformułowania, które po prostu nie pojawia się w żadnej specyfikacji C ++. Więc chociaż C ++ dziedziczy semantyczne znaczenie makr, specyfikacja nie dostarcza (ani nie dziedziczy) sformułowania, które wspiera twoje wnioskowanie. Wydaje się, że jest to przeoczenie w specyfikacji C ++, które uniemożliwia w pełni zgodne, wydajne rzutowanie bez podpisu.INT_MIN
nie musi to być minimalna reprezentowalna wartość typuint
, ponieważ jeśli chodzi o C, jeśli typ nie spełniają wymaganiaint
, standard C nie może w żaden sposób objąć tej implementacji, a standard C ++ nie podaje żadnej definicji poza tym, „co mówi standard C”. Sprawdzę, czy istnieje prostsze wyjaśnienie.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.
źródło
result
przepełnia się; przepełnienie całkowite jest niezdefiniowane; dlatego pętla się kończy; dlategoi == n
na zakończenie; dlategoresult
jest równyn
. Nadal muszę preferować odpowiedź hvd (ze względu na niepatologiczne zachowanie mniej inteligentnych kompilatorów), ale zasługuje to na więcej głosów pozytywnych.n
jest jakąś wartością bez znaku ii
ostatecznie musi osiągnąć każdą wartość bez znaku.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. ZA
static_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
window
koncepcja? 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
0
i 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)
zamiast2^position
. Oznacza to, że dla wszystkichn - 1
bitó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 ++ 20std::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_window
Funkcja 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 + 1
jest równoważne z2^n
, gdzien
jest liczbą bitów w reprezentacji wartości. Wartość, której używamy dla rozmiaru naszego okna, jest równa2^(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ówna2^n
. Dodawanie i odejmowanie niex
jest opcją w modzie arytmetycznymx
, więc nie wpłynęliśmy na oryginalny mod wartości2^n
.Prawidłowa obsługa promocji w postaci liczb całkowitych
Ponieważ jest to funkcja rodzajowy i nie tylko
int
aunsigned
, musimy również zajmować się integralnych zasad promocji. Istnieją dwa potencjalnie interesujące przypadki: jeden, w którymshort
jest mniejszy niżint
i drugi, w którymshort
jest tego samego rozmiaru coint
.Przykład:
short
mniejszy niżint
Jeśli
short
jest mniejsze niżint
(powszechne na nowoczesnych platformach), to wiemy również, żeunsigned short
może zmieścić się w anint
, co oznacza, że wszelkie operacje na nim faktycznie wystąpią wint
, 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-bitowyshort
i 17-bitowyint
(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:
short
taki sam rozmiar jakint
Jeśli
short
ma taki sam rozmiar jakint
(rzadkie na nowoczesnych platformach), zasady integralnej promocji są nieco inne. W tym przypadkushort
promuje doint
iunsigned short
promuje dounsigned
. 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-bitoweshort
i 16-bitoweint
: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
int
aunsigned
i 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
cast
icast_to_signed_integer_basic
at-O2
oraz-O3
, a MSVC nie generuje żadnego kodu w/O2
, więc rozwiązanie jest optymalne.źródło
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.2
forx86_64-linux
(g++ -O -S test.cpp
) doźródło
UINT_MAX
jest wyrażeniem typuunsigned int
, a to sprawia, że całystatic_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1)
ten typ. Powinno być jednak możliwe naprawienie tego problemu i spodziewam się, że nadal będzie kompilowany tak samo.Jeśli
x
to nasz wkład ...Jeśli
x > INT_MAX
chcemy znaleźć stałąk
takie, że0
<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ć
x2
sięint
bezpiecznie. Pozwolićint x3 = static_cast<int>(x2);
Teraz chcemy odjąć coś takiego jak
UINT_MAX - k * INT_MAX + 1
odx3
, jeślik > 0
.Teraz, w systemie dopełnienia 2s, o ile
x > INT_MAX
dział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+1
w C ++ gwarantowane jest zero, konwersja na int była noopem i odjęliśmyk*INT_MAX
ją , 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_MAX
czy nie. Cóż, tworzymy 2 gałęzie, jedną zx > INT_MAX
i 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_MAX
jest naprawdę duży w stosunku doINT_MAX
, powyższe może nie działać. Zakładam to wk*INT_MAX <= UINT_MAX+1
sposó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ć.
źródło
UINT_MAX
nie może być mała w stosunku doINT_MAX
, ponieważ specyfikacja gwarantuje, że każda dodatnia liczba int ze znakiem jest reprezentowalna jako int bez znaku. AleUINT_MAX+1
wynosi zero w każdym systemie; arytmetyka bez znaku to zawsze moduloUINT_MAX+1
. Wciąż może istnieć jądro praktycznego podejścia ...UINT_MAX+1
jest równe zero w każdym systemie” ustalonym w '03 -spec? Jeśli tak, czy istnieje konkretna podsekcja, pod którą powinienem szukać? Dzięki.std::numeric_limits<int>::is_modulo
jest 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; }
EDYCJA : Poprawiono kod, aby uniknąć możliwej pułapki na maszynach niemodułowych (wiadomo, że istnieje tylko jedna, a mianowicie archaicznie skonfigurowane wersje Unisys Clearpath). Dla uproszczenia jest to realizowane przez brak obsługi wartości -2 n -1, gdzie n jest liczbą
int
bitów wartości na takiej maszynie (tj. Na Clearpath). w praktyce ta wartość również nie będzie obsługiwana przez maszynę (tj. z reprezentacją znak i wielkość lub uzupełnienie do 1).źródło
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
źródło
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
źródło