Left shift operation

[Hellhound]

Hallo zusammen,

ich implementiere aktuell einen UnitTest für meine floatToFixedPoint Umrechnung die ich im Pixelprocessing benötige.Dabei bin ich auf ein Verhalten gestoßen, dass ich mir nicht so ganz erklären kann. Für gültige Farbwerte [0.0f..1.0f] führe ich einen einfachen links shift um n bits eines float Wertes durch:

unsigned int fixed = fValue * (1<<nbits);

Nichts weltbewegendes. Klappt auch für alle 8,16,24 bit werte. Ich weiß, laut ISO C99 Spezifikation ist der Grenzwert 31, da er noch keinen Overflow erzeugt. Dennoch passen meine Tests für diesen Wert nicht und ich habe z.T. "marginale Abweichungen" in den Berechnungen.

Ich habe mal den Wert 0.2835f genommen und für 8,16,24 bits berechnet. Passt. Nehme ich den gleichen Wert für 31bit, dann passt es nicht mehr. Hier erhalte ich einen Wert von 608811584 und erwarte einen Wert von 608811614 ... Die Abweichungen kann ich mir noch mit der zunehmenden Genauigkeit erklären und der Ursache, dass der float nicht exakt 0.2835 ist sondern laut debugger als 0.283499986 behandelt wird. Wie ich diese Ungenauigkeit im Test abfange ist mir aktuell auch noch nicht klar, da ich hier keine floats im Resultat prüfe sondern unsigned ints und so kein Delta berücksichtigen kann ...

Mir ist auch aufgefallen dass ich nur bei 31 bits ein Problem mit dem shift operator habe. Die Anweisung wie oben dargestellt

unsigned int fixed = fValue * (1<<nbits);

Klappt nicht. Hier muß ich die Anweisung umbauen zu:

unsigned int shift = (1<<nbits);
unsigned int fixed = fValue*shift;

Um ein gültiges Resultat zu erhalten, ansonsten ist das Resultat falsch und ich erhalte statt der erwarteten 608811614 einen Wert
von 3686155712 ...

Als Vergleich habe ich zusätzlich mal mit 30bit gerechnet, hier funktioniert zwar noch der eigentliche shift Operator korrekt, aber ich
habe ebenfalls eine Abweichung im Ergebnis und erhalte 304405792 anstelle von 304405807.

Aber das der Shift Operator bei 31bits nicht mehr korrekt greift ist mir ein Rätsel.
Habe ich irgend etwas übersehen oder falsch verstanden?

Gruß
Hellhound

[joggel]

Also ich könnte mir vorstellen, das bei

Code: Alles auswählen

unsigned int fixed = fValue * (1<<nbits);

etwas schief gehen könnte.
Ich weiß nur nicht wie das casten intern genau funktioniert.
Es wäre ja möglich, das das Ergebnis von "1<<nbits" nach float gecastet wird.
Bei diesem cast geht eben Genauigkeit verloren, da float ja beschränkt genau ist.
Diese float-Zahlen sind ja fast eh nur "Näherungen".
Selbst dieser Wert "0.2835" kann nja nicht mal exakt mittels float dargestellt werden.

Nochmal Edit:

Um ein gültiges Resultat zu erhalten, ansonsten ist das Resultat falsch und ich erhalte statt der erwarteten 608811614 einen Wert
von 3686155712 ...

Das konnte ich reproduzieren mit:

Code: Alles auswählen

	
float fValue(0.2835f);
unsigned int nbits(31);
int shiftedInt(1<<nbits);
unsigned int fixed = fValue * shiftedInt;

Also wird der Grund dafür in der ersten Variante liegen, das "(1<<nbits)" als int und nicht "unsigned" int interpretiert wird, und dann gecastet! Also wenn "1<<nbits" wobei nbits=31 ist und das Ergebnis vom Typ Int, wird das Ergebnis negativ, weil das 31ste Bit das Vorzeichen angibt.
Multiplizierst Du dieses Ergebnis (negativ) mit einem positiven float Wert, kommt ja rechnerisch ein negativer Wert heraus. Da das Ergebnis aber vom Typ "unsigned int" ist, wird das 31ste Bit nicht als Vorzeichen interpretiert, sondern als Wert (2^31) und dann eben der Rest...

