Effiziente Besetzung ohne Vorzeichen, um ein von der Implementierung definiertes Verhalten zu vermeiden

Ich möchte eine Funktion definieren, die ein unsigned intas-Argument verwendet und ein intkongruentes Modulo UINT_MAX + 1 an das Argument zurückgibt.

Ein erster Versuch könnte so aussehen:

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

Wie jeder Sprachanwalt weiß, ist das Casting von nicht signiert zu signiert für Werte größer als INT_MAX implementierungsdefiniert.

Ich möchte dies so implementieren, dass (a) es nur auf dem von der Spezifikation vorgeschriebenen Verhalten beruht; und (b) es wird auf jeder modernen Maschine zu einem No-Op kompiliert und der Compiler optimiert.

Was bizarre Maschinen betrifft ... Wenn es kein vorzeichenbehaftetes int-kongruentes Modulo UINT_MAX + 1 zum vorzeichenlosen int gibt, nehmen wir an, ich möchte eine Ausnahme auslösen. Wenn es mehr als eine gibt (ich bin nicht sicher, ob dies möglich ist), nehmen wir an, ich möchte die größte.

OK, zweiter Versuch:

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
}

Die Effizienz ist mir egal, wenn ich mich nicht in einem typischen Zweierkomplementsystem befinde, da dies meiner bescheidenen Meinung nach unwahrscheinlich ist. Und wenn mein Code zu einem Engpass bei den allgegenwärtigen Vorzeichengrößen-Systemen von 2050 wird, kann jemand das herausfinden und dann optimieren.

Dieser zweite Versuch kommt dem, was ich will, ziemlich nahe. Obwohl die Umwandlung in intfür einige Eingaben implementierungsdefiniert unsignedist, wird die Umwandlung in durch den Standard garantiert, um den Wert modulo UINT_MAX + 1 beizubehalten. Die Bedingung überprüft also genau, was ich will, und wird auf keinem System, auf das ich wahrscheinlich stoße, zu nichts kompiliert.

Allerdings ... Ich bin immer noch dabei, intohne vorher zu prüfen, ob es ein implementierungsdefiniertes Verhalten hervorruft. Auf einem hypothetischen System im Jahr 2050 könnte es wer-weiß-was tun. Nehmen wir also an, ich möchte das vermeiden.

Frage: Wie soll mein "dritter Versuch" aussehen?

Um es noch einmal zusammenzufassen: Ich möchte:

• Umwandlung von unsigned int in signated int
• Behalten Sie den Wert mod UINT_MAX + 1 bei
• Rufen Sie nur Standardverhalten auf
• Kompilieren Sie auf einem typischen Zwei-Komplement-Computer mit optimiertem Compiler zu einem No-Op

[Aktualisieren]

Lassen Sie mich ein Beispiel geben, um zu zeigen, warum dies keine triviale Frage ist.

Stellen Sie sich eine hypothetische C ++ - Implementierung mit den folgenden Eigenschaften vor:

• sizeof(int) gleich 4
• sizeof(unsigned) gleich 4
• INT_MAX entspricht 32767
• INT_MINgleich -2 ³² + 32768
• UINT_MAXgleich 2 ³² - 1
• Arithmetik intist Modulo 2 ³² (in den Bereich INT_MINdurch INT_MAX)
• std::numeric_limits<int>::is_modulo ist wahr
• Das Casting ohne Vorzeichen nin int behält den Wert für 0 <= n <= 32767 bei und ergibt ansonsten Null

Bei dieser hypothetischen Implementierung gibt es genau einen intkongruenten Wert (mod UINT_MAX + 1) für jeden unsignedWert. Meine Frage wäre also klar definiert.

Ich behaupte, dass diese hypothetische C ++ - Implementierung vollständig den Spezifikationen von C ++ 98, C ++ 03 und C ++ 11 entspricht. Ich gebe zu, dass ich nicht jedes Wort von allen auswendig gelernt habe ... Aber ich glaube, ich habe die relevanten Abschnitte sorgfältig gelesen. Wenn Sie also möchten, dass ich Ihre Antwort akzeptiere, müssen Sie entweder (a) eine Spezifikation zitieren, die diese hypothetische Implementierung ausschließt, oder (b) sie korrekt behandeln.

