Wenn ich eine vorzeichenlose ganze Zahl auf die nächste kleinere oder gleiche gerade ganze Zahl runden möchte, kann ich dann durch 2 dividieren und dann mit 2 multiplizieren?

Lesezeit: 9 Minuten

Benutzeravatar von user2370139
Benutzer2370139

Zum Beispiel :

f(8)=8
f(9)=8

Kann ich tun x = x/2*2; ? Besteht die Gefahr, dass der Compiler einen solchen Ausdruck wegoptimiert?

  • Optimierungen dürfen die Ergebnisse einer wohldefinierten Operation nicht ändern.

    – Barmar

    24. Oktober 2017 um 18:44 Uhr

  • Empfehlen Sie dringend die Verwendung von: x >>= 1; x <<= 1;

    – Benutzer3629249

    24. Oktober 2017 um 22:12 Uhr

  • @ user3629249 Warum es dringend empfehlen? Es drückt die Absicht weniger klar aus als der bereits in der Frage enthaltene Code, es wird zu identischem Maschinencode kompiliert, sodass es nicht schneller ist, und es gibt kein Analogon, wenn Sie auf das nächste Vielfache einer anderen Zahl als 2 runden möchten (es sei denn, diese Zahl auch ist zufällig eine Potenz von 2).

    – Arthur Tacca

    25. Oktober 2017 um 7:36 Uhr

  • weil es schneller ist, kein multiplizieren und dividieren. Ein VIEL einfacherer Weg ist einfach zu verwenden: x &= ~(1)' Where the 1` könnte eine Zeichenfolge aus Einsen der gewünschten Länge sein. Zum Beispiel: x &= ~(0x07); für drei Bits usw

    – Benutzer3629249

    26. Oktober 2017 um 2:12 Uhr

  • Wenn beide Methoden zu denselben Maschinenbefehlen führen, müssen Sie die Optimierung auf das Maximum einstellen.

    – Benutzer3629249

    26. Oktober 2017 um 2:13 Uhr

Benutzeravatar von Bathsheba
Bathseba

Der Compiler darf beliebige Optimierungen vornehmen, solange es keine Seiteneffekte in das Programm bringt. In Ihrem Fall können die 2er nicht gelöscht werden, da der Ausdruck dann einen anderen Wert für ungerade Zahlen hat.

x / 2 * 2 ausgewertet wird streng wie (x / 2) * 2und x / 2 wird in ganzzahliger Arithmetik durchgeführt, wenn x ist ein ganzzahliger Typ.

Dies ist tatsächlich eine idiomatische Rundungstechnik.

  • Ich mag die Anmerkung, dass dies idiomatisch ist. Es ist meiner Meinung nach auch etwas intuitiver als eine Maske.

    – StoryTeller – Unslander Monica

    18. Oktober 2017 um 7:54 Uhr

  • Natürlich der Compiler ist erlaubt, diese richtig zu optimieren, zB durch Ersetzen mit (x>>1)<<1. IIRC, es gibt Compiler, die dies auch dann tun, wenn Optimierungen technisch ausgeschaltet sind.

    – MSalter

    18. Oktober 2017 um 8:05 Uhr

  • @MSalters: Ja, es war dumm, das zu sagen. Ich habe geändert.

    – Bathseba

    18. Oktober 2017 um 8:07 Uhr

  • @MSalters: Oder im Fall von unsigned (x & 0xfffffffe) 🙂

    – Matthias M.

    18. Oktober 2017 um 12:41 Uhr

  • @Voo: Warum? Es ist eine Ganzzahl ohne Vorzeichen. Das Verhalten ist per Definition identisch.

    – MSalter

    20. Oktober 2017 um 7:06 Uhr

StoryTeller - Benutzeravatar von Unslander Monica
StoryTeller – Unslander Monica

Da Sie angegeben haben, dass die Ganzzahlen vorzeichenlos sind, können Sie dies mit einer einfachen Maske tun:

x & (~1u)

Dadurch wird das LSB auf Null gesetzt, wodurch die unmittelbare gerade Zahl erzeugt wird, die nicht größer als ist x. Das heißt, wenn x hat einen Typ, der nicht breiter als ein ist unsigned int.

