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?

Question 1

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?

Question 2

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.

Question 3

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)

Question 4

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++).

Question 5

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.

Question 6

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.

Question 7

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).

Question 8

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.