Sättigendes Subtrahieren/Addieren für vorzeichenlose Bytes

Lesezeit: 6 Minuten

Benutzeravatar von ovk
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.

    – 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

Benutzeravatar von Shafik Yaghmour
Shafik Yaghmur

Der Artikel Verzweigungsfreie Sättigungsarithmetik gibt Strategien dazu:

Ihre Additionslösung lautet wie folgt:

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

Benutzeravatar von user1969104
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 – Stellt Monicas Benutzeravatar wieder her
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.

Benutzeravatar von Yves Daoust
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;

Benutzeravatar von gnasher729
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.

1419320cookie-checkSättigendes Subtrahieren/Addieren für vorzeichenlose Bytes

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

Privacy policy