Absolutwert abs(x) mit bitweisen Operatoren und boolescher Logik [duplicate]

Lesezeit: 2 Minuten

beta_me Benutzeravatar von me_beta
beta_me ich_beta

Wie funktioniert das?

Die Idee ist zu machen abs(x) Verwenden Sie bitweise Operatoren für ganze Zahlen (unter der Annahme von 32-Bit-Wörtern):

y = x >> 31
(x + y) ^ y // This gives abs(x) (is ^ XOR)?

  • @cmaster-reinstatemonica wollte eigentlich lernen, wie es funktioniert

    – beta_me me_beta

    9. März 2020 um 14:26 Uhr

  • Wenn Sie diese Art von Bit-Twiddling mögen, ist das Buch Hacker’s Delight (2nd ed) voll von dieser Art von bitweisen Manipulationen. (Der Begriff “Hacker” wird im älteren, positiven Sinne verwendet.)

    – Eljay

    9. März 2020 um 14:28 Uhr

  • @cmaster-reinstatemonica Ich bin neugierig, die ISA, die heute gebräuchlich ist, hat eine ganze Zahl Absolutwertbefehl in Nicht-Vektorregistern? Nicht x86, nicht ARM. Macht nur in SPE, xtensa ist nicht gerade Mainstream. Ansonsten ist es nur Gleitkomma oder Vektor. Hauptsächlich, weil Compiler entsprechenden Code generieren können exakt an den OP-Code, sodass die Anweisung, die Sie sich für die CPU vorstellen, nicht erforderlich ist.

    – EÖF

    9. März 2020 um 22:11 Uhr


  • Als Referenz habe ich profiliert (die ähnliche Version) (x^y)-y als schneller als std::abs(x) auf x86-64.

    – imallett

    10. März 2020 um 5:19 Uhr

  • @EOF In der Tat habe ich über die Vektoranweisungen nachgedacht. Aber selbst X86 hat sowohl eine Negation (wie praktisch alle ISAs) als auch bedingte Bewegungen. Mein Hauptpunkt ist: Wenn Sie etwas wissen, ist das schneller als a >= 0 ? a : -aerzählen Sie Ihren Compiler-Leuten davon, und sie werden seine Optimierung ändern.

    – Cmaster – Wiedereinsetzung von Monica

    10. März 2020 um 7:04 Uhr

Benutzeravatar von Eric Postpischil
Eric Postpischil

Unter der Annahme von 32-Bit-Wörtern, wie in der Frage angegeben:

Für negativ x, x >> 31 ist in den C- und C++-Standards implementierungsdefiniert. Der Autor des Codes erwartet Zweierkomplement-Ganzzahlen und eine arithmetische Rechtsverschiebung, in der x >> 31 erzeugt alle Nullbits, wenn das Vorzeichenbit von x Null und alle Eins-Bits, wenn das Vorzeichenbit Eins ist.

Also wenn x ist positiv oder null, y ist null, und x + y ist xAlso (x + y) ^ y ist xwas der absolute Wert von ist x.

