8-bit-AVR: int32 to uint32

[Leo B. (luigi)]

Servus zusammen,

ich steh vermutlich grad nur mitten auf der Leitung, aber folgendes 
Problem:

Ich rechne auf einem 8-bit AVR ATmega, und habe einen 32-bit int mit 
Vorzeichen, dessen Betrag ich ermitteln möchte.
Nun ist mir klar, dass das Ergebnis (also der Betrag) ein unsigned 
32-bit sein muss, da ja INT_MAX eins kleiner ist als -INT_MIN.
Mein Vorgänger hat mir im Code jetzt etwas hinterlassen, das vom gcc zu 
ziemlich viel Programmcode aufgeblasen wird:

static uint32_t abs( int32_t a )
{
  if( a < 0 )
  {
    // -INT_MIN ist idR. größer als INT_MAX und nicht mehr
    // als int darstellbar! Man muss daher bei der Bildung
    // des Absolutbetrages aufpassen.
    return -( (uint32_t)(-(a+1)) + 1 );
  }
  return (uint32_t)a;
}

und nun stehe ich auf dem Schlauch, warum er das so komplex macht...
Ergibt es nicht das selbe einfach folgendes zu schreiben?

static uint32_t abs( int32_t a )
{
  if( a < 0 )
    return (uint32_t)(-a);
  return (uint32_t)a;
}

Irgendwie leuchtet es mir nicht ganz ein warum das so komplex sein soll.

Vielen Dank
Leo

[Eric B. (beric)]

Dein Vorgänger hat hier versucht den Fall a == 0x80000000 einzufangen, 
wo es nichts einzufangen gab :-/ Gegen deiner Lösung ist m.E. nichts 
einzuwenden.

Noch kürzer wäre:

static uint32_t abs( int32_t a )
{
  return (uint32_t)((a < 0)? -a: a);
}

[Tassilo H. (tassilo_h)]

Hmm, aber wird -a nicht als signed 32-bit berechnet? Und wenn ich mich 
recht entsinne, ist das Überlaufverhalten bei signed integer nicht 
definiert. D.h. abhängig von der Implementierung kann das gutgehen oder 
auch nicht. Und noch gemeiner: Selbst wenn das gutgeht, wenn man eine 
Variable übergibt, kann das trotzdem noch schiefgehen, wenn man einen 
Ausdruck übergibt, von dem der Compiler weiß, daß es INT32_MIN ist. Dann 
kann der Optimierer jedwede Berechnung sein lassen und das Ergebnis als 
beliebig annehmen (d.h. i.a. so, daß am meisten anderer Code eingespart 
werden kann).

Besser evtl. so:

if (a == INT32_MIN) {
  return ((uint32_t)INT32_MAX)+1ul;
} else {
  return a < 0 ? -a : a;
}

[M. K. (sylaina)]

Tassilo H. schrieb:
> Hmm, aber wird -a nicht als signed 32-bit berechnet? Und wenn ich mich
> recht entsinne, ist das Überlaufverhalten bei signed integer nicht
> definiert.

Und was soll da überlaufen? Wenn der übergebene signed int32 kleiner 0 
ist wird schlicht der übergebene signed int32 mit -1 multipliziert und 
jeder Compiler heute weiß, dass er dafür lediglich nur ein einziges bit 
toggeln muss.

[Carl D. (jcw2)]

Michael K. schrieb:
> Tassilo H. schrieb:
>> Hmm, aber wird -a nicht als signed 32-bit berechnet? Und wenn ich mich
>> recht entsinne, ist das Überlaufverhalten bei signed integer nicht
>> definiert.
>
> Und was soll da überlaufen? Wenn der übergebene signed int32 kleiner 0
> ist wird schlicht der übergebene signed int32 mit -1 multipliziert und
> jeder Compiler heute weiß, dass er dafür lediglich nur ein einziges bit
> toggeln muss.

Hoffentlich weiß der Compiler eher, daß er die anderen 31 auch togglen 
muß und zudem noch 1 addieren.

[Sebastian V. (sebi_s)]

Überlaufverhalten von signed int ist nicht definiert. Ich habe in der 
MPIR Library (dem Fork von GMP) mal folgendes gesehen:

static uint32_t abs( int32_t a )
{
  if( a < 0 )
    return -(uint32_t)(a);
  return (uint32_t)a;
}

Meiner Meinung nach ist das wohldefiniert, da zuerst die Konvertierung 
von signed zu unsigned passiert (ggf. mit Überlauf) und dann eine 
Negation von dem unsigned Wert, ebenfalls mit wohldefiniertem 
Überlaufverhalten.

[Tassilo H. (tassilo_h)]