In der Tat muss eine korrekte Antwort jede vom Standard zugelassene hypothetische Implementierung behandeln. Das ist per Definition "nur standardmäßiges Verhalten aufrufen".

Beachten Sie übrigens, dass dies std::numeric_limits<int>::is_modulohier aus mehreren Gründen völlig nutzlos ist. Zum einen kann dies trueauch dann der Fall sein , wenn Casts ohne Vorzeichen für große Werte ohne Vorzeichen nicht funktionieren. Zum anderen kann es sich truesogar um ein Komplement- oder ein Vorzeichengrößen-System handeln, wenn die Arithmetik einfach über den gesamten ganzzahligen Bereich modulo ist. Und so weiter. Wenn Ihre Antwort von abhängt is_modulo, ist es falsch.

[Update 2]

Die Antwort von hvd hat mir etwas beigebracht: Meine hypothetische C ++ - Implementierung für Ganzzahlen ist im modernen C nicht zulässig. Die Standards C99 und C11 sind sehr spezifisch in Bezug auf die Darstellung vorzeichenbehafteter Ganzzahlen. in der Tat erlauben sie nur Zweierkomplement, Einkomplement und Vorzeichengröße (Abschnitt 6.2.6.2 Absatz (2);).

Aber C ++ ist nicht C. Wie sich herausstellt, steht diese Tatsache im Mittelpunkt meiner Frage.

Der ursprüngliche C ++ 98-Standard basierte auf dem viel älteren C89, der besagt (Abschnitt 3.1.2.5):

Für jeden der vorzeichenbehafteten Integer-Typen gibt es einen entsprechenden (aber unterschiedlichen) vorzeichenlosen Integer-Typ (gekennzeichnet mit dem Schlüsselwort unsigned), der dieselbe Speichermenge (einschließlich Vorzeicheninformationen) verwendet und dieselben Ausrichtungsanforderungen hat. Der Bereich nichtnegativer Werte eines vorzeichenbehafteten Ganzzahltyps ist ein Unterbereich des entsprechenden vorzeichenlosen Ganzzahltyps, und die Darstellung desselben Werts in jedem Typ ist dieselbe.

C89 sagt nichts darüber aus, nur ein Vorzeichenbit zu haben oder nur Zweierkomplement / Einkomplement / Vorzeichengröße zuzulassen.

Der C ++ 98-Standard hat diese Sprache fast wörtlich übernommen (Abschnitt 3.9.1 Absatz (3)):

Für jeden der vorzeichenbehafteten Ganzzahltypen gibt es einen entsprechenden (aber unterschiedlichen) vorzeichenlosen Ganzzahltyp : " unsigned char", " unsigned short int", " unsigned int" und " unsigned long int", von denen jeder dieselbe Speichermenge belegt und dieselben Ausrichtungsanforderungen hat (3.9 ) als entsprechenden vorzeichenbehafteten Integer-Typ; Das heißt, jeder vorzeichenbehaftete Ganzzahltyp hat dieselbe Objektdarstellung wie sein entsprechender vorzeichenloser Ganzzahltyp . Der Bereich nichtnegativer Werte eines vorzeichenbehafteten Ganzzahltyps ist ein Unterbereich des entsprechenden vorzeichenlosen Ganzzahltyps, und die Wertdarstellung jedes entsprechenden vorzeichenbehafteten / vorzeichenlosen Typs muss gleich sein.

Der C ++ 03-Standard verwendet im Wesentlichen dieselbe Sprache wie C ++ 11.

Soweit ich das beurteilen kann, beschränkt keine Standard-C ++ - Spezifikation ihre vorzeichenbehafteten Ganzzahldarstellungen auf eine C-Spezifikation. Und es gibt nichts, was ein einzelnes Vorzeichenbit oder etwas Ähnliches vorschreibt. Es heißt nur, dass nicht negativ vorzeichenbehaftete Ganzzahlen ein Unterbereich der entsprechenden vorzeichenlosen Ganzzahlen sein müssen.

Also wieder behaupte ich, dass INT_MAX = 32767 mit INT_MIN = -2 ³² +32768 erlaubt ist. Wenn Ihre Antwort etwas anderes voraussetzt, ist sie falsch, es sei denn, Sie zitieren einen C ++ - Standard, der mich als falsch erweist.