Du kannst das natürlich erzwingen 1 vom gleichen Typ wie ein breiter sein xso was:

x & ~((x & 1u) | 1u)

Aber an diesem Punkt sollten Sie diesen Ansatz wirklich als eine Übung in Verschleierung betrachten und Bathsebas Antwort akzeptieren.


Ich habe natürlich die Standardbibliothek vergessen. Wenn Sie einschließen stdint.h (oder cstdint, wie Sie es in C++-Code tun sollten). Die Details können Sie der Implementierung überlassen:

uintmax_t const lsb = 1;
x & ~lsb;

oder

x & ~UINTMAX_C(1)

  • Brauchst du nicht x & (~static_cast<decltype(x)>(1)) oder brauche ich einen Kaffee?

    – Bathseba

    18. Oktober 2017 um 7:54 Uhr


  • @Bathsheba – Dann brauche ich definitiv einen Kaffee. Mmm … Ich habe nicht viel darüber nachgedacht, mit einem vorzeichenlosen Integer-Typ zu arbeiten.

    – StoryTeller – Unslander Monica

    18. Oktober 2017 um 7:58 Uhr

  • @Bathsheba – Ich würde, aber dieses C-Tag … Ich möchte irgendwie darüber nachdenken und ganz cool sein, indem ich eine Lösung erstelle, die sowohl in C als auch in C ++ funktioniert.

    – StoryTeller – Unslander Monica

    18. Oktober 2017 um 8:00 Uhr

  • @Bathsheba – Aber nur bis zu UINT_MAX, nein? Wir sind immer noch im selben Boot, wenn x ist unsigned longICH denken.

    – StoryTeller – Unslander Monica

    18. Oktober 2017 um 8:03 Uhr

  • Ich fürchte x & (~1u) funktioniert nicht, wenn der Typ x ist größer als unsigned int. Umgekehrt, x & ~1 würde sich für alle Typen wie erwartet verhalten. Dies ist eine kontraintuitive Falle. Wenn Sie darauf bestehen, eine vorzeichenlose Konstante zu verwenden, müssen Sie schreiben x & ~(uintmax_t)1 wie eben x & ~1ULL würde scheitern, wenn x hat einen größeren Typ als unsigned long long. Um die Sache noch schlimmer zu machen, haben viele Plattformen jetzt größere Integer-Typen als uintmax_twie zum Beispiel __uint128_t.

    – chqrlie

    18. Oktober 2017 um 9:31 Uhr

C und C++ verwenden im Allgemeinen die „Als-ob“-Regel bei der Optimierung. Das Berechnungsergebnis muss sein als ob Der Compiler hat Ihren Code nicht optimiert.

In diesem Fall, 9/2*2=8. Der Compiler kann jede Methode verwenden, um das Ergebnis 8 zu erzielen. Dazu gehören Bitmasken, Bitverschiebungen oder jeder CPU-spezifische Hack, der die gleichen Ergebnisse liefert (x86 hat einige Tricks, die darauf beruhen, dass es nicht zwischen Zeigern unterscheidet und ganze Zahlen, im Gegensatz zu C und C++).

  • Fall und Punkt. Damit produziert GCC -O1. Alle Ansätze sind auf denselben Maschinencode destilliert.

    – StoryTeller – Unslander Monica

    18. Oktober 2017 um 8:37 Uhr

  • Und wie ich vermutet habe, für alle 3 Varianten wird das GCC verwenden and RAX, -2 Methode sogar auf -O0.

    – MSalter

    18. Oktober 2017 um 8:41 Uhr

  • GCC ist insofern höchst ungewöhnlich, als es diese Art von mathematischen/bittwiddelnden Peephole-Optimierungen anwendet, selbst wenn Optimierungen deaktiviert sind. Das ist eine Art interessante und bemerkenswerte Design-Eigenart. Andere Compiler führen eine viel wörtlichere Übersetzung des C-Codes in Maschinenanweisungen mit deaktivierter Optimierung durch, aber sobald Sie den Optimierer aktivieren, ist die Ausgabe dieselbe, weshalb Sie den Code für die Lesbarkeit schreiben sollten, es sei denn, Sie wissen sicher, dass Ihre Compiler ist hirntot.

    – Cody Grey

    18. Oktober 2017 um 11:45 Uhr


  • Das Umwandeln einer Abteilung in eine Schicht ist eine Standardoptimierungstechnik, die als “Stärkereduzierung” bekannt ist. Ja, es ist sehr Standard und extrem einfach, aber ich bin anderer Meinung, dass es keine Optimierung ist. @Superkatze

    – Cody Grey

    18. Oktober 2017 um 16:27 Uhr


  • @supercat: Ich stimme hier größtenteils Cody Gray zu. Es ist nicht so sehr die Kraftreduktion; es ist die Tatsache, dass GCC keinen Code für einzelne Ausdrücke generiert. x/2*2 kompiliert zu einer einzigen Anweisung. Im Allgemeinen wird das Kompilieren ohne Optimierungen zu Debugging-Zwecken durchgeführt, und dann möchten Sie eine 1: N-Korrespondenz zwischen Quellcode und Assembly.

    – MSalter

    19. Oktober 2017 um 7:13 Uhr