Wenn x ist negativ, y ist alles Einsen, was −1 im Zweierkomplement darstellt. Dann x + y ist x - 1. Dann invertiert XORing mit allen Einsen alle Bits. Das Invertieren aller Bits entspricht dem Nehmen des Zweierkomplements und dem Subtrahieren von Eins, und das Zweierkomplement ist die Methode, die verwendet wird, um ganze Zahlen im Zweierkomplementformat zu negieren. Mit anderen Worten, XORing q bei allen gibt -q - 1. So x - 1 XORed mit allen Einsen erzeugt -(x - 1) - 1 = -x + 1 - 1 = -xwas der absolute Wert von ist x ausser wenn x ist der minimal mögliche Wert für das Format (–2.147.483.648 für das 32-Bit-Zweierkomplement). In diesem Fall ist der Absolutwert (2.147.483.648) zu groß, um dargestellt zu werden, und das resultierende Bitmuster ist nur das Original x.

  • Was hier also tatsächlich passiert, ist, dass y zu -1 wird, dh arithmetische Verschiebung, wenn x<0, ich habe es verstanden.

    – beta_me me_beta

    9. März 2020 um 14:32 Uhr

  • @Beta WENN Ihre Implementierung von C oder C++ hält sich an Zweierkomplement-Ganzzahlen und eine arithmetische Rechtsverschiebung. Vor C++20 waren nur Ganzzahlen erforderlich, um alle Werte dazwischen darzustellen -(2^(N-1) - 1) zu +(2^(N-1) - 1), oder sein Komplement. Die meisten Compiler haben das Zweierkomplement gemacht, weil sie keine Monster sind, aber es war möglich. Der C++20-Standard verlangt, dass Ganzzahlen Zweierkomplemente sind. Wie Eric oben sagt, ist die Rechtsverschiebung bei einer negativen ganzen Zahl implementierungsdefiniert, aber wahrscheinlich arithmetische Rechtsverschiebung.

    – JohnFilleau

    9. März 2020 um 15:18 Uhr

  • Tatsächlich ist der Typ von Y nicht angegeben, Sie haben einen sehr wichtigen Teil dieses Algorithmus verpasst, nämlich “Wenn Y 32-Bit-Vorzeichenlos ist, funktioniert dies immer noch”. Das liegt daran, dass es kreative Zuordnungen von Bits verwendet und die Definition von 2er-Komplementzahlen nutzt, die ohne Rücksicht auf die Vorzeichen des Systems funktioniert. Es ist ein alter Numberical-Recipies-Trick, der tatsächlich (damals) einige Aspekte der Portabilität verbesserte, in einer Art und Weise, wie wir uns jetzt wünschen, dass niemand auf diese Weise „verbessert“ würde.

    – Edwin Buck

    9. März 2020 um 15:49 Uhr

  • Für andere, die sich fragen, wie ich bemerkt habe, dass es sich um einen numerischen Rezeptansatz handelt, ist die häufige Wiederverwendung von Registern ein guter Hinweis. Solches Bit-Mongering war in den Tagen der Programmierung, die hauptsächlich Assembler waren, gängige Praxis, und viele Optimierungen wie diese wurden in C portiert, was sie dann auf C++ / Java / usw. überschwappen ließ. Heute sind diese Techniken meistens unter einer netten API verpackt Anrufe, aber gelegentlich sieht man jemanden, der eine Lösung wie diese “optimiert”.

    – Edwin Buck

    9. März 2020 um 15:54 Uhr

  • @EdwinBuck: Ja, heutzutage kennen Optimierungscompiler diesen Trick und werden ihn gegebenenfalls verwenden, wenn Sie schreiben unsigned absx = x<0 ? -x : x; (Oder etwas Besseres, das einen signierten Überlauf von UB in vermeidet -x für die negativste Zweierkomplementzahl).

    – Peter Cordes

    9. März 2020 um 18:51 Uhr


Benutzeravatar von Ayxan Haqverdili
Ayxan Haqverdili

Dieser Ansatz beruht auf vielen implementierungsspezifischen Verhaltensweisen:

  1. Davon geht es aus x ist 32 Bit breit. Sie könnten dies jedoch beheben, indem Sie x >> (sizeof(x) * CHAR_BIT - 1)
  2. Es wird davon ausgegangen, dass die Maschine die Zweierkomplementdarstellung verwendet.
  3. Der Rechtsverschiebungsoperator kopiert das Vorzeichenbit von links nach rechts.

Beispiel mit 3 Bit:

101 -> x = -3
111 -> x >> 2

101 + 111 = 100 -> x + y

100 XOR 111 -> 011 -> 3

Dies ist nicht tragbar.

  • Ich bin keiner von ihnen, aber das beantwortet keine OP-Fragen. Nur Kommentare tun

    – solid.py

    9. März 2020 um 14:09 Uhr

  • Nicht mein DV, und ich habe den C++20-Standard nicht gelesen, aber unter C (auch derzeit markiert) ist die Rechtsverschiebung eines negativen vorzeichenbehafteten Werts implementierungsdefiniert, daher gibt es andere Probleme mit diesem Ansatz.

    – Andreas Henle

    9. März 2020 um 14:09 Uhr

  • In der OP-Frage, die xor Betrieb ist mit y (nicht x)

    – BiagioF

    9. März 2020 um 14:11 Uhr

  • Der Code geht nicht davon aus int ist 32 Bit, weil es keine gibt int überhaupt in der Frage. Und es gibt ausdrücklich an, dass die Wörter, mit denen es arbeitet, unabhängig von der Art, 32 Bit sind.

    – Eric Postpischil

    9. März 2020 um 14:26 Uhr

  • @EricPostpischil Vielen Dank für das Feedback. Ist diese Umformulierung besser?

    – Ayxan Haqverdili

    9. März 2020 um 14:28 Uhr