a) es ist kein einzelnes bit, sondern das Zweierkomplement
b) (-INT32_MIN) ist als int32_t nicht darstellbar, da -INT32_MIN = 
INT32_MAX+1. Die Rechnung wird aber erstmal als int32_t ausgeführt. 
Klar, wenn man das alles ignoriert, wird es auf den meisten 
Prozessorarchitekturen gutgehen, da das Zweierkomplement wieder 
0x80000000 ergibt, was nach uint32_t gecastet dann stimmt. 
Nichtsdestotrotz hat man zwischendrin etwas nicht definiertes, da 
-INT32_MIN eben nicht in ein int32_t passt.
Wenn der Compiler das merkt und man die Funktion mal mit zur Compilezeit 
bekannten INT32_MIN aufruft, könnte der Optimizer hingehen uns sagen, 
das ist eh alles nicht definiert, also laß ich jetzt allen Code weg, der 
mit dem Ergebnis weiterrechnet und nehme als Ergebnis irgendwas an. Muß 
nicht passieren, kann aber. Sowas gibt wundervoll schwer zu findende 
Bugs in Code, der eigentlich immer schon funktioniert hat...

[MagIO (Gast)]

Ja klar, 1 bit toggeln ;o)

-1 = %11111111111111111111111111111111
Toggelt man jetzt nur das Sign-bit wird daraus
%01111111111111111111111111111111 = INT32MAX

Das was man machen muss nennt sich Zweierkomplement:
Alle bits invertieren und eins dazuzählen.

[Tassilo H. (tassilo_h)]

Sebastian V. schrieb:
> Überlaufverhalten von signed int ist nicht definiert. Ich habe in der
> MPIR Library (dem Fork von GMP) mal folgendes gesehen:
>

static uint32_t abs( int32_t a )
> {
>   if( a < 0 )
>     return -(uint32_t)(a);
>   return (uint32_t)a;
> }

> Meiner Meinung nach ist das wohldefiniert, da zuerst die Konvertierung
> von signed zu unsigned passiert (ggf. mit Überlauf) und dann eine
> Negation von dem unsigned Wert, ebenfalls mit wohldefiniertem
> Überlaufverhalten.

Gute Lösung, stimmt, das ist definiert. -(uint32_t)a ist definiert als 
UINT32_MAX-a+1, was das richtige Ergebnis liefert.

[B. S. (bestucki)]

Leo B. schrieb:
> da ja INT_MAX eins kleiner ist als -INT_MIN.

Nicht zwingend. Nach Standard kann die Plattform auch das Einer- statt 
dem Zweierkomplement benutzen, dann ist der Betrag von MIN und MAX 
identisch. Wenn man also portabel programmieren will, muss man annehmen, 
dass z.B. ein signed char einen Wertebereich von -127 bis +127 hat, die 
mögliche -128 muss man natürlich trotzdem beachten. Ich weiss, ist 
Haarspalterei, die meisten Plattformen benutzen das Zweierkomplement.

Michael K. schrieb:
> jeder Compiler heute weiß, dass er dafür lediglich nur ein einziges bit
> toggeln muss.

Nur beim Einerkomplement. Beim Zweierkomplement siehts anders aus.

Michael K. schrieb:
> Und was soll da überlaufen?

Z.B. bei einem 16Bit int:

-(-32768)

Die Zahl +32768 existiert bei einem solchen int nicht => Überlauf.

Tassilo H. schrieb:
> Gute Lösung, stimmt, das ist definiert. -(uint32_t)a ist definiert als
> UINT32_MAX-a+1, was das richtige Ergebnis liefert.

Nein. Ein Cast einer negativen Zahl in einen unsigned Typen ist 
undefiniertes Verhalten. Edit: Moment, lese gerade noch, bin mir nicht 
mehr ganz sicher.

[Sebastian V. (sebi_s)]

be s. schrieb:
> Nein. Ein Cast einer negativen Zahl in einen unsigned Typen ist
> undefiniertes Verhalten. Edit: Moment, lese gerade noch, bin mir nicht
> mehr ganz sicher.

Ist definiert:

6.3.1.3 Signed and unsigned integers
[...]
Otherwise, if the new type is unsigned, the value is converted by 
repeatedly adding or subtracting one more than the maximum value that 
can be represented in the new type until the value is in the range of 
the new type.

[Tassilo H. (tassilo_h)]

Der cast ist definiert:

"the value is converted by repeatedly adding or subtracting one more 
than the maximum value that can be represented in the newtype until the 
value is in the range of the newtype."

Beim Zweierkomplement ändert sich also nix am Bitmuster und alle obigen 
Annahmen stimmen. Auf einer Einerkomplementmaschine stimmt das natürlich 
nicht, aber das ist jetzt eher unüblich.