Erweitern der Antwort von user71404:

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
}

Wenn x >= INT_MIN(beachten Sie die Promotion-Regeln, INT_MINwird konvertiert in unsigned), dann x - INT_MIN <= INT_MAXhat dies keinen Überlauf.

Wenn dies nicht offensichtlich ist, werfen Sie einen Blick auf die Behauptung "Wenn x >= -4u, dann x + 4 <= 3." Und denken Sie daran, dass INT_MAXdiese mindestens dem mathematischen Wert von -INT_MIN - 1 entspricht.

Auf den gängigsten Systemen, wo !(x <= INT_MAX)schon sagt x >= INT_MIN, soll das Optimierungsprogramm der Lage sein (und auf meinem System ist in der Lage) , um die zweite Prüfung zu entfernen, zu bestimmen , dass die beiden returnAussagen können auf den gleichen Code kompiliert werden, und entfernen Sie auch die erste Prüfung. Generierte Baugruppenliste:

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

Die hypothetische Umsetzung in Ihrer Frage:

• INT_MAX entspricht 32767
• INT_MIN entspricht -2 ³² + 32768

ist nicht möglich, bedarf daher keiner besonderen Berücksichtigung. INT_MINwird gleich entweder -INT_MAXoder sein -INT_MAX - 1. Dies folgt aus der Darstellung von Ganzzahltypen durch C (6.2.6.2), bei der nBits Wertbits und ein Bit Vorzeichenbit sein müssen und nur eine einzige Trap-Darstellung zulässig ist (ohne Darstellungen, die aufgrund von Füllbits ungültig sind). nämlich derjenige, der sonst eine negative Null darstellen würde -INT_MAX - 1. C ++ erlaubt keine ganzzahligen Darstellungen, die über das hinausgehen, was C erlaubt.

Update : Der Microsoft-Compiler bemerkt das anscheinend nichtx > 10undx >= 11testet dasselbe. Es generiert nur dann den gewünschten Code, wenn erx >= INT_MINdurch ersetzt wirdx > INT_MIN - 1u, den es als Negation vonx <= INT_MAX(auf dieser Plattform) erkennen kann.

[Update von Fragesteller (Nemo), der auf unsere Diskussion weiter unten eingeht]

Ich glaube jetzt, dass diese Antwort in allen Fällen funktioniert, aber aus komplizierten Gründen. Ich werde wahrscheinlich das Kopfgeld für diese Lösung vergeben, aber ich möchte alle wichtigen Details erfassen, falls es jemanden interessiert.

Beginnen wir mit C ++ 11, Abschnitt 18.3.3:

Tabelle 31 beschreibt den Header <climits>.

...

Der Inhalt entspricht dem Standard C-Bibliotheksheader <limits.h>.

Hier bedeutet "Standard C" C99, dessen Spezifikation die Darstellung vorzeichenbehafteter Ganzzahlen stark einschränkt. Sie sind wie vorzeichenlose Ganzzahlen, jedoch mit einem Bit für "Vorzeichen" und null oder mehr Bits für "Auffüllen". Die Füllbits tragen nicht zum Wert der ganzen Zahl bei, und das Vorzeichenbit trägt nur als Zweierkomplement, Einkomplement oder Vorzeichengröße bei.

Da C ++ 11 die <climits>Makros von C99 erbt , ist INT_MIN entweder -INT_MAX oder -INT_MAX-1, und der Code von hvd funktioniert garantiert. (Beachten Sie, dass INT_MAX aufgrund der Auffüllung viel kleiner sein kann als UINT_MAX / 2 ... Aber dank der Funktionsweise von signierten-> nicht signierten Casts wird diese Antwort in Ordnung gebracht.)

C ++ 03 / C ++ 98 ist schwieriger. Es verwendet den gleichen Wortlaut, um <climits>von "Standard C" zu erben , aber jetzt bedeutet "Standard C" C89 / C90.

Alle diese - C ++ 98, C ++ 03, C89 / C90 - haben den Wortlaut, den ich in meiner Frage gebe, enthalten aber auch diesen (C ++ 03 Abschnitt 3.9.1 Absatz 7):