[Hellhound]

Hey stimmt, danke für den Schlag auf den Hinterkopf ;) Die 1 wird ja als int dargestellt, mit einem cast der 1 oder des ganzen Ausdrucks klappt es nun mit dem Shift operator, auch bei 31 bit Werten ... Nun muß ich nur noch das Rundungsproblem in den Griff bekommen ...

[dot]

Du kannst auch einfach 1U schreiben statt 1 ;)

Ich weiß, laut ISO C99 Spezifikation ist der Grenzwert 31, da er noch keinen Overflow erzeugt.

Laut ISO C99 Spezifikation ist der Grenzwert irgendeine Zahl >= 16 ;)

[Hellhound]

Du kannst auch einfach 1U schreiben statt 1

Na klar danke, da hab ich wohl schon wieder zuviel JAVA getankt :x

Laut ISO C99 Spezifikation ist der Grenzwert irgendeine Zahl >= 16

Hmm ich weiß grad nicht auf welchen Teil Du Dich beziehst, aber laut der Spezifikation für das
bitweise Shifting (6.5.7) müsste es 31 sein:

The type of the result is
that of the promoted left operand. If the value of the right operand is negative or is
greater than or equal to the width of the promoted left operand, the behavior is undefined.

[dot]

Auf den Teil wo steht dass ein int >= 16 bit hat ;)

EDIT: In C99 wär das §5.2.4.2.1 wenn dus ganz genau wissen willst^^

Worauf ich hinauswollte: Du kannst dich bei den exakten Größen der primitiven Typen nicht auf den Standard verlassen. Standard C/C++ ist nicht einfach nur für PCs gedacht sondern für alles Mögliche, von Waschmaschinen über Handys bis zu Raumfahrzeugen und Dingen die noch nichtmal erfunden sind. Die Standards definieren nur Mindestwerte. Laut Standard ist es sogar nichtmal sicher dass ein Byte 8 Bit hat, 21 wärn auch ok. Selbst wenn es nur um die Plattform PC geht kann man mittlerweile in Probleme laufen. Abhängig vom Compiler hat ein int auf x64 vielleicht 64bit. Wenn du einen Typ mit definierter Bitbreite brauchst dann verwend nicht int sondern verwend was aus stdint.h, z.B. uint32_t. Für den garantiert dir der Standard dass es sich immer um einen unsigned Integer handelt der exakt 32bit breit ist, so er existiert...

[kaiserludi]

Laut Standard ist es sogar nichtmal sicher dass ein Byte 8 Bit hat, 21 wärn auch ok.

Und es gibt sogar Systeme, auf denen ein Byte tatsächlich nicht 8 Bit groß ist, wenn sie auch Seltenheitswert besitzen:
http://stackoverflow.com/questions/5516 ... byte-8-bit

[BeRsErKeR]

Nun muß ich nur noch das Rundungsproblem in den Griff bekommen ...

Da floats von Haus aus sehr ungenau sind und du den Wert mit einem sehr großen Faktor (z.B. 2^31) multiplizierst wirst du wohl immer relativ große Abweichungen in Kauf nehmen müssen.

[Krishty]

Das Lustige ist, dass das Ergebnis auf x86 wahrscheinlich recht präzise ausfällt (weil alles mit 80-Bit-Präzision in der FPU berechnet wird) und auf x64 katastrophal (weil alles mit 32-Bit-Präzision in den SSE-Einheiten berechnet wird).

Hier, Hellhound, das wird dich durch den Winter bringen:
http://www.cplusplus.com/reference/clib ... ath/ldexp/
„the function returns x * 2^exp“

Gruß, Ky

[kaiserludi]

Das Lustige ist, dass das Ergebnis auf x86 wahrscheinlich recht präzise ausfällt (weil alles mit 80-Bit-Präzision in der FPU berechnet wird) und auf x64 katastrophal (weil alles mit 32-Bit-Präzision in den SSE-Einheiten berechnet wird).

Gibt eine lustige Fehlersuche, wenn man viele Jahre lang nicht angefassten X86-Code, der sich in komplexen Formeln überall darauf verlässt, dass sie Ergebnisse ziemlich genau sind, dann auf einmal für X64 kompilieren will :mrgreen: .