Benutzeravatar von Edwin Buck
Edwin Buck

Dies ist nicht portabel, aber ich werde erklären, warum es trotzdem funktioniert.

Die erste Operation nutzt ein Merkmal negativer Zweierkomplementzahlen aus, nämlich dass das erste Bit 1 ist, wenn es negativ ist, und 0, wenn es positiv ist. Dies liegt daran, dass die Zahlen von reichen

Das folgende Beispiel gilt für 8 Bit, kann aber auf eine beliebige Anzahl von Bits extrapoliert werden. In Ihrem Fall sind es 32 Bit (aber 8 Bit zeigen die Bereiche einfacher an)

10000000 (smallest negative number)
10000001 (next to smallest)
...
11111111 (negative one)
00000000 (zero)
00000001 (one)
...
01111110 (next to largest)
01111111 (largest)

Gründe für die Verwendung der 2er-Komplementcodierung von Zahlen ergeben sich aus der Eigenschaft, dass das Addieren einer negativen Zahl zu ihrer positiven Zahl Null ergibt.

Um nun das Negativ einer 2er-Komplementzahl zu erstellen, müssten Sie das tun

  1. Nehmen Sie die Umkehrung (bitweise nicht) einer Eingabezahl.
  2. Fügen Sie eins hinzu.

Der Grund, warum die 1 hinzugefügt wird, besteht darin, die Funktion der Addition zu erzwingen, die das Register auf Null setzt. Sehen Sie, wenn es nur x + ~(x) wäre, dann würden Sie ein Register aller Einsen bekommen. Indem Sie eins hinzufügen, erhalten Sie einen kaskadierenden Übertrag, der ein Register mit Nullen ergibt (mit einer 1 im Übertrag des Registers).

Dieses Verständnis ist wichtig, um zu wissen, “warum” der von Ihnen bereitgestellte Algorithmus (meistens) funktioniert.

y = x >> 31   // this line acts like an "if" statement.
              // Depending on if y is 32 signed or unsigned, when x is negative, 
              // it will fill y with 0xFFFFFFFF or 1.  The rest of the 
              // algorithm doesn't, care because it accommodates both inputs.
              // when x is positive, the result is zero.

Wir werden untersuchen (x ist zuerst positiv)

(x + y) ^ y   // for positive x, first we substitute the y = 0
(x + 0) ^ 0   // reduce the addition
(x) ^ 0       // remove the parenthesis
x ^ 0         // which, by definition of xor, can only yield x
x

Lassen Sie uns nun untersuchen (x ist negativ, y ist 0xFFFFFFFF (y wurde signiert))

(x + y) ^ y   // first substitute the Y
(x + 0xFFFFFFFF) ^ 0xFFFFFFFF // note that 0xFFFFF is the same as 2's complement -1
(x - 1) ^ 0xFFFFFFFF // add in a new variable Z to hold the result
(x - 1) ^ 0xFFFFFFFF = Z  // take the ^ 0xFFFFFFFF of both sides
(x - 1) ^ 0xFFFFFFFF ^ 0xFFFFFFFF = Z ^ 0xFFFFFFFF // reduce the left side
(x - 1) = z ^ 0xFFFFFFFF // note that not is equivalent to ^ 0xFFFFFFFF
(x - 1) = ~(z) // add one to both sides
x - 1 + 1 = ~(z) + 1 //  reduce
x = ~(z) + 1  // by definition z is negative x (for 2's complement numbers)

Lassen Sie uns nun untersuchen (x ist negativ, y ist 0x01 (y war unsigned))

(x + y) ^ y   // first substitute the Y
(x + 1) ^ 0x00000001 // note that x is a 2's complement negative, but is
                     // being treated as unsigned, so to make the unsigned
                     // context of x tracable, I'll add a -(x) around the X
