Sättigendes Subtrahieren/Addieren für vorzeichenlose Bytes
Lesezeit: 6 Minuten
gut
Stellen Sie sich vor, ich habe zwei vorzeichenlose Bytes b und x. Ich muss rechnen bsub wie b - x und badd wie b + x. Ich möchte jedoch nicht, dass während dieser Operationen ein Unterlauf/Überlauf auftritt. Zum Beispiel (Pseudocode):
b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254
und
b = 250; x = 10;
badd = b + x; // badd must be 255, not 4
Der offensichtliche Weg, dies zu tun, beinhaltet das Verzweigen:
bsub = b - min(b, x);
badd = b + min(255 - b, x);
Ich frage mich nur, ob es bessere Möglichkeiten gibt, dies zu tun, dh durch einige hacky Bit-Manipulationen?
y ^ ((x ^ y) & -(x < y)) zum int Typen bewertet min(x, y) ohne Verzweigung. Dies könnte Teil einer möglichen Lösung sein, basierend auf dem, was Sie bisher haben.
– Bathseba
2. November 2015 um 15:41 Uhr
Vielleicht geklemmte Inkrement-Ganzzahl? ist hilfreich.
– Shafik Yaghmour
2. November 2015 um 15:46 Uhr
Ist das eine C- oder eine C++-Frage? Bitte wähle eines.
Brauchen Sie es, um tragbar zu sein? Denn wenn Sie sich eine bestimmte Architektur ansehen, gibt es wahrscheinlich eine nette einzelne Anweisung. Ich weiß, dass ARM eine Sättigungsvektoraddition und -subtraktion für Bytes hat. Auf X86 die _mm_adds_epi8 Intrinsic führt eine Sättigungsaddition von 16 Bytes in einer einzigen Anweisung durch.
u32b sat_addu32b(u32b x, u32b y)
{
u32b res = x + y;
res |= -(res < x);
return res;
}
modifiziert für uint8_t:
uint8_t sat_addu8b(uint8_t x, uint8_t y)
{
uint8_t res = x + y;
res |= -(res < x);
return res;
}
und ihre Subtraktionslösung ist:
u32b sat_subu32b(u32b x, u32b y)
{
u32b res = x - y;
res &= -(res <= x);
return res;
}
modifiziert für uint8_t:
uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
uint8_t res = x - y;
res &= -(res <= x);
return res;
}
@ user1969104 das mag der Fall sein, aber wie der Kommentar im Artikel zeigt, wird das gelöst, indem vor dem Anwenden von unärem Minus auf unsigned umgewandelt wird. In der Praxis ist es unwahrscheinlich, dass Sie sich mit etwas anderem als dem Zweierkomplement befassen müssen.
– Shafik Yaghmour
3. November 2015 um 4:09 Uhr
Dies mag eine gute C-Antwort sein, ist aber keine sehr gute C++-Antwort.
– Yakk – Adam Nevraumont
3. November 2015 um 18:46 Uhr
@Yakk Was macht dies zu einer “schlechten” C++-Antwort? Dies sind grundlegende mathematische Operationen, und ich sehe nicht, wie sie nur als C oder als schlechtes C++ interpretiert werden würden.
– JPhi1618
3. November 2015 um 19:54 Uhr
@ JPhi1618 Eine bessere C ++ – Antwort könnte sein template<class T>struct sat{T t;}; mit überladenen Operatoren, die sättigen? Richtige Verwendung von Namespaces. Meistens Zucker.
– Yakk – Adam Nevraumont
3. November 2015 um 19:59 Uhr
@ Yakk, Ah, ok. Ich habe dies nur als Minimalbeispiel gesehen, das das OP nach Bedarf anpassen könnte. Ich würde nicht erwarten, dass eine Implementierung so vollständig ist. Danke fürs klarstellen.
– JPhi1618
3. November 2015 um 20:02 Uhr
Benutzer1969104
Eine einfache Methode besteht darin, einen Überlauf zu erkennen und den Wert entsprechend wie unten zurückzusetzen
bsub = b - x;
if (bsub > b)
{
bsub = 0;
}
badd = b + x;
if (badd < b)
{
badd = 255;
}
GCC kann die Überlaufprüfung beim Kompilieren mit -O2 in eine bedingte Zuweisung optimieren.
Ich habe gemessen, wie viel Optimierung im Vergleich zu anderen Lösungen. Bei über 1000000000 Operationen auf meinem PC dauerte diese Lösung und die von @ShafikYaghmour durchschnittlich 4,2 Sekunden und die von @chux durchschnittlich 4,8 Sekunden. Diese Lösung ist auch besser lesbar.
@ user694733 Es ist nicht wegoptimiert, es ist abhängig vom Carry-Flag in eine bedingte Zuweisung optimiert.
– fuz
2. November 2015 um 16:00 Uhr
Ja user694733 hat recht. Es wird in eine bedingte Zuweisung optimiert.
– Benutzer1969104
2. November 2015 um 16:02 Uhr
Dies würde nicht für alle Fälle funktionieren, zum Beispiel badd: b = 155 x =201, dann badd = 156, und das ist größer als b. Sie müssten das Ergebnis je nach Operation mit min() oder max() der beiden Variablen vergleichen
– Christian F
17. November 2015 um 13:59 Uhr
@CristianF Wie berechnet man 155+201 = 156? Ich denke, es muss 155 + 201 = 356% 256 = 100 sein. Ich glaube nicht, dass min(), max() in einer beliebigen Kombination von b, x-Werten benötigt wird.
– Benutzer1969104
17. November 2015 um 14:36 Uhr
Chux – Wiedereinsetzung von Monica
Zur Subtraktion:
diff = (a - b)*(a >= b);
Zusatz:
sum = (a + b) | -(a > (255 - b))
Evolution
// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too
Danke an @R_Kapp
Danke an @NathanOliver
Diese Übung zeigt den Wert des einfachen Codierens.
sum = b + min(255 - b, a);
Zum sum vielleicht (a + b) | -(a <= (255 - b))?
– R_Kapp
2. November 2015 um 15:58 Uhr
Du könnte tun sum = ((a + b) | (!!((a + b) & ~0xFF) * 0xFF)) & 0xFFvorausgesetzt sizeof(int) > sizeof(unsigned char)aber das sieht so komplex aus, dass ich nicht weiß, ob Sie damit etwas gewinnen würden (außer Kopfschmerzen).
– Benutzer694733
2. November 2015 um 16:17 Uhr
@ user694733 Ja und vielleicht sogar (a+b+1)*(a <= (255-b)) - 1.
– chux – Wiedereinsetzung von Monica
2. November 2015 um 16:20 Uhr
@NathanOliver Danke für das Versehen – der aussagekräftige Aspekt dabei ist, dass die sub war einfach, wie die Grenze war 0. Aber andere Grenzen stellen Komplikationen dar und folgen dem Kommentar von user2079303.
– chux – Wiedereinsetzung von Monica
2. November 2015 um 16:22 Uhr
@ user1969104 OP war weder auf “besser” (Coderaum vs. Geschwindigkeitsleistung) noch auf Zielplattform oder Compiler klar. Die Geschwindigkeitsbewertung ist im Zusammenhang mit dem nicht geposteten größeren Problem am sinnvollsten.
– chux – Wiedereinsetzung von Monica
2. November 2015 um 16:51 Uhr
Wenn Sie eine ausreichend aktuelle Version von gcc oder clang (vielleicht auch einige andere) verwenden, können Sie dies verwenden Einbauten Überlauf zu erkennen.
if (__builtin_add_overflow(a,b,&c))
{
c = UINT_MAX;
}
Zur Ergänzung:
unsigned temp = a+b; // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);
Zur Subtraktion:
unsigned temp = a-b; // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);
Keine Vergleichsoperatoren oder Multiplikationen erforderlich.
Yves Daust
Alles kann in vorzeichenloser Byte-Arithmetik durchgeführt werden
// Addition without overflow
return (b > 255 - a) ? 255 : a + b
// Subtraction without underflow
return (b > a) ? 0 : a - b;
gnasher729
Wenn Sie dies mit zwei Bytes tun möchten, verwenden Sie den einfachsten möglichen Code.
Wenn Sie dies mit zwanzig Milliarden Bytes tun möchten, prüfen Sie, welche Vektorbefehle auf Ihrem Prozessor verfügbar sind und ob diese verwendet werden können. Möglicherweise stellen Sie fest, dass Ihr Prozessor 32 dieser Operationen mit einer einzigen Anweisung ausführen kann.
14193200cookie-checkSättigendes Subtrahieren/Addieren für vorzeichenlose Bytesyes
y ^ ((x ^ y) & -(x < y))
zumint
Typen bewertetmin(x, y)
ohne Verzweigung. Dies könnte Teil einer möglichen Lösung sein, basierend auf dem, was Sie bisher haben.– Bathseba
2. November 2015 um 15:41 Uhr
Vielleicht geklemmte Inkrement-Ganzzahl? ist hilfreich.
– Shafik Yaghmour
2. November 2015 um 15:46 Uhr
Ist das eine C- oder eine C++-Frage? Bitte wähle eines.
– fuz
2. November 2015 um 16:02 Uhr
@AlanCampbell heißt es Arithmetik sättigen.
– Shafik Yaghmour
3. November 2015 um 2:53 Uhr
Brauchen Sie es, um tragbar zu sein? Denn wenn Sie sich eine bestimmte Architektur ansehen, gibt es wahrscheinlich eine nette einzelne Anweisung. Ich weiß, dass ARM eine Sättigungsvektoraddition und -subtraktion für Bytes hat. Auf X86 die
_mm_adds_epi8
Intrinsic führt eine Sättigungsaddition von 16 Bytes in einer einzigen Anweisung durch.– porglezomp
3. November 2015 um 4:30 Uhr