Benutzeravatar von chqrlie
chqrlie

Du kannst schreiben x / 2 * 2 und der Compiler erzeugt sehr effizienten Code, um das niedrigstwertige Bit zu löschen, wenn x hat einen vorzeichenlosen Typ.

Umgekehrt könnte man schreiben:

x = x & ~1;

Oder wahrscheinlich weniger lesbar:

x = x & -2;

Oder auch

x = (x >> 1) << 1;

Oder auch das:

x = x - (x & 1);

Oder dieser letzte, von supercat vorgeschlagene, der für positive Werte aller ganzzahligen Typen und Darstellungen funktioniert:

x = (x | 1) ^ 1;

Alle obigen Vorschläge funktionieren korrekt für alle vorzeichenlosen Integer-Typen auf Zweierkomplement-Architekturen. Ob der Compiler optimalen Code produziert, ist eine Frage der Konfiguration und der Qualität der Implementierung.

Beachte das aber x & (~1u) funktioniert nicht, wenn der Typ x ist größer als unsigned int. Dies ist eine kontraintuitive Falle. Wenn Sie darauf bestehen, eine vorzeichenlose Konstante zu verwenden, müssen Sie schreiben x & ~(uintmax_t)1 wie eben x & ~1ULL würde scheitern, wenn x hat einen größeren Typ als unsigned long long. Um die Sache noch schlimmer zu machen, haben viele Plattformen jetzt Integer-Typen größer als uintmax_twie zum Beispiel __uint128_t.

Hier ein kleiner Richtwert:

typedef unsigned int T;

T test1(T x) {
    return x / 2 * 2;
}

T test2(T x) {
    return x & ~1;
}

T test3(T x) {
    return x & -2;
}

T test4(T x) {
    return (x >> 1) << 1;
}

T test5(T x) {
    return x - (x & 1);
}

T test6(T x) {  // suggested by supercat
    return (x | 1) ^ 1;
}

T test7(T x) {  // suggested by Mehrdad
    return ~(~x | 1);
}

T test1u(T x) {
    return x & ~1u;
}

Wie von Ruslan vorgeschlagen, testen Sie weiter Godbolts Compiler Explorer zeigt dies für alle oben genannten Alternativen gcc -O1 erzeugt den gleichen genauen Code für unsigned intaber den Typ ändern T zu unsigned long long zeigt abweichenden Code für test1u.

Benutzeravatar von Jens Gustedt
Jens Gustedt

Wenn Ihre Werte, wie Sie sagen, von einem unsignierten Typ sind, ist dies am einfachsten

x & -2;

Die Wunder der vorzeichenlosen Arithmetik machen es dazu -2 wird in den Typ von umgewandelt xund hat ein Bitmuster, das alle Einsen hat, aber für das niedrigstwertige Bit, das ist 0.

Im Gegensatz zu einigen anderen vorgeschlagenen Lösungen sollte dies mit jedem vorzeichenlosen Integer-Typ funktionieren, der mindestens so breit ist wie unsigned. (Und mit schmaleren Typen sollte man sowieso nicht rechnen.)