Die Darstellungen von Integraltypen müssen Werte unter Verwendung eines reinen binären Zahlensystems definieren. (44) [ Beispiel : Diese Internationale Norm erlaubt 2-Komplement-, 1-Komplement- und vorzeichenbehaftete Größenrepräsentationen für Integraltypen.]

Fußnote (44) definiert "reines binäres Zahlensystem":

Eine Positionsdarstellung für Ganzzahlen, die die Binärziffern 0 und 1 verwendet, wobei die durch aufeinanderfolgende Bits dargestellten Werte additiv sind, mit 1 beginnen und mit der aufeinanderfolgenden Integralleistung von 2 multipliziert werden, außer vielleicht für das Bit mit der höchsten Position.

Das Interessante an dieser Formulierung ist, dass sie sich selbst widerspricht, da die Definition des "reinen binären Zahlensystems" keine Darstellung von Vorzeichen / Größe zulässt! Es erlaubt dem hohen Bit, beispielsweise den Wert -2 ^n-1 (Zweierkomplement) oder - (2 ^n-1 -1) (Einerkomplement) zu haben. Es gibt jedoch keinen Wert für das hohe Bit, das zu Vorzeichen / Größe führt.

Wie auch immer, meine "hypothetische Implementierung" qualifiziert sich unter dieser Definition nicht als "rein binär", so dass dies ausgeschlossen ist.

Die Tatsache, dass das hohe Bit etwas Besonderes ist, bedeutet jedoch, dass wir uns vorstellen können, dass es überhaupt einen Wert beisteuert: einen kleinen positiven Wert, einen großen positiven Wert, einen kleinen negativen Wert oder einen großen negativen Wert. (Wenn das Vorzeichenbit - (2 ^n-1 -1) beitragen kann , warum nicht - (2 ^n-1 -2)? Usw.)

Stellen wir uns also eine vorzeichenbehaftete Ganzzahldarstellung vor, die dem "Vorzeichen" -Bit einen verrückten Wert zuweist.

Ein kleiner positiver Wert für das Vorzeichenbit würde zu einem positiven Bereich für int(möglicherweise so groß wie unsigned) führen, und der Code von hvd behandelt dies einwandfrei.

Ein großer positiver Wert für das Vorzeichenbit würde zu inteinem Maximum führen, das größer als ist unsigned, was verboten ist.

Ein großer negativer Wert für das Vorzeichenbit würde dazu führen int, dass ein nicht zusammenhängender Wertebereich dargestellt wird, und andere Formulierungen in der Spezifikation schließen dies aus.

Wie wäre es schließlich mit einem Vorzeichenbit, das eine kleine negative Menge beisteuert? Könnten wir eine 1 im "Vorzeichenbit" haben, die beispielsweise -37 zum Wert des int beiträgt? Dann wäre INT_MAX (sagen wir) 2 ³¹ -1 und INT_MIN wäre -37?

Dies würde dazu führen, dass einige Zahlen zwei Darstellungen haben ... Aber Ein-Komplement gibt zwei Darstellungen zu Null, und das ist gemäß dem "Beispiel" erlaubt. Nirgends sagt die Spezifikation, dass Null die einzige Ganzzahl ist, die zwei Darstellungen haben könnte. Ich denke, diese neue Hypothese wird von der Spezifikation zugelassen.

In der Tat -INT_MAX-1scheint jeder negative Wert von -1 bis zu als Wert für das "Vorzeichenbit" zulässig zu sein, aber nichts kleineres (damit der Bereich nicht zusammenhängend ist). Mit anderen Worten, INT_MINkönnte alles von -INT_MAX-1bis -1 sein.

Weißt du was? Für die zweite Umwandlung im Code von hvd, um ein implementierungsdefiniertes Verhalten zu vermeiden, benötigen wir nur x - (unsigned)INT_MINweniger als oder gleich INT_MAX. Wir haben gerade gezeigt, INT_MINist zumindest -INT_MAX-1. Offensichtlich xist höchstens UINT_MAX. Das Umwandeln einer negativen Zahl in ein vorzeichenloses Zeichen entspricht dem Hinzufügen UINT_MAX+1. Alles zusammen:

x - (unsigned)INT_MIN <= INT_MAX

dann und nur dann, wenn

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

Das letzte haben wir gerade gezeigt, und selbst in diesem perversen Fall funktioniert der Code tatsächlich.

Das erschöpft alle Möglichkeiten und beendet damit diese äußerst akademische Übung.

Fazit: In C89 / C90 gibt es ein stark unterbestimmtes Verhalten für vorzeichenbehaftete Ganzzahlen, das von C ++ 98 / C ++ 03 geerbt wurde. Es ist in C99 behoben, und C ++ 11 erbt das Update indirekt durch Einbindung <limits.h>von C99. Aber auch C ++ 11 behält den widersprüchlichen Wortlaut "reine binäre Darstellung" bei ...

Dieser Code basiert nur auf dem von der Spezifikation vorgeschriebenen Verhalten, sodass die Anforderung (a) leicht erfüllt werden kann:

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

Mit Anforderung (b) ist es nicht so einfach. Dies wird mit gcc 4.6.3 (-Os, -O2, -O3) und mit clang 3.0 (-Os, -O, -O2, -O3) zu einem No-Op kompiliert. Intel 12.1.0 weigert sich, dies zu optimieren. Und ich habe keine Informationen über Visual C.

Die ursprüngliche Antwort löste das Problem nur für unsigned=> int. Was ist, wenn wir das allgemeine Problem "eines vorzeichenlosen Typs" in den entsprechenden vorzeichenbehafteten Typ lösen wollen? Darüber hinaus war die ursprüngliche Antwort hervorragend darin, Abschnitte des Standards zu zitieren und einige Eckfälle zu analysieren, aber es hat mir nicht wirklich geholfen, ein Gefühl dafür zu bekommen, warum es funktioniert, sodass diese Antwort versuchen wird, eine starke konzeptionelle Grundlage zu geben. Diese Antwort wird versuchen, das "Warum" zu erklären und moderne C ++ - Funktionen zu verwenden, um den Code zu vereinfachen.

C ++ 20 Antwort

Das Problem hat sich mit P0907 dramatisch vereinfacht: Vorzeichenbehaftete Ganzzahlen sind das Zweierkomplement und der endgültige Wortlaut P1236 , der in den C ++ 20-Standard aufgenommen wurde. Jetzt ist die Antwort so einfach wie möglich:

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

Das ist es. Eine static_castBesetzung (oder eine Besetzung im C-Stil) wird garantiert das tun, was Sie für diese Frage benötigen, und das, was viele Programmierer immer dachten.

C ++ 17 Antwort

In C ++ 17 sind die Dinge viel komplizierter. Wir müssen uns mit drei möglichen ganzzahligen Darstellungen befassen (Zweierkomplement, Einerkomplement und Vorzeichengröße). Selbst in dem Fall, in dem wir wissen, dass es sich um ein Zweierkomplement handeln muss, weil wir den Bereich möglicher Werte überprüft haben, liefert die Konvertierung eines Werts außerhalb des Bereichs der vorzeichenbehafteten Ganzzahl in diese vorzeichenbehaftete Ganzzahl immer noch ein implementierungsdefiniertes Ergebnis. Wir müssen Tricks anwenden, wie wir sie in anderen Antworten gesehen haben.

Hier ist zunächst der Code, wie das Problem generisch gelöst werden kann:

template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
constexpr auto cast_to_signed_integer(T const value) {
    using unsigned_t = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
    using signed_t = std::make_signed_t<unsigned_t>;
    using result_t = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result_t>;
    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_t>(value);
    } else {
        constexpr auto window = static_cast<signed_t>(result_limits::min());
        return static_cast<result_t>( // cast to the type we want the result in
            static_cast<signed_t>( // cast back to signed or we end up with our original value
                static_cast<T>( // cast to unsigned to force modular reduction
                    static_cast<unsigned_t>(value) + // cast to avoid promotion to int
                    static_cast<unsigned_t>(window) // shift values to overlapping range, cast to silence warning
                )
            ) + window // shift values to negative range
        );
    }
}

Dies hat ein paar mehr Casts als die akzeptierte Antwort, um sicherzustellen, dass keine signierten / nicht signierten Mismatch-Warnungen von Ihrem Compiler vorhanden sind, und um die Regeln für die Ganzzahl-Promotion ordnungsgemäß zu handhaben.

Wir haben zuerst einen Sonderfall für Systeme, die keine Zweierkomplemente sind (und daher müssen wir den maximal möglichen Wert behandeln, insbesondere weil es nichts gibt, dem wir zuordnen können). Danach kommen wir zum eigentlichen Algorithmus.

Die zweite Bedingung der obersten Ebene ist unkompliziert: Wir wissen, dass der Wert kleiner oder gleich dem Maximalwert ist, sodass er in den Ergebnistyp passt. Die dritte Bedingung ist trotz der Kommentare etwas komplizierter, daher würden einige Beispiele wahrscheinlich helfen, zu verstehen, warum jede Aussage notwendig ist.

Konzeptionelle Basis: die Zahlenreihe

Was ist dieses windowKonzept? Betrachten Sie die folgende Zahlenreihe:

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

Es stellt sich heraus, dass Sie für Zweierkomplement-Ganzzahlen die Teilmenge der Zahlenlinie, die von beiden Typen erreicht werden kann, in drei gleich große Kategorien unterteilen können:

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

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

Dies kann leicht unter Berücksichtigung der Darstellung nachgewiesen werden. Eine vorzeichenlose Ganzzahl beginnt bei 0und verwendet alle Bits, um den Wert in Potenzen von 2 zu erhöhen. Eine vorzeichenbehaftete Ganzzahl ist für alle Bits genau gleich, mit Ausnahme des Vorzeichenbits, das -(2^position)anstelle von wert ist 2^position. Dies bedeutet, dass sie für alle n - 1Bits dieselben Werte darstellen. Dann haben vorzeichenlose Ganzzahlen ein weiteres normales Bit, das die Gesamtzahl der Werte verdoppelt (mit anderen Worten, es gibt genauso viele Werte mit diesem gesetzten Bit wie ohne gesetztes Bit). Die gleiche Logik gilt für vorzeichenbehaftete Ganzzahlen, außer dass alle Werte mit diesem gesetzten Bit negativ sind.

Die beiden anderen legalen Ganzzahldarstellungen, das Komplement und die Vorzeichengröße, haben alle dieselben Werte wie die Komplement-Ganzzahlen von zwei, mit einer Ausnahme: dem negativsten Wert. C ++ definiert alles über ganzzahlige Typen mit Ausnahme von reinterpret_cast(und C ++ 20 std::bit_cast) in Bezug auf den Bereich darstellbarer Werte, nicht in Bezug auf die Bitdarstellung. Dies bedeutet, dass unsere Analyse für jede dieser drei Darstellungen gilt, solange wir nie versuchen, die Trap-Darstellung zu erstellen. Der vorzeichenlose Wert, der diesem fehlenden Wert zugeordnet werden würde, ist ziemlich unglücklich: der Wert genau in der Mitte der vorzeichenlosen Werte. Glücklicherweise prüft unsere erste Bedingung (zur Kompilierungszeit), ob eine solche Darstellung vorhanden ist, und behandelt sie dann speziell mit einer Laufzeitprüfung.

Die windowVariable im Code ist die Größe jedes dieser Segmente (wir verwenden den negativen Wert, damit er als vorzeichenbehaftete Ganzzahl dargestellt werden kann). Die erste Bedingung behandelt den Fall, in dem wir uns in dem =Abschnitt befinden, was bedeutet, dass wir uns in dem überlappenden Bereich befinden, in dem die Werte in einem ohne Änderung im anderen dargestellt werden können. Wenn wir uns außerhalb dieser Region befinden (wir befinden uns in der +Region), müssen wir um eine Fenstergröße nach unten springen. Dies versetzt uns in den überlappenden Bereich, was bedeutet, dass wir sicher von vorzeichenlos in signiert konvertieren können, da sich der Wert nicht ändert. Wir sind jedoch noch nicht fertig, da wir jedem vorzeichenbehafteten Wert zwei vorzeichenlose Werte zugeordnet haben. Daher müssen wir zum nächsten Fenster (der -Region) wechseln, damit wir wieder eine eindeutige Zuordnung haben.

Gibt uns dies einen kongruenten Mod UINT_MAX + 1, wie in der Frage gefordert? UINT_MAX + 1ist äquivalent zu 2^n, wobei ndie Anzahl der Bits in der Wertdarstellung ist. Der Wert, den wir für unsere Fenstergröße verwenden, ist gleich 2^(n - 1)(der endgültige Index in einer Folge von Werten ist eins kleiner als die Größe). Wir subtrahieren diesen Wert zweimal, was bedeutet, dass wir subtrahieren, 2 * 2^(n - 1)was gleich ist 2^n. Das Addieren und Subtrahieren xist im arithmetischen Mod ein No-Op x, daher haben wir den ursprünglichen Wert-Mod nicht beeinflusst 2^n.

Ordnungsgemäßer Umgang mit ganzzahligen Werbeaktionen

Da dies eine generische Funktion ist und nicht nur intund unsigned, müssen wir uns auch mit integralen Werberegeln befassen. Es gibt zwei möglicherweise interessante Fälle: einen, der shortkleiner als intund einer, der shortdie gleiche Größe wie hat int.

Beispiel: shortkleiner alsint

Wenn shortes kleiner als int(auf modernen Plattformen üblich) ist, wissen wir auch, dass unsigned shortes in eine passen kann int, was bedeutet, dass alle Operationen darauf tatsächlich stattfinden. Deshalb inthaben wir explizit auf den heraufgestuften Typ umgestellt , um dies zu vermeiden. Unsere abschließende Aussage ist ziemlich abstrakt und wird leichter zu verstehen, wenn wir reale Werte einsetzen. Für unseren ersten interessanten Fall ohne Verlust der Allgemeinheit betrachten wir ein 16-Bit shortund ein 17-Bit int(was nach den neuen Regeln immer noch zulässig ist und nur bedeuten würde, dass mindestens einer dieser beiden ganzzahligen Typen einige Füllbits aufweist ):

constexpr auto window = static_cast<int17_t>(result_limits::min());
return static_cast<int16_t>(
    static_cast<int17_t>(
        static_cast<uint16_t>(
            static_cast<uint17_t>(value) +
            static_cast<uint17_t>(window)
        )
    ) + window
);

Auflösen nach dem größtmöglichen vorzeichenlosen 16-Bit-Wert

constexpr auto window = int17_t(-32768);
return int16_t(
    int17_t(
        uint16_t(
            uint17_t(65535) +
            uint17_t(window)
        )
    ) + window
);

Vereinfacht zu

return int16_t(
    int17_t(
        uint16_t(
            uint17_t(65535) +
            uint17_t(32768)
        )
    ) +
    int17_t(-32768)
);

Vereinfacht zu

return int16_t(
    int17_t(
        uint16_t(
            uint17_t(98303)
        )
    ) +
    int17_t(-32768)
);

Vereinfacht zu

return int16_t(
    int17_t(
        uint16_t(32767)
    ) +
    int17_t(-32768)
);

Vereinfacht zu

return int16_t(-1);

Wir setzen das größtmögliche unsignierte ein und kommen zurück -1, Erfolg! Wir können in jedem dieser Schritte sehen, wie etwas Schlimmes passieren würde, wenn wir nicht jede Besetzung an Ort und Stelle hätten.

Beispiel: shortgleiche Größe wieint

Wenn shortes die gleiche Größe wie int(auf modernen Plattformen ungewöhnlich) hat, unterscheiden sich die Regeln für die integrale Werbung geringfügig. In diesem Fall shortfördert zu intund unsigned shortfördert zu unsigned. Glücklicherweise wandeln wir jedes Ergebnis explizit in den Typ um, in dem wir die Berechnung durchführen möchten, sodass wir keine problematischen Werbeaktionen erhalten. Betrachten wir ohne Verlust der Allgemeinheit ein 16-Bit shortund ein 16-Bit int:

constexpr auto window = static_cast<int16_t>(result_limits::min());
return static_cast<int16_t>(
    static_cast<int16_t>(
        static_cast<uint16_t>(
            static_cast<uint16_t>(value) +
            static_cast<uint16_t>(window)
        )
    ) + window
);

Auflösen nach dem größtmöglichen vorzeichenlosen 16-Bit-Wert

return int16_t(
    int16_t(
        uint16_t(
            uint16_t(65535) +
            uint16_t(32768)
        )
    ) +
    int16_t(-32768)
);

Vereinfacht zu

return int16_t(
    int16_t(32767) + int16_t(-32768)
);

Vereinfacht zu

return int16_t(-1);

Wir setzen das größtmögliche unsignierte ein und kommen zurück -1, Erfolg!

Was passiert , wenn ich nur Sorge um intund unsignedund Sie über Warnungen sich nicht, wie die ursprüngliche Frage?

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

Sehen Sie es live

https://godbolt.org/z/AmLazZ

Hier sehen wir, dass clang, gcc und icc bei -O2und -O3keinen Code generieren und MSVC bei keinen Code generiert /O2, sodass die Lösung optimal ist.

Sie können dem Compiler explizit mitteilen, was Sie tun möchten:

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

Kompiliert mit gcc 4.7.2for x86_64-linux( g++ -O -S test.cpp) to

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

Wenn xist unser Input ...

Wenn x > INT_MAXwollen wir eine Konstante finden , kdass eine solche 0< x - k*INT_MAX< INT_MAX.

Das ist einfach - unsigned int k = x / INT_MAX;. Dann lassunsigned int x2 = x - k*INT_MAX;

Wir können jetzt werfen x2zu intsicher. Lassenint x3 = static_cast<int>(x2);

Wir wollen jetzt so etwas wie UINT_MAX - k * INT_MAX + 1von subtrahieren x3, wenn k > 0.

Auf einem 2s-Komplementsystem funktioniert dies, solange x > INT_MAX:

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

Beachten Sie, dass UINT_MAX+1in C ++ garantiert Null ist, die Konvertierung in int ein Noop war und wir subtrahierten und k*INT_MAXdann wieder auf "den gleichen Wert" addierten. Ein akzeptabler Optimierer sollte also in der Lage sein, all diese Dummheiten zu löschen!

Das lässt das Problem von x > INT_MAXoder nicht. Nun, wir erstellen zwei Zweige, einen mit x > INT_MAXund einen ohne. Derjenige ohne macht einen Strait Cast, den der Compiler zu einem Noop optimiert. Der mit ... macht ein Noop, nachdem der Optimierer fertig ist. Der intelligente Optimierer realisiert beide Zweige auf dieselbe Weise und löscht den Zweig.

Probleme: Wenn UINT_MAXes im Vergleich zu wirklich groß ist INT_MAX, funktioniert das oben Genannte möglicherweise nicht. Ich gehe davon k*INT_MAX <= UINT_MAX+1implizit aus.

Wir könnten dies wahrscheinlich mit einigen Aufzählungen angreifen wie:

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

Ich glaube, welche 2 und 1 auf einem 2s-Komplementsystem funktionieren (sind wir garantiert, dass diese Mathematik funktioniert? Das ist schwierig ...) und eine Logik basierend auf diesen, die sich leicht auf Nicht-2s-Komplementsystemen optimieren lässt ...

Dies öffnet auch den Ausnahmefall. Es ist nur möglich, wenn UINT_MAX viel größer als (INT_MIN-INT_MAX) ist, sodass Sie Ihren Ausnahmecode in einen if-Block einfügen können, der genau diese Frage stellt, und Sie auf einem herkömmlichen System nicht verlangsamen.

Ich bin mir nicht ganz sicher, wie ich diese Konstanten zur Kompilierungszeit konstruieren soll, um damit richtig umzugehen.

std::numeric_limits<int>::is_moduloist eine Kompilierungszeitkonstante. Sie können es also für die Vorlagenspezialisierung verwenden. Problem gelöst, zumindest wenn der Compiler mit Inlining spielt.

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

Ich denke, der int-Typ ist mindestens zwei Bytes, so dass sich INT_MIN und INT_MAX auf verschiedenen Plattformen ändern können.

Grundtypen

≤climits≥ header

Mein Geld ist für die Verwendung von memcpy. Jeder anständige Compiler weiß, wie man es wegoptimiert:

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

Für mich (Xcode 8.3.2, Apple LLVM 8.1, -O3) ergibt sich Folgendes:

_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