(-(x) + 1) ^ 0x00000001 // which simplifies to
(-(x - 1)) ^ 0x00000001 // negative of a negative is positive
(-(x - 1)) ^ -(-(0x00000001)) // substituting 1 for bits of -1
(-(x - 1)) ^ -(0xFFFFFFFF) // pulling out the negative sign
-((x-1) ^ 0xFFFFFFFF) // recalling that while we added signs and negations to
                      // make the math sensible, there's actually no place to
                      // store them in an unsigned storage system, so dropping
                      // them is acceptable
x-1 ^ 0XFFFFFFFF = Z // introducing a new variable Z, take the ^ 0xFFFFFFF of both sides
x-1 ^ 0xFFFFFFFF ^ 0xFFFFFFFF = Z ^ 0xFFFFFFFF // reduce the left side
x-1 = z ^ 0xFFFFFFFF // note that not is equivalent to ^ 0xFFFFFFFF
x-1 = ~(z) // add one to both sides
x - 1 + 1 = ~(z) + 1 //  reduce
x = ~(z) + 1  // by definition z is negative x (for 2's complement numbers, even though we used only non-2's complement types)

Beachten Sie, dass die obigen Beweise zwar für eine allgemeine Erklärung passabel sind, die Realität jedoch darin besteht, dass diese Beweise wichtige Grenzfälle nicht abdecken, wie z die gleiche Anzahl von Bits.

  • Letzter Absatz: x = 0xFFFFFFFF ist -1. Ich glaube du meintest x = 0x80000000, der Sonderfall der negativsten Zahl für das Zweierkomplement. Sie können damit umgehen, indem Sie das abs-Ergebnis als unsigned behandeln. (Und schreiben Sie es sorgfältig, um die Möglichkeit eines C-Vorzeichenüberlaufs von UB zu vermeiden, z. B. indem Sie die - on unsigned um einen Überlauf von 0x7FFFFFFF auf 0x80000000 zu vermeiden)

    – Peter Cordes

    9. März 2020 um 17:01 Uhr

  • Ihre Notation ist seltsam; Sie scheinen zu verwenden ! für bitweise Umkehrung (Einerkomplement). Aber das ist eine C-Frage; der C-Operator dafür ist ~ (Tilde). ! in C ist logisch nicht, was nur 0 oder 1 erzeugen kann.

    – Peter Cordes

    9. März 2020 um 17:02 Uhr

  • @PeterCordes Ich habe den ersten Kommentar verpasst, den repariere ich auch. Vielen Dank für das sorgfältige Lesen.

    – Edwin Buck

    9. März 2020 um 19:30 Uhr

  • Ich habe mit dem Upvoting gewartet, bis die von mir festgestellten Probleme behoben waren. Sieht jetzt gut aus. Eine nette Diskussion darüber, wie Carry-Propagation Bits umdreht, um -1 in 0 umzuwandeln.

    – Peter Cordes

    9. März 2020 um 19:52 Uhr

Benutzeravatar von schnedan
schnedan

Ich benutze diesen Code, zuerst die Berechnung des Zweierkomplements (der Wächter stellt nur mit einer Kompilierungszeitüberprüfung sicher, dass die Vorlage eine Ganzzahl ist)

/**
 * Zweierkomplement - Two's Complement
 */
template<typename T> constexpr auto ZQ(T const& _x) noexcept ->T{
  Compile::Guards::IsInteger<T>();
  return ((~(_x))+1);
}

und in einem zweiten Schritt wird daraus die Ganzzahl abs() berechnet

/**
 * if number is negative, get the same number with positiv sign
 */
template<typename T> auto INTABS(T const _x) -> typename std::make_unsigned<T>::type{
  Compile::Guards::IsInteger<T>();
  return static_cast<typename std::make_unsigned<T>::type>((_x<0)?(ZQ<T>(_x)):(_x));
}

Warum verwende ich diese Art von Code:
* Prüfungen zur Kompilierzeit
* funktioniert mit allen Integer-Größen
* Portabel von kleinen µC bis zu modernen Kernen
* Es ist klar, dass wir das Zweierkomplement betrachten müssen, also brauchen Sie einen vorzeichenlosen Rückgabewert, zB für 8bit abs(-128)=128 kann nicht in einer vorzeichenbehafteten Ganzzahl ausgedrückt werden

1410860cookie-checkAbsolutwert abs(x) mit bitweisen Operatoren und boolescher Logik [duplicate]

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

Privacy policy