[B. S. (bestucki)]

Danke für die Berichtigung. Umgekehrt ists abhängig von der 
Implementierung (Kapitel: Implementation-defined behavior):
> The result of, or the signal raised by, converting an integer to a
> signed integer type when the value cannot be represented in an object
> of that type (6.3.1.3).

Hatte wohl das im Kopf. Gerade wieder mal die Liste von undefiniertem 
Verhalten überflogen, die ist einfach zu lang...

[Klaus (Gast)]

Leo B. schrieb:
> und habe einen 32-bit int mit
> Vorzeichen, dessen Betrag ich ermitteln möchte.

> abs() liefert den absoluten Wert einer Zahl: Bei einer negativen
> Zahl wird das Vorzeichen vertauscht, eine positive Zahl wird
> unverändert zurückgegeben.

Funktioniert auf jeder Plattform und wird auch von jedem als das 
erkannt, was es sein soll. Alles andere ist maximum obfuscation.

MfG Klaus

[B. S. (bestucki)]

Klaus schrieb:
>> abs() liefert den absoluten Wert einer Zahl: Bei einer negativen
>> Zahl wird das Vorzeichen vertauscht, eine positive Zahl wird
>> unverändert zurückgegeben.
>
> Funktioniert auf jeder Plattform und wird auch von jedem als das
> erkannt, was es sein soll. Alles andere ist maximum obfuscation.

Beziehst du dich auf die Version aus stdlib.h? Denn für diese gelten 
folgende Einschränkungen:
> In C, only the int version exists.
> If the result cannot be represented by the returned type (such as
> abs(INT_MIN) in an implementation with two's complement signed values),
> it causes undefined behavior.
http://www.cplusplus.com/reference/cstdlib/abs/

[Johann L. (gjlayde)]

In C90 gibt es labs und ab C99 auch llabs.  Damit sollten 32-Bit und 
64-Bit abs doch nun wirklich kein Problem mehr sein...

[B. S. (bestucki)]

Johann L. schrieb:
> In C90 gibt es labs und ab C99 auch llabs.  Damit sollten 32-Bit und
> 64-Bit abs doch nun wirklich kein Problem mehr sein...

Jedoch mit der gleichen Einschränkung von undefiniertem Verhalten und 
diese soll hier eliminiert werden. Ausserdem, welche der drei Funktionen 
benutzt du, wenn du als Argument einen uint32_t hast und portabel 
programmieren willst? Das ist ein übler Nachteil, der daraus entstanden 
ist, den Typen eine variable Breite zuordnen zu dürfen.

[Johann L. (gjlayde)]

...außerdem sollte man einer Funktion nicht den gleichen Namen geben wie 
eine  Standard-Funktion (abs)

http://linux.die.net/man/3/abs

[Leo B. (luigi)]

Vielen herzlichen Dank,
habe wieder viel gelernt!
Und die Frage dürfte beantwortet sein. Danke!

Grüße Leo

[Mampf F. (mampf)]

Leo B. schrieb:

> static uint32_t abs( int32_t a )
> {
>   if( a < 0 )
>   {
>     // -INT_MIN ist idR. größer als INT_MAX und nicht mehr
>     // als int darstellbar! Man muss daher bei der Bildung
>     // des Absolutbetrages aufpassen.
>     return -( (uint32_t)(-(a+1)) + 1 );
>   }
>   return (uint32_t)a;
> }

IMHO müsste das auch per (~a)+1 funktionieren ... (2er-Komplement 
nehmen)

Oder simpler einfach -a wie in den Beiträgen vorher schon erklärt

Die Rechnung von deinem Kollegen sieht sonderbar aus ... Er wusste wohl, 
dass -a das zweierkomplement nimmt und versuchte dann per -(a+1) das zu 
kompensieren. Und das hat er gleich zweimal gemacht, nachdem er es in 
einen uint32 gecastet hat.

Seltsam das ist ...

[Daniel A. (daniel-a)]

Um mochmal zur Ursprungsfunktion zu kommen:

static uint32_t abs( int32_t a )
{
  if( a < 0 )
  {
    // -INT_MIN ist idR. größer als INT_MAX und nicht mehr
    // als int darstellbar! Man muss daher bei der Bildung
    // des Absolutbetrages aufpassen.
    return -( (uint32_t)(-(a+1)) + 1 );
  }
  return (uint32_t)a;
}

Das ist Identisch zu:

static uint32_t abs( int32_t a ){
  return a;
}

Begründung: Den cast kann man sich wegdenken, da dieser keinen Einfluss 
auf das Ergebniss hat, Wenn man dann ausklammert heben sich die 
Additionen auf, und die Subtraktionen auch.

Ich empfehle automatisierte Tests!