Zitieren des Codes zum Berechnen des ganzzahligen Absolutwerts (abs) ohne Verzweigung von http://graphics.stanford.edu/~seander/bithacks.html:
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;
Patentierte Variante:
r = (v ^ mask) - mask;
Was ist CHAR_BIT
und wie benutzt man es?
CHAR_BIT
ist die Anzahl der Bits in char
. Heutzutage verwenden fast alle Architekturen 8 Bit pro Byte, aber das ist nicht immer der Fall. Einige ältere Maschinen hatten früher 7-Bit-Byte.
Es ist darin zu finden <limits.h>
.
Der Versuch, sowohl die explizite Frage zu beantworten (was ist CHAR_BIT
) und die implizite Frage (wie funktioniert das) in der ursprünglichen Frage.
EIN char
in C und C++ stellt die kleinste Speichereinheit dar, die das C-Programm adressieren kann*.
CHAR_BIT
in C und C++ repräsentiert die Anzahl der Bits in a char
. Aufgrund anderer Anforderungen an den Zeichentyp muss es immer mindestens 8 sein. In der Praxis ist es auf allen modernen Allzweckcomputern genau 8, aber einige historische oder spezielle Systeme können höhere Werte haben.
Java hat kein Äquivalent zu CHAR_BIT
oder sizeof
, ist dies nicht erforderlich, da alle primitiven Typen in Java eine feste Größe haben und die interne Struktur von Objekten für den Programmierer undurchsichtig ist. Wenn Sie diesen Code nach Java übersetzen, können Sie ihn einfach ersetzen sizeof(int) * CHAR_BIT - 1
um den Festwert 31.
In diesem speziellen Code wird es verwendet, um die Anzahl der Bits in einer zu berechnen int
. Beachten Sie, dass diese Berechnung davon ausgeht, dass die int
type enthält keine Füllbits.
Angenommen, Ihr Compiler entscheidet sich für die Vorzeichenerweiterung bei Bitverschiebungen von vorzeichenbehafteten Zahlen und unter der Annahme, dass Ihr System die 2er-Komplementdarstellung für negative Zahlen verwendet, bedeutet dies Folgendes mask
ist 0 für einen positiven oder Nullwert und -1 für einen negativen Wert.
Um eine Zweierkomplementzahl zu negieren, müssen wir ein bitweises not ausführen und dann eins hinzufügen. Entsprechend können wir eins subtrahieren und dann bitweise negieren.
Unter der Annahme, dass die Zweierkomplementdarstellung wieder -1 durch alle Einsen dargestellt wird, entspricht exklusiv oder mit -1 der bitweisen Negation.
Wenn also v null ist, wird die Zahl in Ruhe gelassen, wenn v eins ist, wird sie negiert.
Beachten Sie, dass ein signierter Überlauf in C und C++ ein undefiniertes Verhalten ist. Also mit diesem abs
Implementierung auf dem negativsten Wert führt zu undefiniertem Verhalten. Dies kann behoben werden, indem Umwandlungen hinzugefügt werden, sodass die letzte Zeile des Programms in unsigned int ausgewertet wird.
* Was normalerweise, aber nicht notwendigerweise, mit der kleinsten Speichereinheit identisch ist, die die Hardware adressieren kann. Eine Implementierung kann möglicherweise mehrere Einheiten eines hardwareadressierbaren Speichers zu einer Einheit eines programmadressierbaren Speichers kombinieren oder eine Einheit eines hardwareadressierbaren Speichers in mehrere Einheiten eines programmadressierbaren Speichers aufteilen.
Sie sollten sich darüber im Klaren sein, dass dieser Code vom implementierungsdefinierten Verhalten der Bitverschiebung nach rechts für Typen mit Vorzeichen abhängt. gcc verspricht, immer das vernünftige Verhalten (Vorzeichen-Bit-Erweiterung) zu geben, aber ISO C erlaubt der Implementierung, die oberen Bits mit Nullen zu füllen.
Eine Möglichkeit, dieses Problem zu umgehen:
#ifdef HAVE_SIGN_EXTENDING_BITSHIFT
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
#else
int const mask = -((unsigned)v >> sizeof(int) * CHAR_BIT - 1);
#endif
Dein Makefile
oder config.h
usw. definieren können HAVE_SIGN_EXTENDING_BITSHIFT
zur Build-Zeit abhängig von Ihrer Plattform.
Notiz:
v + mask
Kann führen zuint
Überlauf – was ist undefiniertes Verhalten.(v ^ mask) - mask
kann ähnliche Probleme haben.– chux – Wiedereinsetzung von Monica
3. November 2021 um 21:31 Uhr