Als zusätzlicher Bonus wird, wie von Supercat bemerkt, nur die Konvertierung eines vorzeichenbehafteten Typs in einen unsignierten Typ verwendet. Dies ist durch den Standard wohldefiniert als Modulo-Arithmetik. Das Ergebnis ist also immer UTYPE_MAX-1 zum UTYPE der vorzeichenlose Typ von x. Insbesondere ist es für signierte Typen unabhängig von der Zeichendarstellung der Plattform.

  • Es kann erwähnenswert sein, nur um Verwirrung vorzubeugen, dass die Umwandlung von -2 in “unsigned” den “unsigned value” ergibt, der, wenn er zu 2 addiert wird, 0 ergibt. unabhängig davon, ob ein System Zweierkomplement-vorzeichenbehaftete Mathematik verwendet. Hätte man dagegen ein Einerkomplementsystem, wäre ~1 gleich -1, was bei Umwandlung in unsigned einen Wert mit allen gesetzten Bits ergeben würde.

    – Superkatze

    18. Oktober 2017 um 16:15 Uhr

  • @supercat, danke, ja genau. Ich habe versucht, diese Ideen in meine Antwort zu integrieren.

    – Jens Gustedt

    19. Oktober 2017 um 8:28 Uhr

  • Um dies für vorzeichenlose Typen kleiner als unsigned int sicher zu machen, können Sie (1u * x) & -2 verwenden

    – Plugwash

    19. Oktober 2017 um 17:37 Uhr

Benutzeravatar von Arthur Tacca
Arthur Tacca

Eine Option, von der ich überrascht bin, dass sie bisher nicht erwähnt wurde, ist die Verwendung des Modulo-Operators. Ich würde argumentieren, dass dies Ihre Absicht mindestens so gut wiedergibt wie Ihr ursprünglicher Ausschnitt und vielleicht sogar besser.

x = x - x % 2

Wie andere gesagt haben, behandelt der Optimierer des Compilers jeden vernünftigen Ausdruck gleichwertig, also machen Sie sich Gedanken darüber, was klarer ist, als was Ihrer Meinung nach am schnellsten ist. Alle Antworten zum Bit-Tweaking sind interessant, aber Sie sollten definitiv keine davon anstelle von arithmetischen Operatoren verwenden (vorausgesetzt, die Motivation ist Arithmetik und nicht Bit-Tweaking).

  • Es kann erwähnenswert sein, nur um Verwirrung vorzubeugen, dass die Umwandlung von -2 in “unsigned” den “unsigned value” ergibt, der, wenn er zu 2 addiert wird, 0 ergibt, unabhängig davon, ob ein System Zweierkomplement-vorzeichenbehaftete Mathematik verwendet. Hätte man dagegen ein Einerkomplementsystem, wäre ~1 gleich -1, was bei Umwandlung in unsigned einen Wert mit allen gesetzten Bits ergeben würde.

    – Superkatze

    18. Oktober 2017 um 16:15 Uhr

  • @supercat, danke, ja genau. Ich habe versucht, diese Ideen in meine Antwort zu integrieren.

    – Jens Gustedt

    19. Oktober 2017 um 8:28 Uhr

  • Um dies für vorzeichenlose Typen kleiner als unsigned int sicher zu machen, können Sie (1u * x) & -2 verwenden

    – Plugwash

    19. Oktober 2017 um 17:37 Uhr

Benutzeravatar von ivan.ukr
ivan.ukr

verwende einfach folgendes:

template<class T>
inline T f(T v)
{
    return v & (~static_cast<T>(1));
}

Haben Sie keine Angst, dass dies eine Funktion ist, der Compiler sollte dies schließlich in nur v & (~ 1) mit dem entsprechenden Typ von 1 optimieren.

1415900cookie-checkWenn ich eine vorzeichenlose ganze Zahl auf die nächste kleinere oder gleiche gerade ganze Zahl runden möchte, kann ich dann durch 2 dividieren und dann mit 2 multiplizieren?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy